Ganian, Robert ;
Narayanaswamy, N. S. ;
Ordyniak, Sebastian ;
Rahul, C. S. ;
Ramanujan, M. S.
On the Complexity Landscape of Connected fFactor Problems
Abstract
Given an nvertex graph G and a function f:V(G) > {0, ..., n1}, an ffactor 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 ffactor 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 ffactor. However, checking for the presence of a connected ffactor is easily seen to generalize Hamiltonian Cycle and hence is NPcomplete. In fact, the Connected fFactor problem remains NPcomplete even when f(v) is at least n^epsilon for each vertex v and epsilon<1; on the other side of the spectrum, the problem was known to be polynomialtime solvable when f(v) is at least n/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/(log n)^c, the problem can be solved in quasipolynomial time in general and in randomized polynomial time if c <= 1. We also show that when c>1, the problem is NPintermediate.
BibTeX  Entry
@InProceedings{ganian_et_al:LIPIcs:2016:6501,
author = {Robert Ganian and N. S. Narayanaswamy and Sebastian Ordyniak and C. S. Rahul and M. S. Ramanujan},
title = {{On the Complexity Landscape of Connected fFactor Problems}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {41:141:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6501},
URN = {urn:nbn:de:0030drops65013},
doi = {10.4230/LIPIcs.MFCS.2016.41},
annote = {Keywords: ffactors, connected ffactors, quasipolynomial time algorithms, randomized algorithms}
}
19.08.2016
Keywords: 

ffactors, connected ffactors, quasipolynomial time algorithms, randomized algorithms 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

19.08.2016 