Discrete convexity and polynomial solvability in minimum 0-extension problems
From MaRDI portal
Publication:5962712
Abstract: For a graph G and a set V containing the vertex set of G, a 0-extension of G is a metric d on V such that d extends the shortest path metric of G and for all x in V there exists a vertex s in G with d(x, s) = 0. The minimum 0-extension problem 0-Ext[G] on G is: given a set V containing V(G) and a nonnegative cost function c defined on the set of all pairs of V, find a 0-extension d of G with sum c(xy)d(x, y) minimum. The 0-extension problem generalizes a number of basic combinatorial optimization problems, such as minimum (s,t)-cut problem and multiway cut problem. Karzanov proved the polynomial solvability of 0-Ext[G] for a certain large class of modular graphs G, and raised the question: What are the graphs G for which 0-Ext[G] can be solved in polynomial time? He also proved that 0-Ext[G] is NP-hard if G is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if G is orientable and modular, then 0-Ext[G] can be solved in polynomial time. This completes the classification of graphs G for which 0-Ext[G] is tractable. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and Zivny on valued CSP.
Recommendations
- Discrete convexity and polynomial solvability in minimum 0-extension problems (extended abstract)
- Minimum 0-extension problems on directed metrics
- Minimum 0-extensions of graph metrics
- One more well-solved case of the multifacility location problem
- Approximation Algorithms for the 0-Extension Problem
Cites work
- scientific article; zbMATH DE number 439012 (Why is no real title available?)
- scientific article; zbMATH DE number 4191657 (Why is no real title available?)
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 3950165 (Why is no real title available?)
- scientific article; zbMATH DE number 26592 (Why is no real title available?)
- scientific article; zbMATH DE number 1322793 (Why is no real title available?)
- scientific article; zbMATH DE number 3103212 (Why is no real title available?)
- A Cut Approach to the Rectilinear Distance Facility Location Problem
- A characterization of minimizable metrics in the multifacility location problem
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A min-max theorem for transversal submodular functions and its implications
- A multifacility location problem on median spaces
- Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
- Directed submodularity, ditroids and directed submodular flows
- Discrete Convex Analysis
- Discrete convex analysis
- Folder complexes and multiflow combinatorial dualities
- Gated sets in metric spaces
- Generalized skew bisubmodularity: a characterization and a min-max theorem
- Geometric algorithms and combinatorial optimization
- Graphs of some CAT(0) complexes
- Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
- Hard cases of the multifacility location problem
- Hereditary modular graphs
- Metric graph theory and geometry: a survey
- Metrics with finite sets of primitive extensions
- Minimum 0-extensions of graph metrics
- Modular Interval Spaces
- Multimatroids I. Coverings by Independent Sets
- Networks with Condorcet solutions
- New algorithms for convex cost tension problem with application to computer vision
- Notes on L-/M-convex functions and the separation theorems
- On the complexity of submodular function minimisation on diamonds
- One more well-solved case of the multifacility location problem
- Oracle tractability of skew bisubmodular functions
- Polyhedra related to undirected multicommodity flows
- Proximity theorems of discrete convex functions
- Pseudomatroids
- Semiring-based constraint satisfaction and optimization
- Skew bisubmodularity and valued CSPs
- State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
- Submodular functions and optimization.
- Submodularity on a tree: unifying \(L^\natural\)-convex and bisubmodular functions
- The Complexity of Multiterminal Cuts
- The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
- The complexity of conservative valued CSPs
- The complexity of valued constraint satisfaction problems
- The maximum multiflow problems with bounded fractionality
- The power of linear programming for general-valued CSPs
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- Towards minimizing \(k\)-submodular functions
- Weakly Modular Graphs and Nonpositive Curvature
- \(L\)-convexity on graph structures
- \(M\)-convex function on generalized polymatroid
Cited in
(25)- Parameterized algorithms for zero extension and metric labelling problems
- A tractable class of binary VCSPs via M-convex intersection
- Discrete convex functions on graphs and their algorithmic applications
- Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
- Minimum violation vertex maps and their applications to cut problems
- Minimum 0-extension problems on directed metrics
- The power of Sherali-Adams relaxations for general-valued CSPs
- Weakly Modular Graphs and Nonpositive Curvature
- On a general framework for network representability in discrete optimization
- A nonpositive curvature property of modular semilattices
- A characterization of minimizable metrics in the multifacility location problem
- Beyond JWP: a tractable class of binary VCSPs via M-convex intersection
- scientific article; zbMATH DE number 7559417 (Why is no real title available?)
- Uniform modular lattices and affine buildings
- First-order logic axiomatization of metric graph theory
- The complexity of valued CSPs
- The vertex \(k\)-cut problem
- Isotonicity of minimizers in polychotomous discrete interval search via lattice programming
- Polynomial combinatorial algorithms for skew-bisubmodular function minimization
- Minimizing submodular functions on diamonds via generalized fractional matroid matchings
- A compact representation for modular semilattices and its applications
- Generalized minimum 0-extension problem and discrete convexity
- Lovász extension and graph cut
- A survey of fundamental operations on discrete convex functions of various kinds
- Discrete convexity and polynomial solvability in minimum 0-extension problems (extended abstract)
This page was built for publication: Discrete convexity and polynomial solvability in minimum 0-extension problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962712)
