License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.61
URN: urn:nbn:de:0030-drops-48337
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4833/
Philip, Geevarghese ;
Ramanujan, M. S.
Vertex Exponential Algorithms for Connected f-Factors
Abstract
Given a graph G and a function f:V(G) -> [V(G)], 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. Tutte (1954) showed that one can check whether a given graph has a specified f-factor in polynomial time. However, detecting a connected f-factor is NP-complete, even when f is a constant function - a foremost example is the problem of checking whether a graph has a Hamiltonian cycle; here f is a function which maps every vertex to 2. The current best algorithm for this latter problem is due to Björklund (FOCS 2010), and runs in randomized O^*(1.657^n) time (the O^*() notation hides polynomial factors). This was the first superpolynomial improvement, in nearly fifty years, over the previous best algorithm of Bellman, Held and Karp (1962) which checks for a Hamiltonian cycle in deterministic O(2^n*n^2) time.
In this paper we present the first vertex-exponential algorithms for the more general problem of finding a connected f-factor. Our first result is a randomized algorithm which, given a graph G on n vertices and a function f:V(G) -> [n], checks whether G has a connected f-factor in O^*(2^n) time. We then extend our result to the case when f is a mapping from V(G) to {0,1} and the degree of every vertex v in the subgraph H is required to be f(v)(mod 2). This generalizes the problem of checking whether a graph has an Eulerian subgraph; this is a connected subgraph whose degrees are all even (f(v) equiv 0). Furthermore, we show that the min-cost editing and edge-weighted versions of these problems can be solved in randomized O^*(2^n) time as long as the costs/weights are bounded polynomially in n.
BibTeX - Entry
@InProceedings{philip_et_al:LIPIcs:2014:4833,
author = {Geevarghese Philip and M. S. Ramanujan},
title = {{Vertex Exponential Algorithms for Connected f-Factors}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {61--71},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-77-4},
ISSN = {1868-8969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4833},
URN = {urn:nbn:de:0030-drops-48337},
doi = {10.4230/LIPIcs.FSTTCS.2014.61},
annote = {Keywords: Exact Exponential Time Algorithms, f-Factors}
}
|
Keywords: |
|
Exact Exponential Time Algorithms, f-Factors |
|
Collection: |
|
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
12.12.2014 |
