| Title | : | Classifying Connected f-Factor Problems based on f |
| Speaker | : | Rahul C S (IITM) |
| Details | : | Tue, 12 May, 2015 3:00 PM @ BSB 361 |
| Abstract: | : | A graph is a mathematical structure widely used for modeling networks and in many other applications. Finding subgraphs satisfying degree and connectivity constraints is a well studied problem over many years. Given an undirected graph G=(V,E) having n vertices and a function f:V->mathbb{N}$, an $f$-factor H is a spanning subgraph such that degree of each vertex v in H is $f(v)$, for every v in V. We consider the problem of computing an $f$-factor which is connected. We observe that the computational hardness of the problem vary depending on the smallest value in the range of $f$. When $f(v)$>=c for every v in V and some constant c, the problem is shown to be NP-Complete. When $f(v)$>=|V|/2 for every v in V, the problem is polynomial time solvable. Thus, when the lower bound on the range of $f$ is too small the problem is hard and when it is too large, the problem is easy. Motivated by this observation, we attempt to explore the codomain of $f$ and understand how the hardness of the problem vary along with change in $f$. Further we come up with an algorithm and a hardness result.
We had shown that the problem of computing a connected $f$-factor is hard even when $f(v)$>= n^{1-epsilon} for some constant 0 In this talk we present a polynomial time algorithm for computing connected $f$-factor where $f(v)$>= n/c for every v in V and some constant c. The same algorithm can be used to solve for the case where $f(v)$>= n/polylog(n) for every v in V in time n^{O(polylog(n))}$. This means the problem cannot be NP-Complete unless Exponential Time Hypothesis(ETH) is false. Similarly, we give a subexponential time reduction from Hamiltonian cycle problem where $f(v)$>= n/{log^{1+epsilon}} n(epsilon>0) for each vertex v. This implies there does not exist a polynomial time algorithm for the problem unless ETH is false. Thus, this infinite class of problems parameterized by $epsilon$ is in NP-Intermediate. |
