J 2019

On the Complexity Landscape of Connected f-Factor Problems

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

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 (276 Germany), C. S. RAHUL (356 India) and M. S. RAMANUJAN (356 India)

Edition

Algorithmica, Springer, 2019, 0178-4617

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

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

References:

Impact factor

Impact factor: 0.650

RIV identification code

RIV/00216224:14330/19:00113716

Organization unit

Faculty of Informatics

DOI

UT WoS

000465544600015

Keywords in English

Parameterized Complexity
Změněno: 14/5/2020 10:41, Mgr. Michal Petr

Abstract

V originále

Let G be an undirected simple graph having n vertices and let f:V(G) -> {0,…,n-1} be a function. An f-factor of G is a spanning subgraph H such that dH(v)=f(v) for every vertex v in 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 NP-complete. In fact, the CONNECTED f-FACTOR problem remains NP-complete even when we restrict f(v) to be at least n^e for each vertex v and constant 0