On the Complexity Landscape of Connected f-Factor Problems

D 2016

On the Complexity Landscape of Connected f-Factor Problems

GANIAN, Robert; N. S. NARAYANASWAMY; Sebastian ORDYNIAK; C. S. RAHUL; M. S. RAMANUJAN et. al.

Základní údaje

Originální název

On the Complexity Landscape of Connected f-Factor Problems

Autoři

GANIAN, Robert; N. S. NARAYANASWAMY; Sebastian ORDYNIAK; C. S. RAHUL a M. S. RAMANUJAN

Vydání

Germany, 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, od s. "41:1"-"41:14", 14 s. 2016

Nakladatel

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/16:00093949

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-016-3

ISSN

DOI

https://doi.org/10.4230/LIPIcs.MFCS.2016.41

EID Scopus

2-s2.0-85012914012

Klíčová slova anglicky

algorithms; vertex deletion problems

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 12. 5. 2017 04:21, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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.

Citovat

GANIAN, Robert; N. S. NARAYANASWAMY; Sebastian ORDYNIAK; C. S. RAHUL a M. S. RAMANUJAN. On the Complexity Landscape of Connected f-Factor Problems. Online. 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, 2016, s. "41:1"-"41:14", 14 s. ISBN 978-3-95977-016-3. Dostupné z: https://doi.org/10.4230/LIPIcs.MFCS.2016.41.

@inproceedings{1376049,
   author = {Ganian, Robert and Narayanaswamy, N. S. and Ordyniak, Sebastian and Rahul, C. S. and Ramanujan, M. S.},
   address = {Germany},
   booktitle = {41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26},
   doi = {https://doi.org/10.4230/LIPIcs.MFCS.2016.41},
   editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
   keywords = {algorithms; vertex deletion problems},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Germany},
   isbn = {978-3-95977-016-3},
   pages = {"41:1"-"41:14"},
   publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
   title = {On the Complexity Landscape of Connected f-Factor Problems},
   year = {2016}
}

TY  - CONF
ID  - 1376049
AU  - Ganian, Robert - Narayanaswamy, N. S. - Ordyniak, Sebastian - Rahul, C. S. - Ramanujan, M. S.
PY  - 2016
TI  - On the Complexity Landscape of Connected f-Factor Problems
PB  - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
CY  - Germany
SN  - 9783959770163
KW  - algorithms
KW  - vertex deletion problems
N2  - 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.
ER  -

GANIAN, Robert; N. S. NARAYANASWAMY; Sebastian ORDYNIAK; C. S. RAHUL a M. S. RAMANUJAN. On the Complexity Landscape of Connected f-Factor Problems. Online. In Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier. \textit{41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26}. Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016, s.~''41:1''-''41:14'', 14 s. ISBN~978-3-95977-016-3. Dostupné z: https://doi.org/10.4230/LIPIcs.MFCS.2016.41.

Přehled o publikaci