2008 | OriginalPaper | Chapter
Graph Layout Problems Parameterized by Vertex Cover
Authors : Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, Saket Saurabh
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the framework of parameterized complexity, one of the most commonly used structural parameters is the
treewidth
of the input graph. The reason for this is that most natural graph problems turn out to be fixed parameter tractable when parameterized by treewidth. However,
Graph Layout
problems are a notable exception. In particular, no fixed parameter tractable algorithms are known for the
Cutwidth
,
Bandwidth
,
Imbalance
and
Distortion
problems parameterized by treewidth. In fact,
Bandwidth
remains NP-complete even restricted to trees. A possible way to attack graph layout problems is to consider structural parameterizations that are stronger than treewidth. In this paper we study graph layout problems parameterized by the size of the minimum vertex cover of the input graph. We show that all the mentioned problems are fixed parameter tractable. Our basic ingredient is a classical algorithm for
Integer Linear Programming
when parameterized by dimension, designed by Lenstra and later improved by Kannan. We hope that our results will serve to re-emphasize the importance and utility of this algorithm.