Parameterized algorithms for finding highly connected solution

To introduce our question and the parameterization, consider the classical Vertex Cover problem. In this problem, the input is a graph G on n vertices and a positive integer ℓ, and the goal is to find a vertex subset S of size at most ℓ such that G − S is an independent set. Further, we want that G [ S ] is highly connected. That is, G [ S ] should be n − k edge-connected. Clearly, the problem is NP-complete, as substituting k = n − 1, we obtain the Connected Vertex Cover problem. A simple observation also shows that the problem admits an algorithm with running time n O ( k ). Since the problem is polynomial-time solvable for every fixed integer k, a natural parameter is the integer k. In all the problems we consider, the parameter is k, and the goal is to find a solution S of size at most ℓ, such that G [ S ] is n − k edge-connected and G − S satisfies a property. We show that this version of well-known problems such as Vertex Cover, Feedback Vertex Set, Odd Cycle Transversal and Multiway Cut admit an algorithm with running time f ( k ) ⋅ n O ( 1 ), that is, they are FPT with the parameter k. One of our main subroutines to obtain these algorithms is an FPT algorithm for n − k edge connected Steiner Subgraph, which could be of an independent interest. Finally, we also show that such an algorithm is not possible for Multicut.

Authors

• Ankit Abhinav
• Susobhan Bandopadhyay
• Aritra Banik National Institute of Science Education and Research
• Saket Saurabh

Keywords

• Subset problems
• Parameterized algorithms
• Connectivity