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 Pk-free graphs, k≥7, is an open problem. In [7], it is shown that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This result is extended by Maffray and Pastor [22] showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for (S1,2,3,bull)-free graphs. In this paper, using a similar approach as in [7], we show that MWIS can be solved in polynomial time for (S1,2,4,triangle)-free graphs which generalizes the result for (P7,triangle)-free graphs.
Maximum weight independent sets for (S1,2,4,triangle)-free graphs in polynomial time
Mosca R.
2021-01-01
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 Pk-free graphs, k≥7, is an open problem. In [7], it is shown that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This result is extended by Maffray and Pastor [22] showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for (S1,2,3,bull)-free graphs. In this paper, using a similar approach as in [7], we show that MWIS can be solved in polynomial time for (S1,2,4,triangle)-free graphs which generalizes the result for (P7,triangle)-free graphs.File | Dimensione | Formato | |
---|---|---|---|
1806.09472.pdf
accesso aperto
Descrizione: Submitted Article
Tipologia:
Documento in Pre-print
Dimensione
241.95 kB
Formato
Adobe PDF
|
241.95 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S030439752100308X-main.pdf
Solo gestori archivio
Descrizione: Article
Tipologia:
PDF editoriale
Dimensione
493.29 kB
Formato
Adobe PDF
|
493.29 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.