Independence Systems and Stable Set Relaxations

This work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/22172Many fundamental combinatorial optimization problems involve the search for subsets of graph elements which satisfy some notion of independence. This thesis develops techniques for optimizing over a class of independence systems and focuses on systems having the vertex set of a finite graph as a ground set. The search for maximum stable sets in a graph offers a well-studied example of such a problem. More generally, for any integer k greater than or equal to one, the maximum co-k-plex problem fits into this framework as well. Co-k-plexes are defined as a relaxation of stable sets. This thesis studies co-k-plexes from polyhedral, algorithmic, and enumerative perspectives. The polyhedral analysis explores the relationship between the stable set polytope and co-k-plex polyhedra. Results include generalizations of odd holes, webs, wheels, and the claw. Sufficient conditions for the integrality of some related linear systems and results on the composition of stable set polyhedra are also given. The algorithmic analysis involves the development of heuristic and exact algorithms for finding maximum k-plexes. This problem is closely related to the search for co-kplexes. The final chapter includes results on the enumerative structure of co-k-plexes in certain graphs