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.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00726556
Contributor : Stéphane Vialette <>
Submitted on : Thursday, August 30, 2012 - 3:43:11 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM

Links full text

Identifiers

Citation

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⟩

Share

Metrics

Record views

291