Document Open Access Logo

On the Tractability of Optimization Problems on H-Graphs

Authors Fedor V. Fomin , Petr A. Golovach , Jean-Florent Raymond

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2018.30.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • H-topological intersection graphs
  • parameterized complexity
  • minimal separators
  • boolean-width
  • mim-width

Metrics

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

Abstract

For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. These graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This notion was introduced in the early 1990s by Biro, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of H-graphs by showing that a number of fundamental optimization problems like Clique, Independent Set, or Dominating Set are solvable in polynomial time on H-graphs. We extend and complement these algorithmic findings in several directions.
First we show that for every fixed H, the class of H-graphs is of logarithmically-bounded boolean-width. We also prove that H-graphs are graphs with polynomially many minimal separators. Pipelined with the plethora of known algorithms on graphs of bounded boolean-width and graphs with polynomially many minimal separators, this describes a large class of optimization problems that are solvable in polynomial time on H-graphs.
The most fundamental optimization problems among those solvable in polynomial time on H-graphs are Clique, Independent Set, and Dominating Set. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that Independent Set and Dominating Set are W[1]-hard being parameterized by the size of H plus the size of the solution. On the other hand, we prove that when H is a tree, Dominating Set is fixed-parameter tractable (FPT) parameterized by the size of H. Besides, we show that Clique admits a polynomial kernel parameterized by H and the solution size.

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the Tractability of Optimization Problems on H-Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.30

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
Jean-Florent Raymond
  • Technische Universität Berlin, Germany

Funding

  • Fomin, Fedor V.: Supported by the Research Council of Norway via the project "MULTIVAL".
  • Golovach, Petr A.: Supported by the Research Council of Norway via the project "CLASSIS".
  • Raymond, Jean-Florent: Supported by the European Research Council (ERC) via the ERC consolidator grant DISTRUCT-648527. This research was partly done while the author was supported by the Polish National Science Centre grant PRELUDIUM DEC-2013/11/N/ST6/02706.

References

  1. Rémy Belmonte and Martin Vatshelle. On graph classes with logarithmic boolean-width. arXiv preprint, 2010. URL: https://arxiv.org/abs/1009.0216.
  2. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theoretical Computer Science, 511:54-65, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.01.011.
  3. Anne Berry, Jean-Paul Bordat, and Olivier Cogis. Generating All the Minimal Separators of a Graph, pages 167-172. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999. URL: http://dx.doi.org/10.1007/3-540-46784-X_17.
  4. M. Biró, M. Hujter, and Zs. Tuza. Precoloring extension. I. Interval graphs. Discrete Mathematics, 100(1):267-279, 1992. URL: http://dx.doi.org/10.1016/0012-365X(92)90646-W.
  5. Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing, 31(1):212-232, 2001. URL: http://dx.doi.org/10.1137/S0097539799359683.
  6. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Boolean-width of graphs. Theoretical Computer Science, 412(39):5187-5204, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.05.022.
  7. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoretical Computer Science, 511:66-76, 2013. Exact and Parameterized Computation. URL: http://dx.doi.org/10.1016/j.tcs.2013.01.009.
  8. Steven Chaplick, Martin Töpfer, Jan Voborník, and Peter Zeman. On H-topological intersection graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 167-179. Springer, 2017. URL: https://arxiv.org/abs/1608.02389.
  9. Steven Chaplick and Peter Zeman. Combinatorial problems on H-graphs. In The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17), Electronic Notes in Discrete Mathematics, volume 61, pages 223-229, 2017. https://arxiv.org/abs/1706.00575. URL: http://dx.doi.org/10.1016/j.endm.2017.06.042.
  10. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Dániel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  12. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53-61, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.09.065.
  13. Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on h-graphs. CoRR, abs/1709.09737, 2017. URL: http://arxiv.org/abs/1709.09737.
  14. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM J. Comput., 44(1):54-87, 2015. https://arxiv.org/abs/1309.1559. URL: http://dx.doi.org/10.1137/140964801.
  15. Fănică Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput., 1(2):180-187, 1972. URL: http://dx.doi.org/10.1137/0201013.
  16. Fănică Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combinatorial Theory Ser. B, 16:47-56, 1974. Google Scholar
  17. Martin Charles Golumbic. Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam, second edition, 2004. With a foreword by Claude Berge. Google Scholar
  18. Michel Habib and Juraj Stacho. Polynomial-time algorithm for the leafage of chordal graphs. In Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 290-300. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-04128-0_27.
  19. L. Jaffke, O. Kwon, and J. A. Telle. A note on the complexity of Feedback Vertex Set parameterized by mim-width. arXiv preprint, 2017. https://arxiv.org/abs/1711.05157. URL: http://arxiv.org/abs/1711.05157.
  20. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A note on the complexity of feedback vertex set parameterized by mim-width. CoRR, abs/1711.05157, 2017. URL: http://arxiv.org/abs/1711.05157.
  21. 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. arXiv preprint, 2017. URL: https://arxiv.org/abs/1708.04536.
  22. Ton Kloks, H Bodlaender, Haiko Müller, and Dieter Kratsch. Computing treewidth and minimum fill-in: All you need are the minimal separators. Algorithms - ESA'93, pages 260-271, 1993. Google Scholar
  23. Krzysztof Pietrzak. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci., 67(4):757-771, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00078-3.
  24. Venkatesh Raman and Saket Saurabh. Short cycles make W[1]-hard problems hard: FPT algorithms for W[1]-hard problems in graphs with no short cycles. Algorithmica, 52(2):203-225, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9148-9.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »