Polynomial flow-cut gaps and hardness of directed cut problems
Explore this paper's citation graph
Summary
The results improve upon a long-standing lower bound of Ω(log n) for both types of flow-cut gaps and show that existence of PCP's for NP with perfect completeness, polynomially small soundness, and constant number of queries would imply a polynomial factor hardness of approximation for both these problems.
- Type
- article
- Published
- 2009-04-01
- Cited by
- 23
- References
- 34
- Access
- Open access
- OpenAlex
- https://openalex.org/W1974018476
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:47322565
Keywords
Minimum cut, Maximum cut, Maximum flow problem, Mathematics, Combinatorics
References
- PCP characterizations of NP: towards a polynomially-small error-probability
- Flows in networks
- A Lower Bound On The Integrality Gap For Minimum Multicut In Directed Networks
- Improved results for directed multicut
- Improved approximation for directed cut problems
- Expander flows, geometric embeddings and graph partitioning
- Approximate max-flow min-(multi)cut theorems and their applications
- Relations between average case complexity and approximation complexity
- Directed metrics and directed graph partitioning problems
- On the power of unique 2-prover 1-round games
- Hardness of Directed Routing with Congestion
- Logarithmic hardness of the directed congestion minimization problem
- Hardness of routing with congestion in directed graphs
- Testing for Concise Representations
- Approximating Directed Multicuts
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Efficient probabilistically checkable proofs and applications to approximations
- The Complexity of Multiterminal Cuts
- Hardness of cut problems in directed graphs
- Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling
Cited by
- Inapproximability of H-Transversal/Packing
- Multicut lower bounds via network coding
- Polynomial flow-cut gaps and hardness of directed cut problems
- A ( n)^Ω(1) Integrality Gap for the Sparsest Cut SDP
- A Graph-Theoretic Approach to Network Coding
- Network Capability in Localizing Node Failures via End-to-End Path Measurements
- Low-degree test with polynomially small error
- Vertical perimeter versus horizontal perimeter
- The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n
- Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
- Metric Violation Distance: Revisited and Extended
- Approximating Multicut and the Demand Graph
- L_1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry
- Sliding Scale Conjectures in PCP
- Bounds on maximum concurrent flow in random bipartite graphs
- A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
- Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter
- Low-Step Multi-commodity Flow Emulators
- Techniques in parameterized approximation
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
Related papers
- A new approach for computing a most positive cut using the minimum flow algorithms
- Polynomial Flow-Cut Gaps and Hardness of Directed Cut Problems (Extended Abstract)
- Polynomial flow-cut gaps and hardness of directed cut problems
- A faster algorithm for finding the minimum cut in a graph
- Selected applications of maximum flows and minimum cuts in networks
- The Maximum Flow Problem with Negative Capacities or Flows
- Algorithms for some linear and fractional combinatorial optimization problems