Maximum Weight Independent Sets for ($P_7$,Triangle)-Free Graphs in Polynomial Time
Preprint
Abstract
The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity was an open problem for $P_k$-free graphs, $k \ge 5$. Recently, Lokshtanov, Vatshelle, and Villanger proved that MWIS can be solved in polynomial time for $P_5$-free graphs, and Lokshtanov, Pilipczuk, and van Leeuwen proved that MWIS can be solved in quasi-polynomial time for $P_6$-free graphs. It still remains an open problem whether MWIS can be solved in polynomial time for $P_k$-free graphs, $k \geq 6$ or in quasi-polynomial time for $P_k$-free graphs, $k \geq 7$. Some characterizations of $P_k$-free graphs and some progress are known in the literature but so far did not solve the problem. In this paper, we show that MWIS can be solved in polynomial time for ($P_7$,triangle)-free graphs. This extends the corresponding result for ($P_6$,triangle)-free graphs and may provide some progress in the study of MWIS for $P_7$-free graphs.
Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- A New Characterization of $P_k$ P k -Free GraphsAlgorithmica, 2015
- On the diameter of i‐center in a graph without long induced pathsJournal of Graph Theory, 1999
- Dominating subgraphs in graphs with some forbidden structuresDiscrete Mathematics, 1994
- Dominating cliques in P5-free graphsPeriodica Mathematica Hungarica, 1990
- A characterization of graphs without long induced pathsJournal of Graph Theory, 1990
- On the closure of triangle-free graphs under substitutionInformation Processing Letters, 1990
- Paw-free graphsInformation Processing Letters, 1988
- Clustering and domination in perfect graphsDiscrete Applied Mathematics, 1984
- NP-completeness of some generalizations of the maximum matching problemInformation Processing Letters, 1982
- On maximal independent sets of vertices in claw-free graphsJournal of Combinatorial Theory, Series B, 1980