Discrete convexity and polynomial solvability in minimum 0-extension problems

DOI10.1007/S10107-014-0824-7zbMATH Open1342.90163arXiv1405.4960OpenAlexW1877564947MaRDI QIDQ5962712FDOQ5962712

Authors: Hiroshi Hirai 

Publication date: 23 February 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1405.4960

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

zbMATH Keywords

multifacility location problemmodular graphminimum 0-extension problem0-extensionorientable graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Distance in graphs (05C12)

Cites Work

• Discrete Convex Analysis
• Geometric algorithms and combinatorial optimization
• Graphs of some CAT(0) complexes
• Submodular functions and optimization.
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Complexity of Multiterminal Cuts
• Title not available (Why is that?)
• The Complexity of Finite-Valued CSPs
• The complexity of valued constraint satisfaction problems
• The complexity of conservative valued CSPs
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A multifacility location problem on median spaces
• State of the Art—Location on Networks: A Survey. Part II: Exploiting Tree Network Structure
• Networks with Condorcet solutions
• Semiring-based constraint satisfaction and optimization
• Approximation algorithms for classification problems with pairwise relationships
• Metric graph theory and geometry: a survey
• Title not available (Why is that?)
• Gated sets in metric spaces
• Multimatroids I. Coverings by Independent Sets
• Pseudomatroids
• Directed submodularity, ditroids and directed submodular flows
• \(M\)-convex function on generalized polymatroid
• Submodularity on a tree: unifying \(L^\natural\)-convex and bisubmodular functions
• Title not available (Why is that?)
• Discrete convex analysis
• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Polyhedra related to undirected multicommodity flows
• Metrics with finite sets of primitive extensions
• Minimum 0-extensions of graph metrics
• Folder complexes and multiflow combinatorial dualities
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
• Title not available (Why is that?)
• New algorithms for convex cost tension problem with application to computer vision
• Notes on L-/M-convex functions and the separation theorems
• Towards minimizing \(k\)-submodular functions
• The Power of Linear Programming for General-Valued CSPs
• On the complexity of submodular function minimisation on diamonds
• A Cut Approach to the Rectilinear Distance Facility Location Problem
• Weakly Modular Graphs and Nonpositive Curvature
• Hereditary modular graphs
• Modular Interval Spaces
• A characterization of minimizable metrics in the multifacility location problem
• Title not available (Why is that?)
• The Maximum Multiflow Problems with Bounded Fractionality
• L-CONVEXITY ON GRAPH STRUCTURES
• Generalized skew bisubmodularity: a characterization and a min-max theorem
• Skew Bisubmodularity and Valued CSPs
• Oracle Tractability of Skew Bisubmodular Functions
• A Min-Max Theorem for Transversal Submodular Functions and Its Implications
• Proximity theorems of discrete convex functions
• Hard cases of the multifacility location problem
• One more well-solved case of the multifacility location problem
• The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization

Cited In (23)

• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• Title not available (Why is that?)
• The vertex \(k\)-cut problem
• A nonpositive curvature property of modular semilattices
• Uniform modular lattices and affine buildings
• A compact representation for modular semilattices and its applications
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• On a general framework for network representability in discrete optimization
• The Complexity of Valued CSPs
• Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection.
• Node-Connectivity Terminal Backup, Separately Capacitated Multiflow, and Discrete Convexity
• Polynomial combinatorial algorithms for skew-bisubmodular function minimization
• Minimum Violation Vertex Maps and Their Applications to Cut Problems
• Minimum 0-extension problems on directed metrics
• First-order logic axiomatization of metric graph theory
• Weakly Modular Graphs and Nonpositive Curvature
• Title not available (Why is that?)
• Discrete Convex Functions on Graphs and Their Algorithmic Applications
• Isotonicity of minimizers in polychotomous discrete interval search via lattice programming
• Generalized minimum 0-extension problem and discrete convexity
• A characterization of minimizable metrics in the multifacility location problem
• A survey of fundamental operations on discrete convex functions of various kinds
• A Tractable Class of Binary VCSPs via M-Convex Intersection

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)