Independent sets in (P_4+P_4,Triangle)-free graphs
share
The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. Given two graphs G and H, G+H denotes the disjoint union of G and H. This manuscript shows that (i) WIS can be solved for (P_4+P_4, Triangle)-free graphs in polynomial time, where a P_4 is an induced path of four vertices and a Triangle is a cycle of three vertices, and that in particular it turns out that (ii) for every (P_4+P_4, Triangle)-free graph G there is a family S of subsets of V(G) inducing (complete) bipartite subgraphs of G, which contains polynomially many members and can be computed in polynomial time, such that every maximal independent set of G is contained in some member of S. These results seem to be harmonic with respect to other polynomial results for WIS on certain [subclasses of] S_i,j,k-free graphs and to other structure results on [subclasses of] Triangle-free graphs.
READ FULL TEXT