Designing FPT Algorithms for Cut Problems Using Randomized Contractions

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

zbMATH Keywords

fixed-parameter tractabilitygraph separations problemsrandomized contractionsunique label cover

Mathematics Subject Classification ID

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