A O(ck n) 5-Approximation Algorithm for Treewidth

Hans L. Bodlaender; Pål Grønås Drange; Markus S. Dregi; Fedor V. Fomin; Daniel Lokshtanov; Michal Pilipczuk

A O(ck n) 5-Approximation Algorithm for Treewidth

Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, Michal Pilipczuk

Research output: Contribution to journal › Article › Academic

Abstract

We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of G of width at most 5k+4. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single-exponential in k and linear in n. Treewidth based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the treewidth and linear in the input size.

Original language	English
Journal	CoRR
Volume	abs/1304.6321
Publication status	Published - 2013

Access to Document

http://arxiv.org/abs/1304.6321

Cite this

@article{23a3943f38024a62af15dbf3e032c6b2,

title = "A O(ck n) 5-Approximation Algorithm for Treewidth",

abstract = "We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of G of width at most 5k+4. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single-exponential in k and linear in n. Treewidth based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the treewidth and linear in the input size.",

author = "Bodlaender, {Hans L.} and Drange, {P{\aa}l Gr{\o}n{\aa}s} and Dregi, {Markus S.} and Fomin, {Fedor V.} and Daniel Lokshtanov and Michal Pilipczuk",

year = "2013",

language = "English",

volume = "abs/1304.6321",

journal = "CoRR",

}

TY - JOUR

T1 - A O(ck n) 5-Approximation Algorithm for Treewidth

AU - Bodlaender, Hans L.

AU - Drange, Pål Grønås

AU - Dregi, Markus S.

AU - Fomin, Fedor V.

AU - Lokshtanov, Daniel

AU - Pilipczuk, Michal

PY - 2013

Y1 - 2013

N2 - We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of G of width at most 5k+4. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single-exponential in k and linear in n. Treewidth based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the treewidth and linear in the input size.

AB - We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of G of width at most 5k+4. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single-exponential in k and linear in n. Treewidth based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the treewidth and linear in the input size.

M3 - Article

VL - abs/1304.6321

JO - CoRR

JF - CoRR

ER -

A O(ck n) 5-Approximation Algorithm for Treewidth

Abstract

Access to Document

Fingerprint

Cite this