GANIAN, Robert, N. S. NARAYANASWAMY, Sebastian ORDYNIAK, C. S. RAHUL and M. S. RAMANUJAN. On the Complexity Landscape of Connected f-Factor Problems. In Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier. 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26. Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. p. "41:1"-"41:14", 14 pp. ISBN 978-3-95977-016-3. doi:10.4230/LIPIcs.MFCS.2016.41. 2016.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name On the Complexity Landscape of Connected f-Factor Problems
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), N. S. NARAYANASWAMY (356 India), Sebastian ORDYNIAK (40 Austria), C. S. RAHUL (356 India) and M. S. RAMANUJAN (356 India).
Edition Germany, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, p. "41:1"-"41:14", 14 pp. 2016.
Publisher Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/16:00093949
Organization unit Faculty of Informatics
ISBN 978-3-95977-016-3
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.41
Keywords in English algorithms; vertex deletion problems
Tags core_A, firank_A
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 12/5/2017 04:21.
Abstract
Given an n-vertex graph G and a function f:V(G) -> {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^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/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 quasi-polynomial time in general and in randomized polynomial time if c <= 1. We also show that when c>1, the problem is NP-intermediate.
PrintDisplayed: 28/3/2024 13:29