ON LINEAR RECOGNITION OF TREE-WIDTH AT MOST 4

A graph G has tree-width at most Ic if the vertices of G can be decomp osed into a tree-like structure of sets of vertices, each set having c ardinality at most k+1. An alternate definition of tree-width is state d in terms of a k-elimination sequence, which is an order to eliminate the vertices of the graph such that each vertex, at the time it is el iminated from the graph, has degree at most k. Arnborg and Proskurowsk i showed that if a graph has tree-width at most a fixed Ic, then many NP-hard problems can be solved in linear time, provided this k-elimina tion sequence is part of the input. These algorithms are very efficien t for small k, such as 2, 3, or 4, but may be impractical for large Ic as they depend exponentially on k. 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 contains one of these reductions. The reducti ons are then used in a linear-time algorithm that generates a 4-elimin ation sequence, if one exists.