Paper Info
Title
The Parity of Set Systems under Random Restrictions with Applications to Exponential Time Problems
Abstract
We reduce the problem of detecting the existence of an object to the problem of computing the parity of the number of objects in question. In particular, when given any non-empty set system, we prove that randomly restricting elements of its ground set makes the size of the restricted set system an odd number with significant probability. When compared to previously known reductions of this type, ours excel in their simplicity: For graph problems, restricting elements of the ground set usually corresponds to simple deletion and contraction operations, which can be encoded efficiently in most problems. We find three applications of our reductions: 1. An exponential-time algorithm: We show how to decide Hamiltonicity in directed n-vertex graphs with running time 1.9999n provided that the graph has at most 1.0385n Hamiltonian cycles. We do so by reducing to the algorithm of Bjorklund and Husfeldt (FOCS 2013) that computes the parity of the number of Hamiltonian cycles in time 1.619n. 2. A new result in the framework of Cygan et al. (CCC 2012) for analyzing the complexity of NP-hard problems under the Strong Exponential Time Hypothesis: If the parity of the number of Set Covers can be determined in time 1.9999(n), then Set Cover can be decided in the same time. 3. A structural result in parameterized complexity: We define the parameterized complexity class circle plus W[1] and prove that it is at least as hard as W[1] under randomized fpt-reductions with bounded onesided error; this is analogous to the classical result NP subset of RP circle plus P by Toda (SICOMP 1991).
Year
DOI
Venue
2015
10.1007/978-3-662-47672-7_19
Lecture Notes in Computer Science
Field
DocType
Volume
Discrete mathematics,Set cover problem,Parameterized complexity,Combinatorics,Exponential function,Hamiltonian (quantum mechanics),Hamiltonian path,Parity (mathematics),Mathematics,Exponential time hypothesis,Bounded function
Conference
9134
ISSN
Citations 
PageRank 
0302-9743
3
0.41
References 
Authors
12
3
Name
Order
Citations
PageRank
Andreas Björklund121916.65
Holger Dell222016.74
Thore Husfeldt373340.87