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 M. A. Bekos & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science (pp. 98–113). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-031-15914-5_8
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.
