Tree metrics and edge-disjoint S-paths

• 成果类型: Article
• 署名作者: Hirai, Hiroshi; Pap, Gyula
• 署名单位: University of Tokyo; Eotvos Lorand University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0713-5
• 发表日期: 2014
• 页码: 81-123
• 关键词: nonzero a-paths; Approximation algorithms; maximum number; multiflow; network; lines; FLOW

摘要

Given an undirected graph with a terminal set , a weight function on terminal pairs, and an edge-cost , the -weighted minimum-cost edge-disjoint -paths problem (-CEDP) is to maximize over all edge-disjoint sets of -paths, where denote the ends of and is the sum of edge-cost over edges in . Our main result is a complete characterization of terminal weights for which -CEDP is tractable and admits a combinatorial min-max theorem. We prove that if is a tree metric, then -CEDP is solvable in polynomial time and has a combinatorial min-max formula, which extends Mader's edge-disjoint -paths theorem and its minimum-cost generalization by Karzanov. Our min-max theorem includes the dual half-integrality, which was earlier conjectured by Karzanov for a special case. We also prove that -EDP, which is -CEDP with , is NP-hard if is not a truncated tree metric, where a truncated tree metric is a weight function represented as pairwise distances between balls in a tree. On the other hand, -CEDP for a truncated tree metric reduces to -CEDP for a tree metric . Thus our result is best possible unless P = NP. As an application, we obtain a good approximation algorithm for -EDP with near tree metric by utilizing results from the theory of low-distortion embedding.