Document Open Access Logo

A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width

Authors Lars Jaffke, O-joung Kwon, Jan Arne Telle

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.42.pdf
  • Filesize: 0.63 MB
  • 14 pages

Document Identifiers

Author Details

Lars Jaffke
O-joung Kwon
Jan Arne Telle

Cite As Get BibTex

Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.42

Abstract

We give a first polynomial-time algorithm for (Weighted) Feedback Vertex Set on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an n^{O(w)}-time algorithm that solves Feedback Vertex Set. This provides a unified algorithm for many well-known classes, such as Interval graphs and Permutation graphs, and furthermore, it gives the first polynomial-time algorithms for other classes of bounded mim-width, such as Circular Permutation and Circular k-Trapezoid graphs for fixed k. In all these classes the decomposition is computable in polynomial time, as shown by Belmonte and Vatshelle [Theor. Comput. Sci. 2013].
We show that powers of graphs of tree-width w-1 or path-width w and powers of graphs of clique-width w have mim-width at most w. These results extensively provide new classes of bounded mim-width. We prove a slight strengthening of the first statement which implies that, surprisingly, Leaf Power graphs which are of importance in the field of phylogenetic studies have mim-width at most 1. Given a tree decomposition of width w-1, a path decomposition of width w, or a clique-width w-expression of a graph G, one can for any value of k find a mim-width decomposition of its k-power in polynomial time, and apply our algorithm to solve Feedback Vertex Set on the k-power in time n^{O(w)}.
In contrast to Feedback Vertex Set, we show that Hamiltonian Cycle is NP-complete even on graphs of linear mim-width 1, which further hints at the expressive power of the mim-width parameter.

Subject Classification

Keywords
  • graph width parameters
  • graph classes
  • feedback vertex set
  • leaf powers

Metrics

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

