Graph Motif Problems Parameterized by Dual

Authors Guillaume Fertin, Christian Komusiewicz



PDF
Thumbnail PDF

File

LIPIcs.CPM.2016.7.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Guillaume Fertin
Christian Komusiewicz

Cite AsGet BibTex

Guillaume Fertin and Christian Komusiewicz. Graph Motif Problems Parameterized by Dual. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CPM.2016.7

Abstract

Let G=(V,E) be a vertex-colored graph, where C is the set of colors used to color V. The Graph Motif (or GM) problem takes as input G, a multiset M of colors built from C, and asks whether there is a subset S subseteq V such that (i) G[S] is connected and (ii) the multiset of colors obtained from S equals M. The Colorful Graph Motif problem (or CGM) is a constrained version of GM in which M=C, and the List-Colored Graph Motif problem (or LGM) is the extension of GM in which each vertex v of V may choose its color from a list L(v) of colors. We study the three problems GM, CGM and LGM, parameterized by l:=|V|-|M|. In particular, for general graphs, we show that, assuming the strong exponential-time hypothesis, CGM has no (2-epsilon)^l * |V|^{O(1)}-time algorithm, which implies that a previous algorithm, running in O(2^l\cdot |E|) time is optimal. We also prove that LGM is W[1]-hard even if we restrict ourselves to lists of at most two colors. If we constrain the input graph to be a tree, then we show that, in contrast to CGM, GM can be solved in O(4^l *|V|) time but admits no polynomial kernel, while CGM can be solved in O(sqrt{2}^l + |V|) time and admits a polynomial kernel.
Keywords
  • NP-hard problem
  • subgraph problem
  • fixed-parameter algorithm
  • lowerbounds
  • kernelization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Abhimanyu M. Ambalath, Radheshyam Balasundaram, Chintan Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, and M. S. Ramanujan. On the kernelization complexity of colorful motifs. In Proc. of the 5th Int'l Symp. on Parameterized and Exact Computation (IPEC'10), volume 6478 of LNCS, pages 14-25. Springer, 2010. Google Scholar
  2. Nadja Betzler, René van Bevern, Christian Komusiewicz, Michael R. Fellows, and Rolf Niedermeier. Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM Trans. on Computational Biology and Bioinformatics, 8(5):1296-1308, 2011. Google Scholar
  3. Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Constrained multilinear detection and generalized graph motifs. Algorithmica, 74(2):947-967, 2016. Google Scholar
  4. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1):277-305, 2014. Google Scholar
  5. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science, 412(35):4570-4578, 2011. Google Scholar
  6. Edouard Bonnet and Florian Sikora. The graph motif problem parameterized by the structure of the input graph. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC'15), volume 43 of Leibniz International Proceedings in Informatics (LIPIcs), pages 319-330, 2015. Google Scholar
  7. Sharon Bruckner, Falk Hüffner, Richard M. Karp, Ron Shamir, and Roded Sharan. Topology-free querying of protein interaction networks. Journal of Computational Biology, 17(3):237-252, 2010. URL: http://dx.doi.org/10.1089/cmb.2009.0170.
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC'10), pages 251-260. ACM, 2010. Google Scholar
  10. Michael R. Fellows, Guillaume Fertin, Danny Hermelin, and Stéphane Vialette. Upper and lower bounds for finding connected motifs in vertex-colored graphs. Journal of Computer and System Sciences, 77(4):799-811, 2011. Google Scholar
  11. Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53-61, 2009. Google Scholar
  12. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer-Verlag, 1st edition, 2010. Google Scholar
  13. Sepp Hartung, Christian Komusiewicz, and André Nichterlein. Parameterized algorithmics and computational experiments for finding 2-clubs. Journal of Graph Algorithms and Applications, 19(1):155-190, 2015. Google Scholar
  14. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  15. Vincent Lacroix, Cristina G. Fernandes, and Marie-France Sagot. Motif search in graphs: Application to metabolic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):360-368, 2006. Google Scholar
  16. Rolf Niedermeier and Peter Rossmanith. A general method to speed up fixed-parameter-tractable algorithms. Information Processing Letters, 73(3-4):125-129, 2000. Google Scholar
  17. Ron Y. Pinter, Hadas Shachnai, and Meirav Zehavi. Deterministic parameterized algorithms for the graph motif problem. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS'14), volume 8635 of Lecture Notes in Computer Science, pages 589-600. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8.
  18. Ron Y. Pinter and Meirav Zehavi. Algorithms for topology-free and alignment network queries. J. of Discrete Algorithms, 27:29-53, 2014. URL: http://dx.doi.org/10.1016/j.jda.2014.03.002.
  19. Imran Rauf, Florian Rasche, François Nicolas, and Sebastian Böcker. Finding maximum colorful subtrees in practice. Journal of Computational Biology, 20(4):311-321, 2013. Google Scholar
  20. Roded Sharan and Trey Ideker. Modeling cellular machinery through biological network comparison. Nature Biotechnology, 24(4):427-433, 2006. Google Scholar
  21. Florian Sikora. An (almost complete) state of the art around the graph motif problem. Technical report, LIGM Université Paris-Est, March 2012. URL: http://www.lamsade.dauphine.fr/~sikora/pub/GraphMotif-Resume.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail