Methods are described that implement a branch-and-price decomposition
approach to solve the maximum weight independent set (MWIS) problem. The
approach is first described by Warrier et. al, and herein our contributions to this
research are presented. The decomposition calls for the exact solution of the
MWIS problem on induced subgraphs of the original graph. The focus of our
contribution is the use of chordal graphs as the induced subgraphs in this solution
framework.
Three combinatorial branch-and-bound solvers for the MWIS problem are
described. All use weighted clique covers to generate upper bounds, and all
branch according to the method of Balas and Yu. One extends and speeds up
the method of Babel. A second one modifies a method of Balas and Xue to
produce clique covers that share structural similarities with those produced by
Babel. Each of these improves on its predecessor. A third solver is a hybrid of
the other two. It yields the best known results on some graphs.
The related matter of deciding the imperfection or perfection of a graph
is also addressed. With the advent of the Strong Perfect Graph Theorem, this
problem is reduced to the detection of odd holes and anti-holes or the proof of
their absence. Techniques are provided that, for a given graph, find subgraphs in
polynomial time that contain odd holes whenever they are present in the given graph. These techniques and some basic structural results on such subgraphs
narrow the search for odd holes.
Results are reported for the performance of the three new solvers for the
MWIS problem that demonstrate that the third, hybrid solver outperforms its
clique-cover-based ancestors and, in some cases, the best current open-source
solver. The techniques for narrowing the search for odd holes are shown to
provide a polynomial-time reduction in the size of the input required to decide
the perfection or imperfection of a graph.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-1332 |
| Date | 15 May 2009 |
| Creators | Warren, Jeffrey Scott |
| Contributors | Hicks, Illya V. |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation, text |
| Format | electronic, application/pdf, born digital |
Page generated in 0.002 seconds