The nonexistence of reduction rules giving an embedding into a \(k\)-tree (Q1336627)

This paper considers the \(k\)-tree embedding problem: given a graph \(G= (V,E)\), is \(G\) a subgraph of a \(k\)-tree and if so, find such an embedding. This is equivalent to determining whether \(G\) has treewidth at most \(k\), and if so, finding a tree-decomposition with optimal width of \(G\). A locally triggered reduction rule, applied to a graph \(G\), takes a vertex \(v\) which belongs to a subgraph of \(G\) with a certain well- described structure, connects all neighbors of \(v\), and removes \(v\). For \(k= 2\), \(k= 3\), a set of such reduction rules exist, such that the rule can be applied repeatedly until the empty graph results, if and only if \(G\) is in the class to be recognized. These sets can be used to obtain linear time algorithms for the \(k\)-embedding problem. This paper shows that for \(k=4\), such reduction rules do not exist. More general sets of reduction rules for the \(k\)-tree embedding problem (for arbitrary fixed \(k\)) are known to exist, see \textit{S. Arnborg}, \textit{D. G. Corneil} and \textit{A. Proskurowski} [SIAM J. Algebraic Discrete Methods 8, 277-284 (1987; Zbl 0611.05022)]. Also, linear time algorithms for the \(k\)-embedding problem, using a different method, are known (\(k\) fixed), see \textit{H. L. Bodlaender} [A linear time algorithm for finding tree- decompositions of small treewidth, Proc. 25th Ann. Symp. Theor. Comp. Sci., 226-234 (1993)].