Abstract
The recently introduced graph parameter tree-cut width plays a similar role with respect to immersions as the graph parameter treewidth plays with respect to minors. In this paper we provide the first algorithmic applications of tree-cut width to hard combinatorial problems. Tree-cut width is known to be lower-bounded by a function of treewidth, but it can be much larger and hence has the potential to facilitate the efficient solution of problems which are not known to be fixed-parameter tractable (FPT) when parameterized by treewidth. We introduce the notion of nice tree-cut decompositions and provide FPT algorithms for the showcase problems Capacitated Vertex Cover, Capacitated Dominating Set and Imbalance parameterized by the tree-cut width of an input graph G. On the other hand, we show that List Coloring, Precoloring Extension and Boolean CSP (the latter parameterized by the tree-cut width of the incidence graph) are W[1]-hard and hence unlikely to be fixed-parameter tractable when parameterized by tree-cut width.
R. Ganian and S. Szeider — Research supported by the FWF Austrian Science Fund (X-TRACT, P26696).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
A graph H is an immersion of a graph G if H can be obtained from G by applications of vertex deletion, edge deletion, and edge lifting, i.e., replacing two incident edges by a single edge which joins the two vertices not shared by the two edges.
- 2.
We call them “nice” as they serve a similar purpose as the nice tree decompositions [13], although the definitions are completely unrelated.
References
Biedl, T., Chan, T., Ganjali, Y., Hajiaghayi, M.T., Wood, D.R.: Balanced vertex-orderings of graphs. DAM 148(1), 27–48 (2005)
Biró, M., Hujter, M., Tuza, Z.: Precoloring extension. i. Interval graphs. Discrete Math. 100(1–3), 267–279 (1992)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics. Springer, New York (2000)
Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 78–90. Springer, Heidelberg (2008)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)
Erdős, P., Rubin, A.L., Taylor, H.: Choosability in graphs. Congressus Numerantium 26, 125–157 (1979)
Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143–153 (2011)
Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 294–305. Springer, Heidelberg (2008)
Frank, A., Tardos, É.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7(1), 49–65 (1987)
Grohe, M., Kawarabayashi, K.-I., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: STOC 2011–Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 479–488. ACM, New York (2011)
Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987)
Kim, E., Oum, S.-I., Paul, C., Sau, I., Thilikos, D.: FPT 2-approximation for constructing tree-cut decomposition (2014, Submitted) Manuscript
Kloks, T.: Treewidth: Computations and Approximations. Springer, Heidelberg (1994)
Lenstra, H.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)
Lokshtanov, D., Misra, N., Saurabh, S.: Imbalance is fixed parameter tractable. Inf. Process. Lett. 113(19–21), 714–718 (2013)
Marx, D., Wollan, P.: Immersions in highly edge connected graphs. SIAM J. Discrete Math. 28(1), 503–520 (2014)
Nash-Williams, C.S.J.A.: On well-quasi-ordering finite trees. Proc. Cambridge Philos. Soc. 59, 833–835 (1963)
Nešetřil, J., de Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin. 27(6), 1024–1041 (2006)
Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)
Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci. 76(2), 103–114 (2010)
Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Comb. Theo. Ser. B 110, 47–66 (2015). http://arxiv.org/abs/1302.3867 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ganian, R., Kim, E.J., Szeider, S. (2015). Algorithmic Applications of Tree-Cut Width. In: Italiano, G., Pighizzini, G., Sannella, D. (eds) Mathematical Foundations of Computer Science 2015. MFCS 2015. Lecture Notes in Computer Science(), vol 9235. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48054-0_29
Download citation
DOI: https://doi.org/10.1007/978-3-662-48054-0_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48053-3
Online ISBN: 978-3-662-48054-0
eBook Packages: Computer ScienceComputer Science (R0)