Publication details
On the Complexity Landscape of Connected f-Factor Problems
| Authors | |
|---|---|
| Year of publication | 2019 |
| Type | Article in Periodical |
| Magazine / Source | Algorithmica |
| MU Faculty or unit | |
| Citation | |
| Web | https://doi.org/10.1007/s00453-019-00546-z |
| Doi | http://dx.doi.org/10.1007/s00453-019-00546-z |
| Keywords | Parameterized Complexity |
| Description | 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 |