Maximum Weight Independent Set in lClaw-Free Graphs in Polynomial Time

The Maximum Weight Independent Set (MWIS) problem is a well-known NP-hard problem. For graphs $G_1, G_2$, $G_1+G_2$ denotes the disjoint union of $G_1$ and $G_2$, and for a constant $l \ge 2$, $lG$ denotes the disjoint union of $l$ copies of $G$. A {\em claw} has vertices $a,b,c,d$, and edges $ab,ac,ad$. MWIS can be solved for claw-free graphs in polynomial time; the first two polynomial time algorithms were introduced in 1980 by \cite{Minty1980,Sbihi1980}, then revisited by \cite{NakTam2001}, and recently improved by \cite{FaeOriSta2011,FaeOriSta2014}, and by \cite{NobSas2011,NobSas2015} with the best known time bound in \cite{NobSas2015}. Furthermore MWIS can be solved for the following extensions of claw-free graphs in polynomial time: fork-free graphs \cite{LozMil2008}, $K_2$+claw-free graphs \cite{LozMos2005}, and apple-free graphs \cite{BraLozMos2010,BraKleLozMos2008}. This manuscript shows that for any constant $l$, MWIS can be solved for $l$claw-free graphs in polynomial time. Our approach is based on Farber's approach showing that every $2K_2$-free graph has ${\cal O}(n^2)$ maximal independent sets \cite{Farbe1989}, which directly leads to a polynomial time algorithm for MWIS on $2K_2$-free graphs by dynamic programming. Solving MWIS for $l$claw-free graphs in polynomial time extends known results for claw-free graphs, for $lK_2$-free graphs for any constant $l$ \cite{Aleks1991,FarHujTuz1993,Prisn1995,TsuIdeAriShi1977}, for $K_2$+claw-free graphs, for $2P_3$-free graphs \cite{LozMos2012}, and solves the open questions for $2K_2+P_3$-free graphs and for $P_3$+claw-free graphs being two of the minimal graph classes, defined by forbidding one induced subgraph, for which the complexity of MWIS was an open problem.

No reviews yet.

No comments yet.