Half-integral Duals, Connectivity Augmentation and Multiflows in Planar Graphs
Naveen Garg
Indian Institute of Technology Delhi
AG1 Mittagsseminar (own work)
Naveen is with the CSE department at IIT Delhi. Prior to joining IITD he was a postdoc at MPII (1994-97). He is interested in algorithms in general, and approximation, online and game theoretic algorithms in particular.
AG 1, AG 3, AG 4, RG1, MMCI, AG 2, INET, AG 5, SWS
Given an edge weighted graph and a spanning tree, $T$, the {\em tree augmentation problem} is to pick a minimum weight set of edges, $F$, such that $T\cup F$ is 2-edge connected. Williamson et.al. gave a 2-approximation algorithm for this problem using the primal-dual schema. We show that when edge weights are integral, the WGMV procedure can be modified to obtain a half-integral dual.
The tree augmentation problem has an interesting connection to routing flow in graphs where the union of supply and demand is planar. The half-integrality of the dual leads to a tight 2-approximate max-half-integral-flow min-multicut theorem and a 4-approximate max-integral flow min-multicut theorem.
(joint work with Nikhil Kumar and Andras Sebo)