References

  1. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theoretical Computer Science, 511:54-65, 2013. Google Scholar
  2. Daniel Berend and Tamir Tassa. Improved bounds on bell numbers and on moments of sums of random variables. Probability and Mathematical Statistics, 30(2):185-205, 2010. Google Scholar
  3. Benjamin Bergougnoux, Mamadou Moustapha Kanté, and O-Joung Kwon. An optimal XP algorithm for hamiltonian cycle on graphs of bounded clique-width. In Proceedings 15th International Symposium on Algorithms and Data Structures (WADS), pages 121-132, Cham, 2017. Springer. Google Scholar
  4. Hans L. Bodlaender. On disjoint cycles. International Journal of Foundations of Computer Science, 5(1):59-68, 1994. Google Scholar
  5. Andreas Brandstädt. On leaf powers. Technical report, University of Rostock, 2010. Google Scholar
  6. Binh-Minh Bui-Xuan, Ondřej Suchỳ, Jan Arne Telle, and Martin Vatshelle. Feedback vertex set on graphs of low clique-width. European Journal of Combinatorics, 34(3):666-679, 2013. Google Scholar
  7. Tiziana Calamoneri and Blerina Sinaimeri. Pairwise compatibility graphs: A survey. SIAM Review, 58(3):445-460, 2016. URL: http://dx.doi.org/10.1137/140978053.
  8. Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, and Yngve Villanger. Improved algorithms for feedback vertex set problems. Journal of Computer and System Sciences, 74(7):1188-1198, 2008. Google Scholar
  9. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Joham M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 150-159. IEEE, 2011. Google Scholar
  10. Frank K. H. A. Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, and Kim Stevens. An 𝒪(2^O(k)n³) FPT algorithm for the undirected feedback vertex set problem. In Proceedings 11th International Computing and Combinatorics Conference (COCOON), pages 859-869. Springer, 2005. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24(4):873-921, 1995. Google Scholar
  12. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer, 1999. Google Scholar
  13. Wolfgang Espelage, Frank Gurski, and Egon Wanke. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In Proceedings 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 117-128. Springer, 2001. Google Scholar
  14. Paola Festa, Panos M. Pardalos, and Mauricio G. C. Resende. Feedback set problems. In Handbook of Combinatorial Optimization, pages 209-258. Springer, 1999. Google Scholar
  15. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM Journal on Computing, 39(5):1941-1956, 2010. Google Scholar
  16. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM Journal on Computing, 43(5):1541-1563, 2014. Google Scholar
  17. Martin Charles Golumbic and Udi Rotics. On the clique-width of some perfect graph classes. International Journal of Foundations of Computer Science, 11(03):423-443, 2000. Google Scholar
  18. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. Journal of Computer and System Sciences, 72(8):1386-1396, 2006. Google Scholar
  19. Pinar Heggernes, Daniel Meister, Charis Papadopoulos, and Udi Rotics. Clique-width of path powers. Discrete Applied Mathematics, 205:62-72, 2016. Google Scholar
  20. Alon Itai, Christos H. Papadimitriou, and Jayme Luiz Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676-686, 1982. Google Scholar
  21. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A note on the complexity of feedback vertex set parameterized by mim-width. arXiv preprints, 2017. arXiv:1711.05157. Google Scholar
  22. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width. In Proceedings 12th International Symposium on Parameterized and Exact Computation (IPEC), pages 21:1-21:12, 2017. arXiv:1708.04536. Google Scholar
  23. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width. arXiv preprints, 2017. arXiv:1710.07148. Google Scholar
  24. Bart M. P. Jansen, Venkatesh Raman, and Martin Vatshelle. Parameter ecology for feedback vertex set. Tsinghua Science and Technology, 19(4):387-409, 2014. Google Scholar
  25. Iyad Kanj, Michael Pelsmajer, and Marcus Schaefer. Parameterized algorithms for feedback vertex set. In Proceedings 1st International Workshop on Parameterized and Exact Computation (IWPEC), pages 235-247. Springer, 2004. Google Scholar
  26. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103. Springer, 1972. Google Scholar
  27. Dieter Kratsch, Haiko Müller, and Ioan Todinca. Feedback vertex set on at-free graphs. Discrete Applied Mathematics, 156(10):1936-1947, 2008. Google Scholar
  28. Manuel Lafond. On strongly chordal graph that are not leaf powers. arXiv preprints, 2017. arXiv:1703.08018. Google Scholar
  29. Stefan Mengel. Lower bounds on the mim-width of some perfect graph classes. arXiv preprints, 2016. arXiv:1608.01542, to appear in Discrete Applied Mathematics. Google Scholar
  30. Ragnar Nevries and Christian Rosenke. Towards a characterization of leaf powers by clique arrangements. Graphs and Combinatorics, 32(5):2053-2077, 2016. Google Scholar
  31. B. S. Panda and D. Pradhan. NP-completeness of hamiltonian cycle problem on rooted directed path graphs. arXiv preprints, 2008. arXiv:0809.2443. Google Scholar
  32. Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for undirected feedback vertex set. In Proceedings 13th International Symposium on Algorithms and Computation (ISAAC), pages 241-248. Springer, 2002. Google Scholar
  33. Venkatesh Raman, Saket Saurabh, and C. R. Subramanian. Faster fixed parameter tractable algorithms for finding feedback vertex sets. ACM Transactions on Algorithms, 2(3):403-415, 2006. Google Scholar
  34. Sigve H. Sæther and Martin Vatshelle. Hardness of computing width parameters based on branch decompositions over the vertex set. Theoretical Computer Science, 615:120-125, 2016. Google Scholar
  35. Lorna Stewart and Richard Valenzano. On polygon numbers of circle graphs and distance hereditary graphs. Discrete Applied Mathematics, 2017. in press. URL: http://dx.doi.org/10.1016/j.dam.2017.09.016.
  36. Martin Vatshelle. New Width Parameters of Graphs. PhD thesis, University of Bergen, Norway, 2012. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact