The maximum weight independent set problem (WIS), which is known to be generally NP-hard, admits polynomial-time solutions when restricted to graphs in some special classes. In particular, due to the celebrated Edmonds' matching algorithm , WIS is solvable in polynomial time in the class of line graphs. This solution was extended to claw-free graphs and then further to fork-free graphs and to t claw-free graphs, where t claw is the graph consisting of t disjoint copies of the claw. The solution for t claw-free graphs was obtained by generalizing Farber's approach to solve the problem for t K 2 -free graphs. In the present paper, we elaborate this approach further to develop a polynomial-time algorithm to solve the problem in the class of fork+ t claw-free graphs, generalizing both fork-free graphs and t claw-free graphs, and in the class of P 5 + t claw-free graphs. We then apply the latter result to solve the more general problem of finding a d -regular induced subgraph of maximum weight in the class of P 5 + t P 3 -free graphs in polynomial time for any natural d and t , extending some of the previously known solutions.

Let G=(V,E) be a finite undirected graph. An edge set E′⊆E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G; this problem is also known as the Efficient Edge Domination problem; it is the Efficient Domination problem for line graphs. The DIM problem is NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but is solvable in polynomial time for P9-free graphs [and in linear time for P7-free graphs] as well as for S1,2,4-free, for S2,2,2-free, and for S2,2,3-free graphs. In this paper, combining two distinct approaches, we solve it in polynomial time for P10-free graphs and introduce a partial result for the general case.

In a finite undirected graph $G=(V,E)$, a vertex $v \in V$ dominates itself and its neighbors in $G$. A vertex set $D \subseteq V$ is an efficient dominating set (e.d.s. for short) of $G$ if every $v \in V$ is dominated in $G$ by exactly one vertex of $D$. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in $G$, is known to be NP-complete for $P_7$-free graphs and solvable in polynomial time for $P_5$-free graphs. The $P_6$-free case was the last open question for the complexity of ED on $F$-free graphs. Recently, Lokshtanov, Pilipczuk, and van Leeuwen showed that weighted ED is solvable in polynomial time for $P_6$-free graphs, based on their quasi-polynomial algorithm for the Maximum Weight Independent Set problem for $P_6$-free graphs. Independently, by a direct approach which is simpler and faster, we found an ${\cal O}(n^5 m)$ time solution for weighted ED on $P_6$-free graphs. Moreover, we show that weighted ED is solvable in linear time for $P_5$-free graphs which solves another open question for the complexity of (weighted) ED. The result for $P_5$-free graphs is based on modular decomposition.

We present the first polynomial-time algorithm to solve the maximum weight independent set problem for apple-free graphs, which is a common generalization of several important classes where the problem can be solved efficiently, such as claw-free graphs, chordal graphs, and cographs. Our solution is based on a combination of two algorithmic techniques (modular decomposition and decomposition by clique separators) and a deep combinatorial analysis of the structure of apple-free graphs. Our algorithm is robust in the sense that it does not require the input graph G to be apple-free; the algorithm either finds an independent set of maximum weight in G or reports that G is not apple-free.