The Maximum Weight Stable Set Problem (MWS) is a well-known NP-hard problem. A popular way to study MWS is to detect graph classes for which MWS can be solved in polynomial time. In this context some ...decomposition approaches have been introduced in the literature, in particular decomposition by homogeneous sets and decomposition by clique separators, which had several applications in the literature. Brandstädt and Hoàng (2007) 6 showed how to combine such two decomposition approaches and stated the following result: If the MWS problem can be solved in polynomial time for every subgraph of a graph G which has no homogeneous set and has no clique separators then so can the problem for G. This result, namely Corollary 9 of 6, was used in various papers.
Unfortunately, it was stated in a successive paper by Brandstädt and Giakoumakis (2015) 5 that “Actually, 6 does not give a proof for this, and it seems that Corollary 9 of 6 promises too much; later attempts for proving it failed, and thus, it is unproven and its use has to be avoided.”
This manuscript introduces a proof of Corollary 9 of 6. Furthermore a third decomposition approach, namely decomposition by anti-neighborhoods of vertices, is combined together with such two decomposition approaches. Then the various papers in which Corollary 9 of 6 was used would be fixed.
For a finite, simple, undirected graph G with a vertex weight function, the Maximum Weight Independent Set (MWIS) problem asks for an independent vertex set of G with maximum weight. MWIS is a ...well-known NP-hard problem of fundamental importance. For claw-free graphs, MWIS can be solved in polynomial time—in 1980, the first two such algorithms were independently found by Minty for MWIS and by Sbihi for the unweighted case. For a constant ℓ≥2, let ℓG denote the disjoint union of ℓ copies of G.
In this paper, using a dynamic programming approach (inspired by Farber’s result about MWIS for 2K2-free graphs), we show that for any fixed ℓ, MWIS can be solved in polynomial time for ℓclaw-free graphs. This solves the open cases for MWIS on (P3+claw)-free graphs and on (2K2+claw)-free graphs and extends known results for claw-free graphs, ℓK2-free graphs, (K2+claw)-free graphs, and ℓP3-free graphs.
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.
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. For a long time, its complexity was an open problem for Pk-free graphs, k≥5.
Recently, Lokshtanov et al. (2014) proved that MWIS can be solved in polynomial time for P5-free graphs, Lokshtanov et al. (2015) proved that MWIS can be solved in quasi-polynomial time for P6-free graphs, and Bacsó et al. (2016), and independently, Brause (2017) extended this to Pk-free graphs for every fixed k. Then very recently, Grzesik et al. (2017) showed that MWIS can be solved in polynomial time for P6-free graphs. It still remains an open problem for Pk-free graphs, k≥7.
In this paper, we show that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This extends the corresponding result for (P6,triangle)-free graphs and may provide some progress in the study of MWIS for P7-free graphs such as the recent result by Maffray and Pastor (2016) showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs.
Graph decompositions play a crucial role in structural graph theory and in designing efficient graph algorithms. Among them, clique separator decomposition (a decomposition tree of the graph whose ...leaves have no clique separator (so-called atoms)) used by Tarjan for solving various optimization problems recently received much attention. In this note, we first derive the atomic structure of two subclasses of P5-free graphs, where P5 is a chordless path on five vertices. These results enable us to provide efficient solutions for the Maximum Weight Independent Set problem in these classes of graphs.
In Brandstädt and Giakoumakis 2, we reduce the Maximum Weight Independent Set (MWIS) problem on hole- and co-chair-free graphs to a corresponding problem on prime atoms. Here we refine these results ...by investigating atoms of prime graphs (avoiding the requirement that the graphs are prime and atoms) and also observe that the MWIS problem is solvable in polynomial time on (odd-hole, co-chair)-free graphs.
•The Maximum Weight Independent Set (MWIS) problem on graphs is a frequently studied problem.•Clique separators and modular decomposition are powerful tools for solving this problem on various graph classes.•We combine these tools for solving MWIS efficiently on odd-hole- and co-chair-free graphs by showing that atoms of prime odd-hole- and co-chair-free graphs are nearly perfect and atoms of prime hole- and co-chair-free graphs are nearly weakly chordal.
The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for ...hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n3)-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n4)-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs.
The Maximum Weight Independent Set (MWIS) Problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated problem on ...graphs, it is well known to be NP-complete and hard to approximate. Several graph classes for which MWIS can be solved in polynomial time have been introduced in the literature. This note shows that MWIS can be solved in polynomial time for (P6,co-banner)-free graphs – where a P6 is an induced path of 6 vertices and a co-banner is a graph with vertices a,b,c,d,e and edges ab,bc,cd,ce,de – so extending different analogous known results for other graph classes, namely, P4-free, 2K2-free, (P5,co-banner)-free, and (P6,triangle)-free graphs. The solution algorithm is based on an idea/algorithm of Farber (1989) 10, leading to a dynamic programming approach for MWIS, and needs none of the aforementioned known results as sub-procedure.
► The note deals with the Maximum Weight Independent Set (MWIS) Problem. ► It shows that MWIS can be efficiently solved for (P6,co-banner)-free graphs. ► It extends different analogous known results for other graph classes. ► It needs none of the aforementioned known results as sub-procedure. ► It is based on a previous idea of Martin Farber.
The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most ...important problems on graphs, it is well known to be
NP
-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying a combination of clique separator and modular decomposition, we obtain a polynomial time solution of MWIS for hole- and co-chair-free graphs (the co-chair consists of five vertices four of which form a clique minus one edge – a
diamond – and the fifth has degree one and is adjacent to one of the degree two vertices of the diamond).
► The Maximum Weight Independent Set (MWIS) problem on graphs is a frequently studied problem. ► Clique separators and modular decomposition are powerful tools for solving this problem on various graph classes. ► We combine these tools for solving MWIS efficiently on hole- and co-chair-free graphs. ► In particular, we show that prime atoms of those graphs are nearly weakly chordal.
PDF
