Graph decomposition of slim graphs (Q1288512)

Let \(H\) be a fixed graph. An \(H\)-decomposition of an input graph \(G\) is a partition of the edge set of \(G\) such that each part forms a subgraph isomorphic to \(H\). This problem is known to be NP-complete as soon as \(H\) has a component with at least three edges. (This was conjectured by Holyer, and proved independently by \textit{D. Dor} and \textit{M. Tarsi} [Proc. 20th STOC, 252-263 (1992) and SIAM J. Comput. 26, No. 4, 1166-1187 (1997; Zbl 0884.05071)], and by \textit{D. G. Corneil, S. Masuyama} and \textit{S. L. Hakimi} [Discrete Appl. Math. 50, No. 2, 135-148 (1994; Zbl 0793.68114)]). Let \(H\) be a star, or a graph without a stable cutset. The corresponding \(H\)-decomposition problems are NP-complete in general, according to the above results (with the exception of a star with two edges). However, the authors give a polynomial-time algorithm to solve these \(H\)-decomposition problems in a class of slim graphs: A graph \(G\) is \(k\)-slim, if every subgraph \(S\) with \(s \geq k\) vertices contains a set of \(k\) vertices, whose removal separates \(S\) into two parts (with no edges between the parts), each with no more than \(2s/3\) vertices. The class of \(k\)-slim graphs contains the class of graphs of treewidth at most \(k\). However, the \(H\)-decomposition problem is not expressible in (extended) monadic second-order logic, illustrating the fact that some computational problems are efficiently solvable on graphs of bounded treewidth, but only by new algorithmic techniques. It is not known whether such techniques can be extended to solve the \(H\)-decomposition problem, in the class of slim (or bounded treewidth) graphs, for all graphs \(H\).