| Title | : | Exact and Approximation Algorithms for Computing Connected f-Factors |
| Speaker | : | Rahul C S (IITM) |
| Details | : | Tue, 17 Feb, 2015 3:00 PM @ BSB 361 |
| Abstract: | : | Given an undirected graph G=(V,E) and a function f:V->N, an f-factor H is a spanning subgraph such that dH(v)=f(v) for every v in V. The problem of computing an f-factor is polynomial time solvable. We consider the problem of computing a connected f-factor. The Hamiltonian cycle problem is a special case of connected f-factor problem. Even when f(v)=d for every v in V and some constant d, the problem is shown to be NP-hard. When f(v)>=|V|/2 for every v in V, the problem is polynomial time solvable. Motivated by the observation that the hardness of the problem vary along with change in f, we attempt to explore the spectrum of values f and come up with a dichotomy result on connected f-factors. Further we come up with exact and approximation algorithms for optimization version and special cases of the same. We use the techniques from the literature to show that the problem of computing connected f-factor is hard even when f(v)>=|V|^(1-ε) for some constant 0<ε<1. At the other end of the spectrum, we come up with algorithms for the problem of computing connected f-factor when f(v)>=|V|/2.5 for every v in V and for the case where f(v)>=|V|/3 for every v in V. Both these algorithms can be extended to solve the optimization versions of the same. As a special case, we consider the metric version of the problem and give a 3-approximation algorithm. For the case where f(v)>=|V|/c for every v and for some constant c, we give a (1+ε)-approximation algorithm. |
