Document Open Access Logo

The Independent Set Problem Is FPT for Even-Hole-Free Graphs

Authors Edin Husić, Stéphan Thomassé, Nicolas Trotignon

PDF

File

Thumbnail PDF
PDF
LIPIcs.IPEC.2019.21.pdf
  • Filesize: 0.58 MB
  • 12 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
Keywords
  • independent set
  • FPT algorithm
  • even-hole-free graph
  • augmenting graph

Metrics

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

Abstract

The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theorem. However, the complexity of computing a maximum independent set (MIS) is a long-standing open question in even-hole-free graphs. From the hardness point of view, MIS is W[1]-hard in the class of graphs without induced 4-cycle (when parameterized by the solution size). Halfway of these, we show in this paper that MIS is FPT when parameterized by the solution size in the class of even-hole-free graphs. The main idea is to apply twice the well-known technique of augmenting graphs to extend some initial independent set.

Cite As Get BibTex

Edin Husić, Stéphan Thomassé, and Nicolas Trotignon. The Independent Set Problem Is FPT for Even-Hole-Free Graphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2019.21

Author Details

Edin Husić
  • Department of Mathematics, LSE, Houghton Street, London, WC2A 2AE, United Kingdom
Stéphan Thomassé
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
  • Institut Universitaire de France, Paris, France
Nicolas Trotignon
  • Univ Lyon, ENS de Lyon, Université Claude Bernard Lyon 1, CNRS, LIP, F-69342, Lyon Cedex 07, France

Funding

The second and third named authors are partially 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).

Acknowledgements

The majority of paper was prepared while the first named author was a student at ENS de Lyon.

References

  1. VE 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. Google Scholar
  2. Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs. In Christophe Paul and Michal Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), volume 115 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:13, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  3. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165-177, 1990. Google Scholar
  4. Rodney G. Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science & Business Media, 2012. Google Scholar
  5. Michael R Garey and David S Johnson. Computers and intractability, volume 29. wh freeman New York, 2002. Google Scholar
  6. Fănică Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM Journal on Computing, 1(2):180-187, 1972. Google Scholar
  7. 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. Google Scholar
  8. John E. Hopcroft and Richard M. Karp. An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput., 2(4):225-231, 1973. Google Scholar
  9. George J Minty. On maximal independent sets of vertices in claw-free graphs. Journal of Combinatorial Theory, Series B, 28(3):284-304, 1980. Google Scholar
  10. Svatopluk Poljak. A note on stable sets and colorings of graphs. Commentationes Mathematicae Universitatis Carolinae, 15(2):307-309, 1974. Google Scholar
  11. Najiba Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile. Discrete Mathematics, 29(1):53-76, 1980. Google Scholar
  12. Kristina Vušković. Even-hole-free graphs: a survey. Applicable Analysis and Discrete Mathematics, pages 219-240, 2010. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact