Paper Info
Title
On the Complexity Landscape of Connected <Emphasis Type="Italic">f</Emphasis>-Factor Problems
Abstract
Let G be an undirected simple graph having n vertices and let $$f:V(G)\rightarrow \{0,\dots , n-1\}$$f:V(G)?{0,?,n-1} be a function. An f-factor of G is a spanning subgraph H such that $$d_H(v)=f(v)$$dH(v)=f(v) for every vertex $$v\in V(G)$$v?V(G). The subgraph H is called a connected f-factor if, in addition, H is connected. A classical result of Tutte (Can J Math 6(1954):347---352, 1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connectedf-factor is easily seen to generalize Hamiltonian Cycle and hence is $$\mathsf {NP}$$NP-complete. In fact, the Connected f -Factor problem remains $$\mathsf {NP}$$NP-complete even when we restrict f(v) to be at least $$n^{\epsilon }$$n∈ for each vertex v and constant $$0\le \epsilon <1$$0≤∈<1; on the other side of the spectrum of nontrivial lower bounds on f, the problem is known to be polynomial time solvable when f(v) is at least $$\frac{n}{3}$$n3 for every vertex v. In this paper, we extend this line of work and obtain new complexity results based on restrictions on the function f. In particular, we show that when f(v) is restricted to be at least $$\frac{n}{(\log n)^c}$$n(logn)c, the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if $$c\le 1$$c≤1. Furthermore, we show that when $$c>1$$c>1, the problem is $$\mathsf {NP}$$NP-intermediate.
Year
DOI
Venue
2019
10.1007/s00453-019-00546-z
Algorithmica
Keywords
DocType
Volume
Connected f-factors, Quasi-polynomial time algorithms, Randomized algorithms, $$\mathsf {NP}$$NP-intermediate, Exponential time hypothesis
Journal
81
Issue
ISSN
Citations 
6
1432-0541
0
PageRank 
References 
Authors
0.34
7
5
Name
Order
Citations
PageRank
Robert Ganian120840.19
N. S. Narayanaswamy215127.01
Sebastian Ordyniak317630.27
C. S. Rahul422.43
M. S. Ramanujan522228.33