Name
Abstract | ||
|---|---|---|
Given an undirected graph G = (V, E) with n vertices, and a function f : V -> N, we consider the problem of finding a connected f -factor in G. In this work we design an algorithm to check for the existence of a connected f -factor, for the case where f (v) >= n/g(n), for all v in V and g(n) is polylogarithmic in n. The running time of our algorithm is O(n^{2g(n)}. As a consequence of this algorithm we conclude that the complexity of connected f -factor for the case we consider is unlikely to be NP-Complete unless the Exponential Time Hypothesis (ETH) is false. Secondly, under the assumption of the ETH, we show that it is also unlikely to be in P for g(n) in O((log n)^{1+eps} ) for any eps> 0. Therefore, our results show that for all eps> 0, connected f -factor for f (v) >= n/O(log n)^{1+eps}) is in NP-Intermediate unless the ETH is false. Further, for any constant c > 0, when g(n) = c, our algorithm for connected f -factor runs in polynomial time. Finally, we extend our algorithm to compute a minimum weight connected f -factor in edge weighted graphs in the same asymptotic time bounds. |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Binary logarithm,Discrete mathematics,Graph,Combinatorics,F-factor,Vertex (geometry),Minimum weight,Time complexity,Mathematics,Exponential time hypothesis |
DocType | Volume | Citations |
Journal | abs/1507.07856 | 0 |
PageRank | References | Authors |
0.34 | 3 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| N. S. Narayanaswamy | 1 | 151 | 27.01 |
| C. S. Rahul | 2 | 2 | 2.43 |