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 tclaw-free graphs, where tclaw is the graph consisting of t disjoint copies of the claw. The solution for tclaw-free graphs was obtained by generalizing Farber's approach to solve the problem for tK2-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+tclaw-free graphs, generalizing both fork-free graphs and tclaw-free graphs, and in the class of P5+tclaw-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 P5+tP3-free graphs in polynomial time for any natural d and t, extending some of the previously known solutions.
Independent sets of maximum weight beyond claw-free graphs and related problems
Mosca, Raffaele
2025-01-01
Abstract
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 tclaw-free graphs, where tclaw is the graph consisting of t disjoint copies of the claw. The solution for tclaw-free graphs was obtained by generalizing Farber's approach to solve the problem for tK2-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+tclaw-free graphs, generalizing both fork-free graphs and tclaw-free graphs, and in the class of P5+tclaw-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 P5+tP3-free graphs in polynomial time for any natural d and t, extending some of the previously known solutions.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
