1987/04/01 by Stefan Arnborg, Derek G. Corneil, Andrzej Proskurowski · 49 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Binary tree #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Feedback vertex set #Gomory–Hu tree #Graph #K-ary tree #Line graph #Mathematics #Pathwidth #Time complexity #Tree decomposition #Tree structure #Vertex (graph theory)
paper · doi:10.1137/0608024
crossref issued 1987/04/01 · crossref published 1987/04/01 · crossref published-print 1987/04/01 · openalex publication_date 1987/04/01 · crossref created 2005/02/27 · crossref deposited 2018/03/23 · openalex created_date 2025/10/10 · crossref indexed 2026/08/04 · openalex updated_date 2026/08/04
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.