Maximum Weight Independent Sets for ($S_{1,2,4}$,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 for $P_k$-free graphs, $k \ge 7$, is an open problem. In \cite{BraMos2018}, it is shown that MWIS can be solved in polynomial time for ($P_7$,triangle)-free graphs. This result is extended by Maffray and Pastor \cite{MafPas2016} showing that MWIS can be solved in polynomial time for ($P_7$,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for ($S_{1,2,3}$,bull)-free graphs. In this paper, using a similar approach as in \cite{BraMos2018}, we show that MWIS can be solved in polynomial time for ($S_{1,2,4}$,triangle)-free graphs which generalizes the result for ($P_7$,triangle)-free graphs.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Maximum weight stable set in (, bull)-free graphs and (, bull)-free graphsDiscrete Mathematics, 2018
- Maximum Weight Independent Sets for (,triangle)-free graphs in polynomial timeDiscrete Applied Mathematics, 2018
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graphJournal of Discrete Algorithms, 2008
- On easy and hard hereditary classes of graphs with respect to the independent set problemDiscrete Applied Mathematics, 2003
- A note on triangle-free and bipartite graphsDiscrete Mathematics, 2002
- Modular decomposition and transitive orientationDiscrete Mathematics, 1999
- On the closure of triangle-free graphs under substitutionInformation Processing Letters, 1990
- Paw-free graphsInformation Processing Letters, 1988
- Substitution Decomposition for Discrete Structures and Connections with Combinatorial Optimization1984
- On maximal independent sets of vertices in claw-free graphsJournal of Combinatorial Theory, Series B, 1980