2026-07-23T04:48:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11482 2024-03-06T10:48:08Z ddc:004 open_access

The Independent Set Problem Is FPT for Even-Hole-Free Graphs Husić, Edin Thomassé, Stéphan Trotignon, Nicolas independent set FPT algorithm even-hole-free graph augmenting graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Edin Husić and Stéphan Thomassé and Nicolas Trotignon 2019 Is Part Of LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2019.21 urn:nbn:de:0030-drops-114826 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.21 eng https://creativecommons.org/licenses/by/3.0/legalcode