The nonexistence of reduction rules giving an embedding into a \(k\)-tree
type: Item
instance of: scholarly article
title: The nonexistence of reduction rules giving an embedding into a \(k\)-tree
zbMATH Open document ID: 0809.05034
DOI: 10.1016/0166-218X(94)90023-X
author: Jens Lagergren
published in: Discrete Applied Mathematics
publication date: 1995-02-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 681639
zbMATH Keywords: \(k\)-tree embedding problem
zbMATH Keywords: embedding
zbMATH Keywords: treewidth
zbMATH Keywords: tree-decomposition
zbMATH Keywords: triggered reduction rule
zbMATH Keywords: linear time algorithms
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Q3812222
cites work: Characterization and Recognition of Partial 3-Trees
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Linear-time computation of optimal subgraphs of decomposable graphs
cites work: Q4734761
cites work: Q3899969
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Characterization of partial 3-trees in terms of three structures
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: On simple characterizations of k-trees
Wikidata QID: Q127883899
Recommended article: Q3758844
Recommended article: Sequential and parallel algorithms for embedding problems on classes of partial k-trees
Recommended article: Characterization and Recognition of Partial 3-Trees
Recommended article: Embeddings of \(k\)-connected graphs of pathwidth \(k\)
Recommended article: Linear time algorithms for NP-hard problems restricted to partial k- trees
Recommended article: On reduction algorithms for graphs with small treewidth
Recommended article: Q2721972
Recommended article: Tree inclusion problems
Recommended article: Q3716296
description: scientific article; zbMATH DE number 681639