1. Some Results on More Flexible Versions of Graph Motif
- Author
-
Florian Sikora, Romeo Rizzi, Dipartimento di Matematica e Informatica - Universita Udine (DIMI), Università degli Studi di Udine - University of Udine [Italie], Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,Factor-critical graph ,Vertex connectivity ,Computational Complexity (cs.CC) ,Computational biology Computational complexity Biological networks Graph motif problem ,Simplex graph ,law.invention ,Theoretical Computer Science ,Computational biology ,Combinatorics ,law ,Line graph ,[INFO]Computer Science [cs] ,inapproximability results ,Complement graph ,Distance-hereditary graph ,Mathematics ,Discrete mathematics ,High rate ,Biological data ,Multiset ,Biological networks ,Voltage graph ,Graph Motif ,FPT algorithms ,Computational complexity ,Computer Science - Computational Complexity ,Computational Theory and Mathematics ,Graph (abstract data type) ,Graph motif problem ,Motif (music) ,Null graph ,Biological network ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
International audience; The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Due to the high rate of noise in the biological data, more flexible definitions of the problem have been outlined. We present in this paper two inapproximability results for two different optimization variants of Graph Motif: one where the size of the solution is maximized, the other when the number of substitutions of colors to obtain the motif from the solution is minimized. We also study a decision version of Graph Motif where the connectivity constraint is replaced by the well known notion of graph modularity. While the problem remains N P-complete, it allows algorithms in F P T for biologically relevant parameterizations.
- Published
- 2014
- Full Text
- View/download PDF