[Zurück]

R. Ganian, N. Narayanaswamy, S. Ordyniak, C. Rahul, M. S. Ramanujan:
"On the Complexity Landscape of Connected f-Factor Problems*";
Vortrag: International Symposium on Mathematical Foundations of Computer Science (MFCS), Krakau, Polen; 22.08.2016 - 26.08.2016; in: "Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science", (2016), ISBN: 978-3-95977-016-3; S. 1 - 14.

Given an n-vertex graph G and a function f from V(G) to {0,...,n-1}, an f-factor is a subgraph H of G such that deg_H(v) = f(v) for every vertex v in V(G); we say that H is a connected f-factor if, in addition, the subgraph H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize Hamiltonian Cycle and hence is NP-complete. In fact, the Connected f-Factor problem remains NP-complete even when f(v) is at least n to the power of epsilon for each vertex v and epsilon < 1; on the other side of the spectrum, the problem was known to be polynomial-time solvable when f(v) is at least n divided by 3 for every vertex v. In this paper, we extend this line of work and obtain new complexity results based on restricting the function f. In particular, we show that when f(v) is required to be at least n divided by ((log n) to the power of c), the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c is at most 1. We also show that when c > 1, the problem is NP-intermediate.

http://publik.tuwien.ac.at/files/publik_254755.pdf