Abstract
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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adolphson, D., Hu, T.C.: Optimal linear ordering. SIAM J. Appl. Math. 25, 403–423 (1973)
Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling on parallel machines. J. of Scheduling 1, 55–66 (1998)
Blin, G., Fertin, G., Hermelin, D., Vialette, S.: Fixed-parameter algorithms for protein similarity search under RNA structure constraints. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 271–282. Springer, Heidelberg (2005)
Botafogo, R.A.: Cluster analysis for hypertext systems. In: Proceedings of SIGIR 1993, pp. 116–125. ACM Press, New York (1993)
Chinn, P., Chvatalova, J., Dewdney, A., Gibbs, N.: The bandwidth problem for graphs and matrices – a survey. Journal of Graph Theory 6, 223–254 (1982)
Clarkson, K.L.: Las Vegas Algorithms for Linear and Integer Programming When the Dimension is Small. Journal of the Association for Computing Machinery 42(2), 488–499 (1995)
Courcelle, B.: The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs Inf. Comput. 85(1), 12–75 (1990)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)
Fellows, M.R., Fomin, F.V., Lokshtanov, D., Losievskaja, E., Rosamond, F.A., Saurabh, S.: Parameterized Low-distortion Embeddings - Graph metrics into lines and trees, CoRR abs/0804.3028 (2008)
Fellows, M.R., Rosamond, F.A.: The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol. 4497, pp. 268–277. Springer, Heidelberg (2007)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
Frank, A., Tardos, E.: An Application of Simultaneous Diophantine Approximation in Combinatorial Optimization. Combinatorica 7, 49–65 (1987)
Gramm, J., Niedermeier, R., Rossmanith, P.: Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems. Algorithmica 37(1), 25–42 (2003)
Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and l\(_{\mbox{1}}\)-embeddings of graphs. Combinatorica 24(2), 233–269 (2004)
Heggernes, P., Meister, D., Proskurowski, A.: Minimum distortion embeddings into a path of bipartite permutation and threshold graphs. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol. 5124, pp. 331–342. Springer, Heidelberg (2008)
Heinz, S.: Complexity of integer quasiconvex polynomial optimization. Journal of Complexity 21, 543–556 (2005)
Junguer, M., Reinelt, G., Rinaldi, G.: The traveling salesman problem. In: Handbook on Operations Research and Management Sciences, vol. 7, pp. 225–330. North-Holland, Amsterdam (1995)
Kannan, R.: Minkowski’s Convex Body Theorem and Integer Programming. Mathematics of Operations Research 12, 415–440 (1987)
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)
Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoret. Comput. Sci. 172(1-2), 175–193 (1997)
Karger, D.R.: A randomized fully polynomial approximation scheme for all terminal network reliability problem. In: Proceedings of STOC, pp. 11–17. ACM Press, New York (1996)
Khachiyan, L., Porkolab, L.: Integer Optimization on Convex Semialgebraic Sets. Discrte Computational Geometry 23, 207–224 (2000)
Lenstra, H.W.: Integer Programming with a Fixed Number of Variables. Mathematics of Operations Research 8, 538–548 (1983)
Linial, N., London, E., Rabinovich, Y.: The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica 15(2), 215–245 (1995)
Makedon, F., Sudborough, I.H.: Minimizing width in linear layouts. In: ICALP 1983. LNCS, vol. 154, pp. 478–490. Springer, Heidelberg (1983)
Mutzel, P.: A polyhedral approach to planar augmentation and related problems. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol. 979, pp. 497–507. Springer, Heidelberg (1995)
Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)
Papakostas, A., Tollis, I.G.: Algorithms for area-efficient orthogonal drawings. Computational Geometry 9, 83–110 (1998)
Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth II: Algorithms for partial w-trees of bounded degree. J. Algorithms 56(1), 25–49 (2005)
Wood, D.R.: Optimal three-dimensional orthogonal graph drawing in the general position model. Theoret. Comput. Sci. 299(1-3), 151–178 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S. (2008). Graph Layout Problems Parameterized by Vertex Cover. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-540-92182-0_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92181-3
Online ISBN: 978-3-540-92182-0
eBook Packages: Computer ScienceComputer Science (R0)