Discrete convexity and polynomial solvability in minimum 0-extension problems (Q5962712)

From MaRDI portal
scientific article; zbMATH DE number 6544651
Language Label Description Also known as
English
Discrete convexity and polynomial solvability in minimum 0-extension problems
scientific article; zbMATH DE number 6544651

    Statements

    Discrete convexity and polynomial solvability in minimum 0-extension problems (English)
    0 references
    0 references
    23 February 2016
    0 references
    A \(0\)-extension of a graph \(G\) is a metric \(d\) on a set \(V\) containing the vertex set \(V_{G}\) of \(G\) 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-\mathrm{Ext}[G]\) on \(G\) is: given a set \(V \supseteq V_{G}\) and a non-negative cost function \(c\) defined on the set of all pairs of \(V\), find a \(0\)-extension \(d\) of \(G\) which minimizes \(\sum _{xy} c(x,y)d(x,y)\). \(0-\mathrm{Ext}[G]\) generalizes a number of basic combinatorial optimization problems, such as the minimum \((s,t)\)-cut problem or the multiway cut problem on \(m\) terminals. It is equivalent to the classical multifacility location problem, which has applications in computer vision and machine learning. Karzanov raised the question: what are the graphs \(G\) for which \(0-\mathrm{Ext}[G]\) is solvable in polynomial time? He proved the polynomial solvability of \(0-\mathrm{Ext}[G]\) for a large class of modular graphs, and he showed that \(0-\;mathrm{Ext}[G]\) is NP-hard if \(G\) is not modular or not orientable. The author of this paper proves the converse: if \(G\) is orientable and modular, then \(0-\mathrm{Ext}[G]\) can be solved in polynomial time. For the proof, he develops a theory of discrete, convex functions on orientable, modular graphs, similar to the work of Murota, and he utilizes a recent result of Thapper and Živnỳ on valued \(CSP\).
    0 references
    0 references
    0-extension
    0 references
    minimum 0-extension problem
    0 references
    modular graph
    0 references
    orientable graph
    0 references
    multifacility location problem
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references