Finding small separators in linear time via treewidth reduction
From MaRDI portal
Abstract: We present a method for reducing the treewidth of a graph while preserving all of its minimal separators up to a certain fixed size . This technique allows us to solve Cut and Multicut problems with various additional restrictions (e.g., the vertices being removed from the graph form an independent set or induce a connected graph) in linear time for every fixed number of removed vertices. Our results have applications for problems that are not directly defined by separators, but the known solution methods depend on some variant of separation. for example, we can solve similarly restricted generalizations of Bipartization (delete at most vertices from to make it bipartite) in almost linear time for every fixed number of removed vertices. These results answer a number of open questions in the area of parameterized complexity. Furthermore, our technique turns out to be relevant for - and -coloring problems as well, which are cardinality constrained variants of the classical -coloring problem. We make progress in the classification of the parameterized complexity of these problems by identifying new cases that can be solved in almost linear time for every fixed cardinality bound.
Recommendations
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Linear time low tree-width partitions and algorithmic consequences
- Improved sublinear time algorithm for width-bounded separators
- Space-efficient vertex separators for treewidth
- An improved algorithm for finding tree decompositions of small width
- scientific article; zbMATH DE number 1420905
- Treewidth reduction for constrained separation and bipartization problems
- A simple linear-time algorithm for finding path-decompositions of small width
- Subexponential time algorithms for finding small tree and path decompositions
- A Heuristic Algorithm for Small Separators in Arbitrary Graphs
Cited in
(60)- A randomized polynomial kernel for subset feedback vertex set
- Independent feedback vertex set for P₅-free graphs
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- Graph separators: A parameterized view
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- The parameterized complexity of the minimum shared edges problem
- Linear kernels for separating a graph into components of bounded size
- Parameterized algorithms for min-max multiway cut and list digraph homomorphism
- On kernelization and approximation for the vector connectivity problem
- Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
- Finding a maximum minimal separator: graph classes and fixed-parameter tractability
- Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
- Minimal disconnected cuts in planar graphs
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Chordal editing is fixed-parameter tractable
- Treewidth reduction for constrained separation and bipartization problems
- Euler digraphs
- Designing FPT algorithms for cut problems using randomized contractions
- Odd multiway cut in directed acyclic graphs
- Parameterized complexity of the k-arc Chinese postman problem
- Sharp separation and applications to exact and parameterized algorithms
- Increasing the minimum degree of a graph by contractions
- Multicut Is FPT
- Minimum bisection is fixed-parameter tractable
- Parameterized complexity of three edge contraction problems with degree constraints
- On the parameterized complexity of computing balanced partitions in graphs
- On the parameterized complexity of finding separators with non-hereditary properties
- Multi-budgeted directed cuts
- Independent Feedback Vertex Set for P₅-free Graphs
- scientific article; zbMATH DE number 7278081 (Why is no real title available?)
- Parameterized complexity of critical node cuts
- On the parameterized complexity of finding separators with non-hereditary properties
- Losing Treewidth by Separating Subsets
- Hitting selected (odd) cycles
- Some results on connected vertex separators
- Contracting to a longest path in H-free graphs
- Minimization and parameterized variants of vertex partition problems on graphs
- On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
- A survey of parameterized algorithms and the complexity of edge modification
- On Weighted Graph Separation Problems and Flow Augmentation
- Minimum separator reconfiguration
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Exact and parameterized algorithms for the independent cutset problem
- Flow-augmentation. I: Directed graphs
- On polynomial kernelization for stable cutset
- When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices
- Solution discovery via reconfiguration for problems in P
- Revisiting extremal graphs having no stable cutsets
- On the parameterized complexity of multiway near-separator
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Forest cuts in sparse graphs
- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
- On polynomial kernelization for stable cutset
- Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
- Rank reduction of oriented graphs by vertex and edge deletions
- Cuts in graphs with matroid constraints
- Matching (multi)cut: algorithms, complexity, and enumeration
- MaxMin separation problems: FPT algorithms for st-separator and odd cycle transversal
- Multi-budgeted directed cuts
This page was built for publication: Finding small separators in linear time via treewidth reduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933661)
