Abstract
Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for \(\textsf{NP}\)-hard graph problems. For problems that are \({{\textsf{W}}} [1]\)-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of treewidth that is based on edge cuts instead of vertex separators. While tree-cut width has been coined as such an analogue of treewidth for edge cuts, its algorithmic applications have often led to disappointing results: out of twelve problems where one would hope for fixed-parameter tractability parameterized by an edge-cut based analogue to treewidth, eight were shown to be \({{\textsf{W}}} [1]\)-hard parameterized by tree-cut width.
As our main contribution, we develop an edge-cut based analogue to treewidth called edge-cut width. Edge-cut width is, intuitively, based on measuring the density of cycles passing through a spanning tree of the graph. Its benefits include not only a comparatively simple definition, but mainly that it has interesting algorithmic properties: it can be computed by a fixed-parameter algorithm, and it yields fixed-parameter algorithms for all the aforementioned problems where tree-cut width failed to do so.
Cornelius Brand, Robert Ganian and Viktoriia Korchemna gratefully acknowledge support from the Austria Science Foundation (FWF, Project Y1329).
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.
We view a parameter as decompositional if it is tied to a well-defined graph decomposition; all decompositional parameters are closed under the disjoint union operation of graphs.
- 2.
We remark that besides establishing \({{\textsf{W}}} [1]\)-hardness for this problem, the authors also showed that the problem becomes \(\textsf{FPT}\) w.r.t. tree-cut width under additional restrictions.
- 3.
The authors originally used the name “local feedback edge number”.
- 4.
Note that by the syntax, it follows that \(e_i\) and \(e_j\) are both contained in \(\partial (v)\).
References
Bentert, M., Haag, R., Hofer, C., Koana, T., Nichterlein, A.: Parameterized complexity of min-power asymmetric connectivity. Theory Comput. Syst. 64(7), 1158–1182 (2020)
Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A c\({}^{\text{k}}\) n 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317–378 (2016)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Preprocessing for treewidth: a combinatorial analysis through kernelization. SIAM J. Discret. Math. 27(4), 2108–2142 (2013)
Bonnet, É., Kim, E.J., Thomassé, S., Watrigant, R.: Twin-width I: tractable FO model checking. In: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, 16–19 November 2020, pp. 601–612. IEEE (2020)
Bredereck, R., Heeger, K., Knop, D., Niedermeier, R.: Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters. In: Lu, P., Zhang, G. (eds.) 30th International Symposium on Algorithms and Computation, ISAAC 2019, 8–11 December 2019, Shanghai University of Finance and Economics, Shanghai, China. LIPIcs, vol. 149, pp. 44:1–44:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
Cygan, M., et al.: Lower bounds for kernelization. In: Parameterized Algorithms, pp. 523–555. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3_15
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer, Heidelberg (2013). https://doi.org/10.1007/978-1-4471-5559-1
Fellows, M.R., et al.: 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). https://doi.org/10.1007/978-3-540-92182-0_28
Fleszar, K., Mnich, M., Spoerhase, J.: New algorithms for maximum disjoint paths based on tree-likeness. Math. Program. 171, 433–461 (2017). https://doi.org/10.1007/s10107-017-1199-3
Ganian, R.: Improving vertex cover as a graph parameter. Discret. Math. Theor. Comput. Sci. 17(2), 77–100 (2015). http://dmtcs.episciences.org/2136
Ganian, R., Hlinený, P.: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discret. Appl. Math. 158(7), 851–867 (2010)
Ganian, R., Kim, E.J., Szeider, S.: Algorithmic applications of tree-cut width. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 348–360. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48054-0_29
Ganian, R., Klute, F., Ordyniak, S.: On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica 83(1), 297–336 (2021)
Ganian, R., Korchemna, V.: The complexity of Bayesian network learning: Revisiting the superstructure. In: Proceedings of NeurIPS 2021, The Thirty-Fifth Conference on Neural Information Processing Systems (2021, to appear)
Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. Artif. Intell. 257, 61–71 (2018)
Ganian, R., Ordyniak, S.: The power of cut-based parameters for computing edge-disjoint paths. Algorithmica 83(2), 726–752 (2021)
Ganian, R., Ordyniak, S., Ramanujan, M.S.: On structural parameterizations of the edge disjoint paths problem. Algorithmica 83(6), 1605–1637 (2021)
Giannopoulou, A.C., Kwon, O., Raymond, J., Thilikos, D.M.: Lean tree-cut decompositions: obstructions and algorithms. In: Niedermeier, R., Paul, C. (eds.) 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, Berlin, Germany, 13–16 March 2019. LIPIcs, vol. 126, pp. 32:1–32:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
Golovach, P.A., Komusiewicz, C., Kratsch, D., Le, V.B.: Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. J. Comput. Syst. Sci. 123, 76–102 (2022)
Gözüpek, D., Özkan, S., Paul, C., Sau, I., Shalom, M.: Parameterized complexity of the MINCCA problem on graphs of bounded decomposability. Theor. Comput. Sci. 690, 91–103 (2017)
Gutin, G.Z., Jones, M., Wahlström, M.: The mixed Chinese postman problem parameterized by pathwidth and treedepth. SIAM J. Discret. Math. 30(4), 2177–2205 (2016)
Kim, E.J., Oum, S., Paul, C., Sau, I., Thilikos, D.M.: An FPT 2-approximation for tree-cut decomposition. Algorithmica 80(1), 116–135 (2018)
Korhonen, T.: Single-exponential time 2-approximation algorithm for treewidth. CoRR abs/2104.07463 (2021). https://arxiv.org/abs/2104.07463
Magne, L., Paul, C., Sharma, A., Thilikos, D.M.: Edge-treewidth: algorithmic and combinatorial properties. CoRR abs/2112.07524 (2021)
Marx, D., Wollan, P.: Immersions in highly edge connected graphs. SIAM J. Discret. Math. 28(1), 503–520 (2014)
Nederlof, J., Pilipczuk, M., Swennenhuis, C.M.F., Węgrzycki, K.: Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space. In: Adler, I., Müller, H. (eds.) WG 2020. LNCS, vol. 12301, pp. 27–39. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-60440-0_3
Nešetřil, J., Ossona de Mendez, P.: Sparsity. Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27875-4
Oum, S.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithms 5(1), 1–20 (2008)
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)
Scheffler, P.: Practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Technical report TR 396/1994. FU Berlin, Fachbereich 3 Mathematik (1994)
Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Comb. Theory Ser. B 110, 47–66 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Brand, C., Ceylan, E., Ganian, R., Hatschka, C., Korchemna, V. (2022). Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts. In: Bekos, M.A., Kaufmann, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 2022. Lecture Notes in Computer Science, vol 13453. Springer, Cham. https://doi.org/10.1007/978-3-031-15914-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-15914-5_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15913-8
Online ISBN: 978-3-031-15914-5
eBook Packages: Computer ScienceComputer Science (R0)