Tight spans of distances and the dual fractionality of undirected multiflow problems (Q1044206): Difference between revisions

Suppose \(G=(V,E,c)\) is an undirected graph with nonnegative capacity function \(c\) on \(E\) and suppose \(S \subseteq V\) is a set of terminals and \(\mu\) a nonnegative weight function on the set of pairs in \(S\). A path \(P\) is called an \(S\)-path if both its ends are in \(S\). A collection \(\mathcal{P}\) of \(S\)-paths together with a nonnegative flow-valued function \(\lambda\) on \(\mathcal{P}\) satisfying the capacity constraint for each \(e \in E\), \(\sum_{P\in {\mathcal{P}}:e \in P}\lambda(P) \leq c(e)\) is called a multiflow. The weighted maximum multiflow problem with respect to \(G\) and \((S, \mu)\), denoted by \(M(G;S, \mu)\) is formulated as follows: Max\(\sum_{P \in {\mathcal{P}}}\mu(s_P,t_P)\lambda(P)\) over all multiflows \((P, \lambda)\) in \(G\). The fractionality of \((S,\mu)\) is the least positive integer \(k\) such that \(M(G;S,\mu)\) has a \(1/k\)-integral optimal flow for any integer-capacitated graph \(G\) with \(S \subseteq V\). If such a \(k\) does not exist, the fractionality of \((S, \mu)\) if defined to be infinity. The problem of interest in this paper is a necessary and sufficient condition for \((S, \mu)\) to have bounded fractionality. Even the case where \(\mu\) is a \(0,1\)-function is still open. Karzanov and Lomonosov extended this to metrics \(\mu\) that are cut-decomposable. The author considers the dual \(M^*(G; S, \mu)\) of the \(M(G; S, \mu)\). A necessary and sufficient condition for \((S, \mu)\) with integral \(\mu\) to have bounded dual fractionality is obtained. This extends two fundamental results of Kazarnov: (i) the characterization of commodity graphs \(H\) for which the dual of the maximum multiflow problem with respect to \(H\) has bounded fractionality [\textit{A.V. Karzanov}, ``Undirected multiflow problems and related topics - some recent developments and results'', Proc. Int. Congr. Math., Kyoto/Japan 1990, Vol. II, 1561--1571 (1991; Zbl 0746.90019)], and (ii) a characterization of metrics \(d\) on terminals for which the dual of metric-weighted maximum multiflow problem has bounded fractionality [\textit{A.V. Karzanov}, ``Minimum 0-extensions of graph metrics'', Eur. J. Comb. 19, No.1, 71--101 (1998; Zbl 0894.90147); ``Metrics with finite sets of primitive extensions'', Ann. Comb. 2, No.3, 211--241 (1998; Zbl 0946.90069)]. The key idea of this paper uses a nonmetric generalization of the tight span. These nonmetric tight spans provide a unified duality framework to weighted maximum multiflow problems, and give a unified interpretation of combinatorial dual solutions of several known min-max theorems in multiflow theory.