Linear algorithms for graphs of tree-width at most four
Daniel P. Sanders · SMARTech Repository (Georgia Institute of Technology) · 1993
A graph G has tree-width at most k if the vertices of G can be decomposed into a tree-like structure of sets of vertices, each set having cardinality at most $k+1.$ An alternate definition of tree-width is in terms of k-elimination sequences, an order to eliminate the vertices of the graph such that each vertex, at the time it is eliminated from the graph, has degree at most k. Amborg and Proskurowski have shown that if a graph has tree-width at most a fixed k, then many NP-hard problems can be solved in linear time, provided this k-elimination sequence is part of the input. Some examples are maximum independent set, minimum dominating set, chromatic number, Hamilton circuit, and network reliability. These algorithms are very efficient for small k, such as 2, 3, or 4, but may be impractical for large k, as they depend exponentially on k. This thesis presents a practical, efficient linear algorithm to find a 4-elimination sequence for a graph of tree-width at most four. Graphs of tree-width at most k are a natural generalization of series-parallel graphs. Just as linear algorithms on series-parallel graphs depend upon their structure, that they have an instance of a series-reduction or a parallel-reduction, the algorithm presented in this thesis depends upon the graphs having certain reductions as well. A reduction process is developed, and reductions are shown that can be applied to a graph of tree-width at most four without increasing its tree-width. Further, each graph of tree-width at most four is shown to contain one of these reductions. The reductions are then used in a linear time algorithm which generates a 4-elimination sequence, if one exists.