On Linear Recognition of Tree-Width at Most Four

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 stated 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 eliminated from the graph, has degree at most k. Arnborg and Proskurowski showed 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. 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. 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 reductions are then used in a linear-time algorithm that generates a 4-elimination sequence, if one exists.