Unbalanced Point-to-Point Connectivity Problem

From himtp
Jump to: navigation, search

(suggested by Chandra Chekuri)

Problem Statement

The input consists of an edge-weighted undirected graph G = (V,E), two disjoint terminal sets S, T ⊂ V with |S| ≤ |T|. The goal is to find a matching M between S and T that saturates S (that is, all nodes in S are matched) and minimum cost subgraph H of G such that each pair uv in M is connected in H.

What is known?

When |S| = |T| this is the point-to-point connectivity problem. Goemans and Williamson obtained a 2-approximation for this by casting it as a special case of the problem of covering a {0,1} proper function. The new problem appears to be more complex. It captures the rooted k-MST problem as follows. We create k dummy nodes v1, v2, ..., vr that are connected to the given root r with zero cost and let these k nodes be S. T is set to V - {r}.

Is there an O(1)-approximation for the problem? An O(log n)-approximation should follow via the use of probabilistic tree embeddings. Perhaps one can also obtain an a slightly improved bound of O(log |S|) instead of O(log n). We note that the problem does not admit a reduction to covering {0,1} skew-supermodular functions and hence we cannot apply Jain's result. Can we obtain a bi-criteria approximation? An (a,b) approximation here matches an a-fraction of S to T and obtains a Steiner forest for the matching with cost at most b OPT.

Please add comments here

Zeev Nutov pointed out a paper of his [1] on the fixed cost k-flow and related problems. It discusses the Generalized Point-to-Point Connectivity Problem which is a further generalization of what I posed. I was most likely inspired by their paper to think about the unbalanced P2P problem since I do recall seeing it.