Branch decompositions and their applications

[摘要] Many real-life problems can be modeled as optimization or decision problems on graphs. Also, many of those real-life problems are NP-hard. One traditional method to solve these problems is by branch and bound while another method is by graph decompositions. In the 1980;;s, Robertson and Seymour conceived of two new ways to decompose the graph in order to solve these problems. These ingenious ideas were only by-products of their work proving Wagner;;s Conjecture. A branch decomposition is one of these ideas. A paper by Arnborg, Lagergren and Seeseshowed that many NP-complete problems can be solved in polynomial time using divide and conquer techniques on input graphs with bounded branchwidth, but a paper by Seymour and Thomas proved that computing an optimal branch decomposition is also NP-complete. Although computing optimal branch decompositions is NP-complete, there is a plethora of theory about branchwidth and branch decompositions. For example, a paper by Seymour and Thomas offered a polynomial time algorithm to compute the branchwidth and optimal branch decomposition for planar graphs. This doctoral research is concentrated on constructing branch decompositions for graphs and using branch decompositions to solve NP-complete problems modeled on graphs. In particular, a heuristic to compute near-optimal branch decompositions is presented and the heuristic is compared to previous heuristics in the subject. Furthermore, a practical implementation of an algorithm given in a paper by Seymour and Thomas for computing optimal branch decompositions of planar graphs is implemented with the addition of heuristics to give the algorithm a ;;divide and conquer;; design. In addition, this work includes a theoretical result relating the branchwidth of planar graphs to their duals, characterizations of branchwidth for Halin and chordal graphs. Also, this work presents an algorithm for minor containment using a branch decomposition and a parallel implementation of the heuristic for general graphs using p-threads.

[发布机构] Rice University

[效力级别] Operations research