Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
From MaRDI portal
Abstract: Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are 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 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.
Cites work
- A c^k n 5-approximation algorithm for treewidth
- Algorithmic applications of tree-cut width
- Approximating rank-width and clique-width quickly
- Constraint satisfaction with bounded treewidth revisited
- Fundamentals of parameterized complexity
- Graph Layout Problems Parameterized by Vertex Cover
- Graph minors. II. Algorithmic aspects of tree-width
- Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
- scientific article; zbMATH DE number 6515825 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- Immersions in highly edge connected graphs
- Lean Tree-Cut Decompositions: Obstructions and Algorithms
- New algorithms for maximum disjoint paths based on tree-likeness
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- On structural parameterizations of the bounded-degree vertex deletion problem
- On structural parameterizations of the edge disjoint paths problem
- On the complexity of some colorful problems parameterized by treewidth
- Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- Sparsity. Graphs, structures, and algorithms
- The complexity landscape of decompositional parameters for ILP
- The mixed Chinese postman problem parameterized by pathwidth and treedepth
- The power of cut-based parameters for computing edge-disjoint paths
- The structure of graphs not admitting a fixed immersion
- Twin-width. I: Tractable FO model checking
Cited in
(6)- The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
- Fixed-parameter algorithms for computing RAC drawings of graphs
- Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
- A new width parameter of graphs based on edge cuts: -edge-crossing width
- Slim tree-cut width
- Parameterized spanning tree congestion
This page was built for publication: Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6039417)
