Complexity of Finding Embeddings in a $k$-Tree

A $k$-tree is a graph that can be reduced to the $k$-complete graph by a sequence of removals of a degree $k$ vertex with completely connected neighbors. We address the problem of determining whether a graph is a partial graph of a $k$-tree. This problem is motivated by the existence of polynomial t...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on matrix analysis and applications 1987-04, Vol.8 (2), p.277
Main Authors: Arnborg, Stefan, Corneil, Derek G, Proskurowski, Andrzej
Format: Article
Language:English
Subjects:
Algorithms
Graphs
Neighborhoods
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A $k$-tree is a graph that can be reduced to the $k$-complete graph by a sequence of removals of a degree $k$ vertex with completely connected neighbors. We address the problem of determining whether a graph is a partial graph of a $k$-tree. This problem is motivated by the existence of polynomial time algorithms for many combinatorial problems on graphs when the graph is constrained to be a partial $k$-tree for fixed $k$. These algorithms have practical applications in areas such as reliability, concurrent broadcasting and evaluation of queries in a relational database system. We determine the complexity status of two problems related to finding the smallest number $k$ such that a given graph is a partial $k$-tree. First, the corresponding decision problem is NP-complete. Second, for a fixed (predetermined) value of $k$, we present an algorithm with polynomially bounded (but exponential in $k$) worst case time complexity. Previously, this problem had only been solved for $k = 1,2,3$.
ISSN:0895-4798
1095-7162
DOI:10.1137/0608024