Parameterized Algorithms to Preserve Connectivity

VCLA and WPI will host a talk by M. S. Ramanujan on March 3rd, 2014.

ABSTRACT

In this work, we study the following family of connectivity problems. For a given $lambda$-edge connected (multi) graph $G=(V,E)$, a set of links $L$ such that $G+L=(V, Ecup L)$ is $(lambda+1)$-edge connected, and a positive integer $k$, the questions are

1. [Augmentation Problem:] whether $G$ can be augmented to a $(lambda+1)$-edge connected graph by adding at most $k$ links from $L$;

2. [Deletion Problem:] whether it is possible to preserve $(lambda+1)$-edge connectivity of graph $G+ L$ after deleting at least $k$ links from $L$.

We study the above problems in the realm of parameterized complexity and obtain the following results.

1. A $9^k|V|^{O(1)}$ time algorithm for a weighted version of the augmentation problem. This improves over the previous best bound of $2^{O(klog k)}|V|^{O(1)}$ given by Marx and Vegh [ICALP 2013]. We remark that even for $lambda=1$, the best known algorithm so far due to Nagamochi [DAM 2003], runs in time $2^{O(klog k)}|V|^{O(1)}$.

2. A $2^{O(k)}|V|^{O(1)}$ algorithm for the deletion problem thus establishing that the problem is fixed-parameter tractable (FPT). Moreover, we show that the problem admits a kernel with $12k$ vertices and $3k$ links when the graph $G$ has odd-connectivity and a kernel with $O(k^2)$ vertices and $O(k^2)$ links when $G$ has even-connectivity.

Our results are based on a novel connection between augmenting sets and the Steiner Tree problem in an appropriately defined auxiliary graph.

This is joint work with Manu Basavaraju, Fedor Fomin, Petr Golovach, Pranabendu Misra and Saket Saurabh.