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

*(English)*Zbl 0809.05034This 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 S. Arnborg, D. G. Corneil and 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 H. L. Bodlaender [A linear time algorithm for finding tree- decompositions of small treewidth, Proc. 25th Ann. Symp. Theor. Comp. Sci., 226-234 (1993)].

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 S. Arnborg, D. G. Corneil and 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 H. L. Bodlaender [A linear time algorithm for finding tree- decompositions of small treewidth, Proc. 25th Ann. Symp. Theor. Comp. Sci., 226-234 (1993)].

Reviewer: H.Bodlaender (Utrecht)

##### MSC:

05C05 | Trees |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

68R10 | Graph theory (including graph drawing) in computer science |

##### Keywords:

\(k\)-tree embedding problem; embedding; treewidth; tree-decomposition; triggered reduction rule; linear time algorithms
PDF
BibTeX
XML
Cite

\textit{J. Lagergren}, Discrete Appl. Math. 54, No. 2--3, 219--223 (1994; Zbl 0809.05034)

Full Text:
DOI

##### References:

[1] | Arnborg, S.; Corneil, D.G.; Proskurowski, A., Complexity of finding embeddings in a k-tree, SIAM J. algebraic discrete methods, 8, 277-284, (1987) · Zbl 0611.05022 |

[2] | Arnborg, S.; Courcelle, B.; Proskurowski, A.; Seese, D., An algebraic theory of graph reduction, (January 1990), Université de Bordeaux, I-9002 |

[3] | Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graph (extended abstract), (), 38-51, Lecture Notes in Computer Science |

[4] | Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. algebraic discrete methods, 7, 305-314, (1986) · Zbl 0597.05027 |

[5] | Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems on graphs embedded in k-trees, Discrete appl. math., 23, 11-24, (1989) · Zbl 0666.68067 |

[6] | Bern, M.W.; Lawler, E.L.; Wong, A.L., Linear time computation of optimal subgraphs of decomposable graphs, J. algorithms, 8, 216-235, (1987) · Zbl 0618.68058 |

[7] | Bodlaender, H.L., Dynamic programming on graphs with bounded tree-width, Mit⧸lcs⧸tr-394, (1987), MIT |

[8] | Bodlaender, H.L., Improved self-reduction algorithms for graphs with bounded tree-width, Ruu-cs-88-29, (1988), University of Utrecht · Zbl 0684.68047 |

[9] | Bollobás, B., Graph theory, (1985), Springer Berlin |

[10] | Bondy, J.A.; Murty, U.S.R., Graph theory and applications, (1979), North-Holland Amsterdam · Zbl 0453.00012 |

[11] | Courcelle, B., The monadic second order logic of graphs I: recognizable sets of finite graphs, Inform. and comput., 85, 12-75, (1990) · Zbl 0722.03008 |

[12] | Kajitani, Y.; Ishizuka, A.; Ueno, S., Characterization of partial 3-trees in terms of 3 structures, Graphs combin., 2, 233-246, (1986) · Zbl 0609.05030 |

[13] | Lagergren, J., Efficient parallel algorithms for tree-decomposition and related problems, Ieee focs, 173-182, (1990) |

[14] | Matousek; Tomas, Algorithms finding tree decompositions of graphs, manuscript, (1989) |

[15] | Robertson, N.; Seymour, P.D., Graph minors II. algorithmic aspects of tree width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017 |

[16] | Robertson, N.; Seymour, P.D., Graph minors XIII. the disjoint path problem, (September, 1986), preprint |

[17] | Rose, D., On simple characterizations of k-trees, Discrete math., 7, 317-322, (1974) · Zbl 0285.05128 |

[18] | T.V. Wimer, Ph.D. Thesis, URI-030, Clemson University, Clemson. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.