Designing FPT Algorithms for Cut Problems Using Randomized Contractions
From MaRDI portal
Publication:3187169
DOI10.1137/15M1032077zbMath1348.68063arXiv1207.4079OpenAlexW2471129545MaRDI QIDQ3187169
Marcin Pilipczuk, Rajesh Chitnis, Michał Pilipczuk, Marek Cygan, Mohammad Taghi Hajiaghayi
Publication date: 16 August 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.4079
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (29)
A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Parameterized algorithms for graph partitioning problems ⋮ Parameterized aspects of strong subgraph closure ⋮ Finding connected secluded subgraphs ⋮ Unnamed Item ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Reducing CMSO model checking to highly connected graphs ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Multi-Budgeted Directed Cuts ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ Editing to Connected F-Degree Graph ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Multi-budgeted directed cuts ⋮ Euler Digraphs ⋮ An FPT algorithm for matching cut and d-cut
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On group feedback vertex set parameterized by the size of the cutset
- Fundamentals of parameterized complexity
- Parameterized complexity and approximability of the longest compatible sequence problem
- FPT algorithms for path-transversal and cycle-transversal problems
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Finding odd cycle transversals.
- Parameterized graph separation problems
- On the parameterized complexity of multiple-interval graph problems
- Almost 2-SAT is fixed-parameter tractable
- Multi-terminal maximum flows in node-capacitated networks
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Approximating minimum feedback sets and multicuts in directed graphs
- Packing directed circuits fractionally
- Clustering with local restrictions
- An improved parameterized algorithm for the minimum node multiway cut problem
- Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
- Parametrized complexity theory.
- Half-integrality, LP-branching, and FPT Algorithms
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
- On Multiway Cut Parameterized above Lower Bounds
- Finding small separators in linear time via treewidth reduction
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Subexponential Algorithms for Unique Games and Related Problems
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- Improved approximation for directed cut problems
- On the power of unique 2-prover 1-round games
- Color-coding
- An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
- Directed multicut is W[1-hard, even for four terminal pairs]
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Multiway cuts in node weighted graphs
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Faster Parameterized Algorithms Using Linear Programming
- (Meta) Kernelization
- Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- Minimum bisection is fixed parameter tractable
- On Kernelization and Approximation for the Vector Connectivity Problem
- Half-integrality, LP-branching and FPT Algorithms
- Multicut is FPT
- The Steiner k-Cut Problem
- Minimum cuts in near-linear time
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Parameterized Algorithms
- Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs
This page was built for publication: Designing FPT Algorithms for Cut Problems Using Randomized Contractions
