Finding Approximate and Constrained Motifs in Graphs

Abstract : One of the most relevant topics in the analysis of biological networks is the identification of functional motifs inside a network. A recent approach introduced in literature, called Graph Motif, represents the network as a vertex-colored graph, and the motif M as a multiset of colors. An occurrence of a motif M in a vertex-colored graph G is a connected induced subgraph of G whose vertex set is colored exactly as M. In this paper we investigate three different variants of the Graph Motif problem. The first two variants, Minimum Adding Motif (Min-Add Graph Motif) and Minimum Substitution Motif (Min-Sub Graph Motif), deal with approximate occurrences of a motif in the graph, while the third variant, Constrained Graph Motif (CGM), constrains the motif to contain a given set of vertices. We investigate the computational and parameterized complexity of the three problems. We show that Min-Add Graph Motifand Min-Sub Graph Motifare both NP-hard, even when M is a set, and the graph is a tree with maximum degree 4 in which each color appears at most twice. Then, we show that Min-Sub Graph Motifis fixed-parameter tractable when parameterized by the size of M. Finally, we consider the parameterized complexity of the CGMproblem; we give a fixed-parameter algorithm for graphs of bounded treewidth, and show that the problem is W[2]-hard when parameterized by ∣M∣, even if the input graph has diameter 2.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, 483 (-), pp.10-21. 〈10.1016/j.tcs.2012.08.023〉
Liste complète des métadonnées
Contributeur : Stéphane Vialette <>
Soumis le : jeudi 30 août 2012 - 15:43:11
Dernière modification le : mercredi 23 mai 2018 - 15:44:02

Lien texte intégral



Riccardo Dondi, Guillaume Fertin, Stéphane Vialette. Finding Approximate and Constrained Motifs in Graphs. Theoretical Computer Science, Elsevier, 2013, 483 (-), pp.10-21. 〈10.1016/j.tcs.2012.08.023〉. 〈hal-00726556〉



Consultations de la notice