Computer Science – Discrete Mathematics
Scientific paper
2007-07-24
Algorithmica, Volume 59, Number 4, 461-470,2011
Computer Science
Discrete Mathematics
12 pages, 6 figures, the main result used by quant-ph/0511070
Scientific paper
10.1007/s00453-009-9312-5
Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints admit polynomial-time upper bounds if the underlying graph has small treewidth. The same problems often encourage reducing the maximal degree of vertices to simplify theoretical arguments or address practical concerns. Such degree reduction can be performed through a sequence of splittings of vertices, resulting in an _expansion_ of the original graph. We observe that the treewidth of a graph may increase dramatically if the splittings are not performed carefully. In this context we address the following natural question: is it possible to reduce the maximum degree to a constant without substantially increasing the treewidth? Our work answers the above question affirmatively. We prove that any simple undirected graph G=(V, E) admits an expansion G'=(V', E') with the maximum degree <= 3 and treewidth(G') <= treewidth(G)+1. Furthermore, such an expansion will have no more than 2|E|+|V| vertices and 3|E| edges; it can be computed efficiently from a tree-decomposition of G. We also construct a family of examples for which the increase by 1 in treewidth cannot be avoided.
Markov Igor
Shi Yaoyun
No associations
LandOfFree
Constant-degree graph expansions that preserve the treewidth does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Constant-degree graph expansions that preserve the treewidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constant-degree graph expansions that preserve the treewidth will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-440943