On Multiway Cut Parameterized above Lower Bounds
From MaRDI portal
Publication:2891333
DOI10.1007/978-3-642-28050-4_1zbMath1352.68100arXiv1107.1585OpenAlexW1689320375MaRDI QIDQ2891333
Jakub Onufry Wojtaszczyk, Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk
Publication date: 15 June 2012
Published in: ACM Transactions on Computation Theory, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1107.1585
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items
Faster exact algorithms for some terminal set problems ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Parameterizing edge modification problems above lower bounds ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\) ⋮ Structural parameterizations with modulator oblivion ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments ⋮ Odd cycle transversal in mixed graphs ⋮ Parameterized complexity of MaxSat above average ⋮ Solving min ones 2-SAT as fast as vertex cover ⋮ Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations ⋮ Hitting Selected (Odd) Cycles ⋮ The vertex \(k\)-cut problem ⋮ Unnamed Item ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ A kernel of order \(2k-c\log k\) for vertex cover ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multicut Is FPT ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Edge bipartization faster than \(2^k\) ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Multi-Budgeted Directed Cuts ⋮ Parameterized complexity of critical node cuts ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ List H-coloring a graph by removing few vertices ⋮ The complexity of finding small separators in temporal graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Large Independent Sets in Subquartic Planar Graphs ⋮ Large Independent Sets in Triangle-Free Planar Graphs ⋮ Balanced stable marriage: how close is close enough? ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition ⋮ Quick separation in chordal and split graphs ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Important Separators and Parameterized Algorithms ⋮ The Multi-terminal Vertex Separator Problem: Polytope Characterization and TDI-ness ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Multi-budgeted directed cuts ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ On group feedback vertex set parameterized by the size of the cutset
Cites Work
- Unnamed Item
- Vertex cover problem parameterized above and below tight bounds
- Parameterized graph separation problems
- Simple and improved parameterized algorithms for multiterminal cuts
- On the parameterized complexity of multiple-interval graph problems
- Almost 2-SAT is fixed-parameter tractable
- An improved parameterized algorithm for the minimum node multiway cut problem
- Paths, Flowers and Vertex Cover
- FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
- All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- The Complexity of Multiterminal Cuts
- Multiway cuts in node weighted graphs
- Multicut is FPT
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
