| Title | : | An Exploration of NP using Connected f-Factors |
| Speaker | : | Rahul C S (IITM) |
| Details | : | Tue, 15 Nov, 2016 2:00 PM @ MR1 |
| Abstract: | : | Let G = (V, E) be an undirected graph having n vertices. One of the most generic class of problems in the field of graph theory is about computing subgraphs satisfying certain constraints. We consider the problem of computing a spanning subgraph (factor) of a given graph satisfying the imposed degree and connectedness constraints. A function f : V → N defines the degree requirement and the corresponding solution is called an f -factor. With the connectedness constraint the problem is NP-complete and polynomial time solvable otherwise. We rephrase the generic connected f -factor problem as the problem of computing a connected f -factor where the degree requirement at each vertex is at least 1. If we restrict f (v) to be at least n/2 for each vertex, then the problem is polynomial time solvable while the generalized version of the problem is NP-complete. Motivated by this observation, we define a function g and a variant of the f -factor problem where the degree requirement at each vertex is at least n/g(n). We address this problem as the connected g-Bounded f -factor problem. Cheah and Corneil (1990) have shown that the problem of computing a connected d-regular spanning subgraph is NP-complete. This result implies that the connected g-Bounded f -factor problem is NP-complete when g is of the form n/d for a constant d. Our objective is to understand how the hardness of the problem is distributed over the spectrum of values of g. In our exploration of f -factors, we identify that there is a serious interplay between alternating circuits and f -factors and this being the most dominant tool used throughout our work. We use alternating circuits to construct an f -factor with desired properties starting from an arbitrary f -factor. For the case where g(n) = 2.5 we present a diameter based characterization for graphs having a connected g-Bounded f -factor. We prove that for g(n) = 2.5 if the graph has connected and disconnected f -factors then there exists an f -factor of diameter at least 3. We use this characterization to design a polynomial time algorithm for the problem. Further, we design a polynomial time algorithm for the case where g(n) = 3 and extend this algorithm for the generalized connected f -factor problem. This extended version is an iterative procedure which repeatedly computes an f -factor G ′ , such that for a given partition Q, the quotient graph G ′ /Q is connected. We show that the procedure solves the connected c-Bounded f -factor problem in polynomial time for a constant c. Furthermore, the same algorithm solves the problem in quasi-polynomial time for any g(n) in O(polylog(n)). We design a sub-exponential reduction from the Hamiltonian cycle problem to the connected g-Bounded f -factor problem for a function g(n) = (log n)1+Є and any positive constant Є. This has the implication that the problem is in NP-intermediate for g(n) = (log n)1+Є. For g(n) = log n we show that the problem is in RP. At the other end of the spectrum of values of g, we show that the problem remains NP-complete when g(n) is of the form nЄ for any constant Є between 0 and 1. For the metric minimum weighted connected f -factor problem, we present a 3-approximation algorithm which outputs a 2-edge connected solution. This algorithm is similar in spirit to the 2-approximation algorithm for the metric TSP problem. Furthermore, we present a PTAS for the metric minimum weighted connected c-Bounded f-factor problem. |
