Document Open Access Logo

Parameterized Complexity of Independent Set in H-Free Graphs

Authors Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.17.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Édouard Bonnet
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Nicolas Bousquet
  • CNRS, G-SCOP laboratory, Grenoble-INP, France
Pierre Charbit
  • Université Paris Diderot, IRIF, France
Stéphan Thomassé
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France, Institut Universitaire de France
Rémi Watrigant
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

Funding

É. B. is supported by the LABEX MILYON (ANR-10- LABX-0070) of Université de Lyon, within the program "Investissements d’Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). N. B. and P. C. are supported by the ANR Project DISTANCIA (ANR-17-CE40-0015) operated by the French National Research Agency (ANR).

Cite As Get BibTex

Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.17

Abstract

In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs H, we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and W[1]-hard cases. We first show that MIS remains W[1]-hard in graphs forbidding simultaneously K_{1, 4}, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning C_4-free graphs. Then we extend the polynomial algorithm of Alekseev when H is a disjoint union of edges to an FPT algorithm when H is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of iterative expansion accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called iterative compression. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs H.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Parameterized Algorithms
  • Independent Set
  • H-Free Graphs

Metrics

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

Related Versions

References

  1. V. Alekseev. The Effect of Local Constraints on the Complexity of Determination of the Graph Independence Number. Combinatorial-Algebraic Methods in Applied Mathematics, pages 3-13, 1982. in Russian. Google Scholar
  2. V. E. Alekseev. On the number of maximal independent sets in graphs from hereditary classes. Combinatorial-Algebraic Methods in Discrete Optimization, pages 5-8, 1991. (In Russian). Google Scholar
  3. G. Bacsó, D. Lokshtanov, D. Marx, M. Pilipczuk, Z. Tuza, and E. Jan van Leeuwen. Subexponential-time Algorithms for Maximum Independent Set in dollarP_tdollar-free and Broom-free Graphs. CoRR, abs/1804.04077, 2018. Google Scholar
  4. É. Bonnet, N. Bousquet, P. Charbit, S. Thomassé, and R. Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs. CoRR, 2018. URL: http://arxiv.org/abs/1810.04620.
  5. J. Chen, Y. L., S. Lu, S. S., and F. Zhang. Iterative Expansion and Color Coding: An Improved Algorithm for 3D-Matching. ACM Trans. Algorithms, 8(1):6:1-6:22, 2012. Google Scholar
  6. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  7. K. Dabrowski. Structural Solutions to Maximum Independent Set and Related Problems. PhD thesis, University of Warwick, 2012. Google Scholar
  8. K. Dabrowski, V. V. Lozin, H. Müller, and D. Rautenbach. Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. J. Discrete Algorithms, 14:207-213, 2012. Google Scholar
  9. R. Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  10. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  11. H. Perret du Cray and I. Sau. Improved FPT algorithms for weighted independent set in bull-free graphs. Discrete Mathematics, 341(2):451-462, 2018. Google Scholar
  12. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  13. A. Grzesik, T. Klimosova, M. Pilipczuk, and M. Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs. CoRR, abs/1707.05491, 2017. Google Scholar
  14. D. Hermelin, M. Mnich, and E. J. van Leeuwen. Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs. Algorithmica, 70(3):513-560, 2014. Google Scholar
  15. T. Karthick. Independent Sets in Some Classes of S_i,j,k-free Graphs. J. Comb. Optim., 34(2):612-630, August 2017. Google Scholar
  16. T. Karthick and F. Maffray. Maximum weight independent sets in classes related to claw-free graphs. Discrete Applied Mathematics, 216:233-239, 2017. Google Scholar
  17. D. Lokshtanov, M. Vatshelle, and Y. Villanger. Independent Set in P_5-Free Graphs in Polynomial Time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 570-581, 2014. Google Scholar
  18. B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. Operations Research Letters, 32(4):299-301, 2004. Google Scholar
  19. S. Thomassé, N. Trotignon, and K. Vuskovic. A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. Algorithmica, 77(3):619-641, 2017. Google Scholar
  20. D. Zuckerman. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3(1):103-128, 2007. 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