Minimum 0-extensions of graph metrics
Given are a connected graph \(H= (T, U)\), a set of nodes \(V\supseteq T\), a nonnegative function \(c\) defined on unordered pairs of elements of \(V\). The minimum 0-extension problem means to minimize the inner product \(c\cdot m\) over all metrics \(m\) on \(V\) such that (i) \(m\) coincides with the distance function of \(H\) within \(T\), (ii) each \(v\in V\) is at zero distance from some \(s\in T\), i.e. \(m(v, s)= 0\). The minimum 0-extension problem is equivalent to the minimum cut problem that has wide applications in different branches of engineering mainly concerning flow problems. Relaxation of the minimum 0-extension problem concerns dropping (ii) and solving the reminder by linear programming. We say that a graph \(H\) is minimizable if solutions of the minimum 0-extension and its relaxation coincide. Therefore specifying what graph is minimizable enables us to say for what graph there exists a polynomial time algorithm solving the minimum cut problem. The author gives a proof that \(H\) is minimizable if and only if \(H\) is bipartite, has no isometric circuit with six or more nodes and is orientable in the sense that \(H\) can be oriented so that nonadjacent edges of any 4-circuit are oppositely directed along this ciruit. The presented research is in accordance with the current standard of studying strong NP-hardness of different problems. The goal is to know cases for which polynomial time algorithms can be applied for solving a particular NP-hard problem. The main weakness of these studies is the very individual treatment of each NP-hard problem and the lack of a common methodology for studying a class of such problems.
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- Metrics with finite sets of primitive extensions
- A characterization of minimizable metrics in the multifacility location problem
- Hard cases of the multifacility location problem
- On tight spans for directed distances
- Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
- Metric packing for \(K_ 3 + K_ 3\)
- Graphs of some CAT(0) complexes
- Minimum 0-extension problems on directed metrics
- A simple algorithm for the multiway cut problem
- On Lipschitz extension from finite subsets
- One more well-solved case of the multifacility location problem
- The vertex \(k\)-cut problem
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Weakly Modular Graphs and Nonpositive Curvature
- Bounded fractionality of the multiflow feasibility problem for demand graph \(K_3 + K_3\) and related maximization problems
- Simplex partitioning via exponential clocks and the multiway-cut problem
- Approximation Algorithms for the 0-Extension Problem
- Discrete convex functions on graphs and their algorithmic applications
- Simplex transformations and the multiway cut problem
- Parameterized algorithms for zero extension and metric labelling problems
- scientific article; zbMATH DE number 7559417 (Why is no real title available?)
- Retracting Graphs to Cycles
- Discrete convexity and polynomial solvability in minimum 0-extension problems (extended abstract)
- Discrete convexity and polynomial solvability in minimum 0-extension problems
- A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case
- Making doubling metrics geodesic
- On duality and fractionality of multicommodity flows in directed networks
- Generalized minimum 0-extension problem and discrete convexity
- Lower bounds on 0-extension with Steiner nodes
- Optimal padded decomposition for bounded treewidth graphs
- Cut-preserving vertex sparsifiers for planar and quasi-bipartite graphs
This page was built for publication: Minimum 0-extensions of graph metrics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1378296)
