Uniform TitleAlgorithmic developments and complexity results for finding maximum and exact independent sets in graphs
NameMilanic, Martin (author), Lozin, Vadim (chair), Alizadeh, Farid (internal member), Boros, Endre (internal member), Gurvich, Vladimir (internal member), Kahn, Jeffry (internal member), Monnot, Jérôme (outside member), Rutgers University, Graduate School-New Brunswick,
DescriptionWe consider the maximum independent set and maximum weight independent set problems in graphs. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, that is, in graph classes defined by a set F of forbidden induced subgraphs.
We describe a condition on the set F, which guarantees that the maximum independent set problem remains NP-hard in the class of F-free graphs. The same hardness result remains valid even under the additional restriction that the graphs are planar and of maximum degree at most three.
We exhibit several cases where the condition is violated, and the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the maximum independent set problem in:
- two graph classes that properly contain claw-free graphs (thus generalizing the classical result for claw-free graphs);
- various subclasses of planar and more general graphs;
- weighted graphs in certain subclasses of graphs of bounded vertex degree.
Our algorithms are based on various approaches. In particular, we develop an extension of the method of finding augmenting graphs. We also make extensive use of some other well-known graph decompositions.
We also introduce and study the exact version of the problem, where, instead of finding an independent set of maximum weight, the goal is to find an independent set of given weight. Determining the computational complexity of this problem for line graphs, or for line graphs of bipartite graphs would resolve long standing open problems. Here, we show that:
- The exact weighted independent set problem is strongly NP-complete for cubic bipartite graphs.
- The problem is solvable in pseudo polynomial time for any of the following graph classes:
mK2-free graphs, interval graphs and their generalizations k-thin graphs, circle graphs, chordal graphs, AT-free graphs, (claw, net)-free graphs, distance-hereditary graphs, and graphs of bounded tree- or clique-width.
Finally, we show how modular decomposition can be applied to the exact weighted independent set problem. As a corollary, we obtain pseudo-polynomial solutions for the problem in certain subclasses of P5-free and fork-free graphs.
Note[bibliography] Includes bibliographical references (p. 132-138).
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.