Parameterized graph separation problems

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

Parameterized and Exact Computation
On the Parameterized Complexity of Cutting a Few Vertices from a Graph
Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
Graph separators: A parameterized view
On the parameterized complexity of finding separators with non-hereditary properties

Cites work

scientific article; zbMATH DE number 5604125 (Why is no real title available?)
scientific article; zbMATH DE number 176254 (Why is no real title available?)
scientific article; zbMATH DE number 1161563 (Why is no real title available?)
scientific article; zbMATH DE number 2234775 (Why is no real title available?)
A Separator Theorem for Planar Graphs
Applications of a Planar Separator Theorem
Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
Finding and counting given length cycles
Finding good approximate vertex and edge partitions is NP-hard
Multiway cuts in node weighted graphs
Network flows. Theory, algorithms, and applications.
Primal-dual approximation algorithms for integral flow and multicut in trees
The Complexity of Multiterminal Cuts
Tight lower bounds for certain parameterized NP-hard problems

Cited in

(only showing first 100 items - show all)

Minimum Bisection Is Fixed-Parameter Tractable
Parameterized complexity of critical node cuts
Clique Cover and Graph Separation
\textsc{Max-Cut} parameterized above the Edwards-Erdős bound
Hitting selected (odd) cycles
Odd multiway cut in directed acyclic graphs
Faster graph bipartization
FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
Solving target set selection with bounded thresholds faster than \(2^n\)
Solving target set selection with bounded thresholds faster than \(2^n\)
Balanced judicious bipartition is fixed-parameter tractable
Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
Parameterized complexity of the anchored k-core problem for directed graphs
On the parameterized complexity of separating certain sources from the target
Parameterized algorithms for zero extension and metric labelling problems
Designing FPT algorithms for cut problems using randomized contractions
FPT algorithms for path-transversal and cycle-transversal problems
On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
Faster algorithms for all-pairs bounded min-cuts
Partitioning subclasses of chordal graphs with few deletions
The vertex \(k\)-cut problem
On polynomial kernels for structural parameterizations of odd cycle transversal
On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts
Algorithms for Multiterminal Cuts
Improved parameterized and exact algorithms for cut problems on trees
What's next? Future directions in parameterized complexity
Parameterized complexity of weighted multicut in trees
Parameterized complexity of multicut in weighted trees
Multi-budgeted directed cuts
Balanced Judicious Bipartition is Fixed-Parameter Tractable
A Linear-Time Parameterized Algorithm for Node Unique Label Cover
scientific article; zbMATH DE number 7559446 (Why is no real title available?)
Clustering with Local Restrictions
Multi-budgeted directed cuts
Critical node detection problem for complex network in undirected weighted networks
On the complexity of barrier resilience for fat regions and bounded ply
Almost 2-SAT is fixed-parameter tractable
Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
Finding \(k\)-secluded trees faster
Finding \(k\)-secluded trees faster
The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
A \(c^k n\) 5-approximation algorithm for treewidth
Quick separation in chordal and split graphs
New abilities and limitations of spectral graph bisection
Compression via matroids: a randomized polynomial kernel for odd cycle transversal
Parameterized complexity dichotomy for \textsc{Steiner Multicut}
Treewidth reduction for constrained separation and bipartization problems
The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
Multicut in trees viewed through the eyes of vertex cover
Restricted vertex multicut on permutation graphs
Parameterized complexity of deletion to scattered graph classes
Partitioning subclasses of chordal graphs with few deletions
The maximum happy induced subgraph problem: bounds and algorithms
A faster parameterized algorithm for Group Feedback Edge Set
The \textsc{Red-Blue Separation} problem on graphs
A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
Parameterizing cut sets in a graph by the number of their components
Linear time parameterized algorithms for subset feedback vertex set
A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
On integer and bilevel formulations for the \(k\)-vertex cut problem
Finding all leftmost separators of size \(\le k\)
Linear kernels for separating a graph into components of bounded size
Graph-Based Representations in Pattern Recognition
A survey of parameterized algorithms and the complexity of edge modification
Simple and improved parameterized algorithms for multiterminal cuts
The firebreak problem
Constant ratio fixed-parameter approximation of the edge multicut problem
scientific article; zbMATH DE number 1953093 (Why is no real title available?)
Subset feedback vertex set on graphs of bounded independent set size
On Weighted Graph Separation Problems and Flow Augmentation
An approach to emulating separable graphs
Subset feedback vertex set on graphs of bounded independent set size
Solution methods for the vertex variant of the network system vulnerability analysis problem
Parameterized and Exact Computation
Approximating small balanced vertex separators in almost linear time
_p-norm multiway cut
Important separators and parameterized algorithms
Parameterized algorithms for min-max multiway cut and list digraph homomorphism
Odd cycle transversal in mixed graphs
Structure theorem and isomorphism test for graphs with excluded topological subgraphs
How to Cut a Graph into Many Pieces
Covering Vectors by Spaces: Regular Matroids
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
Finding connected secluded subgraphs
On the parameterized complexity of computing balanced partitions in graphs
On the parameterized complexity of finding separators with non-hereditary properties
Multicut Is FPT
On the parameterized complexity of finding separators with non-hereditary properties
Deletion to scattered graph classes. I: Case of finite number of graph classes
On the parameterized complexity of deletion to \(\mathcal{H}\)-free strong components
A parameterized approximation scheme for min \(k\)-cut
Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
Finding connected secluded subgraphs
FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
A note on triple separation of a graph
Brief announcement: Bounded-degree cut is fixed-parameter tractable
On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
A logical approach to multicut problems
An improved parameterized algorithm for the minimum node multiway cut problem
scientific article; zbMATH DE number 7559431 (Why is no real title available?)

This page was built for publication: Parameterized graph separation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820151)