Document Open Access Logo

When Maximum Stable Set Can Be Solved in FPT Time

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

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.49.pdf
  • Filesize: 0.59 MB
  • 22 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
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

Cite AsGet BibTex

Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, and Rémi Watrigant. When Maximum Stable Set Can Be Solved in FPT Time. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.49

Abstract

Maximum Independent Set (MIS for short) is in general graphs the paradigmatic W[1]-hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restricted to structured graph classes such as, for instance, perfect graphs (which includes bipartite graphs, chordal graphs, co-graphs, etc.) or claw-free graphs. In this paper, we introduce some variants of co-graphs with parameterized noise, that is, graphs that can be made into disjoint unions or complete sums by the removal of a certain number of vertices and the addition/deletion of a certain number of edges per incident vertex, both controlled by the parameter. We give a series of FPT Turing-reductions on these classes and use them to make some progress on the parameterized complexity of MIS in H-free graphs. We show that for every fixed t >=slant 1, MIS is FPT in P(1,t,t,t)-free graphs, where P(1,t,t,t) is the graph obtained by substituting all the vertices of a four-vertex path but one end of the path by cliques of size t. We also provide randomized FPT algorithms in dart-free graphs and in cricket-free graphs. This settles the FPT/W[1]-hard dichotomy for five-vertex graphs H.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • 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. Vladimir E. 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. Vladimir E. Alekseev. Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Applied Mathematics, 135(1-3):3-16, 2004. URL: https://doi.org/10.1016/S0166-218X(02)00290-1.
  3. Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan van Leeuwen. Subexponential-Time Algorithms for Maximum Independent Set in P_t-Free and Broom-Free Graphs. Algorithmica, 81(2):421-438, 2019. URL: https://doi.org/10.1007/s00453-018-0479-5.
  4. É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, August 20-24, 2018, Helsinki, Finland, pages 17:1-17:13, 2018. URL: https://doi.org/10.4230/LIPIcs.IPEC.2018.17.
  5. Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs. CoRR, abs/1810.04620, 2018. URL: http://arxiv.org/abs/1810.04620.
  6. Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, and Rémi Watrigant. When Maximum Stable Set can be solved in FPT time. CoRR, abs/1909.08426, 2019. URL: http://arxiv.org/abs/1909.08426.
  7. Andreas Brandstädt and Raffaele Mosca. Maximum weight independent set for 𝓁claw-free graphs in polynomial time. Discrete Applied Mathematics, 237:57-64, 2018. URL: https://doi.org/10.1016/j.dam.2017.11.029.
  8. Andreas Brandstädt and Raffaele Mosca. Maximum Weight Independent Sets for (P₇, triangle)-free graphs in polynomial time. Discrete Applied Mathematics, 236:57-65, 2018. URL: https://doi.org/10.1016/j.dam.2017.10.003.
  9. Andreas Brandstädt and Raffaele Mosca. Maximum Weight Independent Sets for (S_1,2,4, Triangle)-Free Graphs in Polynomial Time. CoRR, abs/1806.09472, 2018. URL: http://arxiv.org/abs/1806.09472.
  10. Jianer Chen, Yang Liu, Songjian Lu, Sing-Hoi Sze, and Fenghui Zhang. Iterative Expansion and Color Coding: An Improved Algorithm for 3D-Matching. ACM Trans. Algorithms, 8(1):6:1-6:22, 2012. Google Scholar
  11. Derek G. Corneil, Yehoshua Perl, and Lorna K. Stewart. A Linear Recognition Algorithm for Cographs. SIAM J. Comput., 14(4):926-934, 1985. Google Scholar
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  13. Konrad Dabrowski. Structural Solutions to Maximum Independent Set and Related Problems. PhD thesis, University of Warwick, 2012. Google Scholar
  14. Konrad Dabrowski, Vadim V. Lozin, Haiko Müller, and Dieter Rautenbach. Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. J. Discrete Algorithms, 14:207-213, 2012. Google Scholar
  15. Konrad K. Dabrowski, Vadim V. Lozin, Dominique de Werra, and Victor Zamaraev. Combinatorics and Algorithms for Augmenting Graphs. Graphs and Combinatorics, 32(4):1339-1352, 2016. URL: https://doi.org/10.1007/s00373-015-1660-0.
  16. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  17. Rod G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  18. Henri Perret du Cray and Ignasi Sau. Improved FPT algorithms for weighted independent set in bull-free graphs. Discrete Mathematics, 341(2):451-462, 2018. Google Scholar
  19. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  20. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding First-Order Properties of Nowhere Dense Graphs. J. ACM, 64(3):17:1-17:32, 2017. URL: https://doi.org/10.1145/3051095.
  21. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. URL: https://doi.org/10.1007/BF02579273.
  22. Andrzej Grzesik, Tereza Klimosova, Marcin Pilipczuk, and Michal Pilipczuk. Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1257-1271, 2019. URL: https://doi.org/10.1137/1.9781611975482.77.
  23. Ararat Harutyunyan, Michael Lampis, Vadim V. Lozin, and Jérôme Monnot. Maximum Independent Sets in Subcubic Graphs: New Results. In Graph-Theoretic Concepts in Computer Science - 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers, pages 40-52, 2019. URL: https://doi.org/10.1007/978-3-030-30786-8_4.
  24. Johan Håstad. Clique is Hard to Approximate Within n^1-ε. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 627-636, 1996. URL: https://doi.org/10.1109/SFCS.1996.548522.
  25. Tamás Kovári, Vera Sós, and Pál Turán. On a problem of K. Zarankiewicz. In Colloquium Mathematicum, volume 1, pages 50-57, 1954. Google Scholar
  26. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, 105:41-72, 2011. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/92.
  27. Daniel Lokshtanov, Marcin Pilipczuk, and Erik Jan van Leeuwen. Independence and Efficient Domination on P₆-free Graphs. ACM Trans. Algorithms, 14(1):3:1-3:30, 2018. URL: https://doi.org/10.1145/3147214.
  28. Daniel Lokshtanov, Martin Vatshelle, and Yngve Villanger. Independent Set in P₅-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
  29. Vadim V. Lozin. From matchings to independent sets. Discrete Applied Mathematics, 231:4-14, 2017. URL: https://doi.org/10.1016/j.dam.2016.04.012.
  30. Vadim V. Lozin and Martin Milanič. Maximum independent sets in graphs of low degree. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 874-880, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283477.
  31. Vadim V. Lozin and Martin Milanič. A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J. Discrete Algorithms, 6(4):595-604, 2008. URL: https://doi.org/10.1016/j.jda.2008.04.001.
  32. Vadim V. Lozin, Jérôme Monnot, and Bernard Ries. On the maximum independent set problem in subclasses of subcubic graphs. J. Discrete Algorithms, 31:104-112, 2015. URL: https://doi.org/10.1016/j.jda.2014.08.005.
  33. Frédéric Maffray and Lucas Pastor. Maximum weight stable set in (P₇, bull)-free graphs and (S_1,2,3, bull)-free graphs. Discrete Mathematics, 341(5):1449-1458, 2018. URL: https://doi.org/10.1016/j.disc.2017.10.004.
  34. Dmitriy S. Malyshev. Classes of subcubic planar graphs for which the independent set problem is polynomially solvable. Journal of Applied and Industrial Mathematics, 7(4):537, 2013. Google Scholar
  35. Dmitriy S. Malyshev and Dmitrii V. Sirotkin. Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs. Journal of Applied and Industrial Mathematics, 11(3):400-414, 2017. Google Scholar
  36. George J. Minty. On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory, Ser. B, 28(3):284-304, 1980. URL: https://doi.org/10.1016/0095-8956(80)90074-X.
  37. Najiba Sbihi. Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile. Discrete Mathematics, 29(1):53-76, 1980. URL: https://doi.org/10.1016/0012-365X(90)90287-R.
  38. Stéphan Thomassé, Nicolas Trotignon, and Kristina Vuskovic. A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. Algorithmica, 77(3):619-641, 2017. Google Scholar
  39. David 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 Imprint Privacy Contact