The Parity of Set Systems under Random Restrictions with Applications to Exponential Time Problems

Andreas Björklund, Holger Dell, Thore Husfeldt

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

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.9999^n provided that the graph has at most 1.0385^n Hamiltonian cycles. We do so by reducing to the algorithm of Björklund and Husfeldt (FOCS 2013) that computes the parity of the number of Hamiltonian cycles in time 1.619^n.
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 pa- rameterized complexity class ⊕W[1] and prove that it is at least as hard as W[1] under randomized fpt-reductions with bounded one- sided error; this is analogous to the classical result NP ⊆ RP⊕P by Toda (SICOMP 1991).
Original languageEnglish
Title of host publicationProceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, (6-10 July 2015, Kyoto, Japan)
Number of pages12
PublisherSpringer
Publication date2015
Pages231-242
ISBN (Print)978-3-662-47671-0
ISBN (Electronic)978-3-662-47672-7
DOIs
Publication statusPublished - 2015
EventThe 42nd International Colloquium on Automata, Languages, and Programming - Grand Prince Hotel Kyoto, Kyoto, Japan
Duration: 6 Jul 201510 Jul 2015
Conference number: 42
http://www.kurims.kyoto-u.ac.jp/icalp2015/

Conference

ConferenceThe 42nd International Colloquium on Automata, Languages, and Programming
Number42
LocationGrand Prince Hotel Kyoto
Country/TerritoryJapan
CityKyoto
Period06/07/201510/07/2015
Internet address
SeriesLecture Notes in Computer Science
Volume9134
ISSN0302-9743

Keywords

  • Parity Computation
  • Set System Restrictions
  • Hamiltonicity
  • Parameterized Complexity
  • Exponential-Time Algorithms

Fingerprint

Dive into the research topics of 'The Parity of Set Systems under Random Restrictions with Applications to Exponential Time Problems'. Together they form a unique fingerprint.

Cite this