Fast Hamiltonicity checking via bases of perfect matchings

M. Cygan, S. Kratsch, J. Nederlof

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

48 Citations (Scopus)
2 Downloads (Pure)

Abstract

For an even integer t = 2, the Matching Connectivity matrix Ht is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph Kt on t vertices; an entry Ht[M1,M2] is 1 if M1¿ M2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of Ht: We first show that Ht has rank exactly 2t/2-1 over GF(2) via an appropriate factorization that explicitly provides families of matchings Xt forming bases for Ht. Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings Xt induce permutation matrices within Ht. We use the factorization to derive an 1.888n nO(1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles modulo two in directed bipartite or undirected graphs in the same time bound. Moreover, we use the fast basis change algorithm from the second result to present a Monte Carlo algorithm that given an undirected graph on n vertices along with a path decomposition of width at most pw decides Hamiltonicity in (2+v2)pw nO(1) time. Finally, we use the third result to show that for every e >0 this cannot be improved to (2+v2-e)pwnO(1) time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of an O((2-e')n) time algorithm for CNF-Sat.
Original languageEnglish
Title of host publicationForty-fifth Annual ACM Symposium on Theory of Computing (STOCS'13, Palo Alto CA, USA, June 1-4, 2013)
EditorsD. Boneh, T. Roughgarden, J. Feigenbaum
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages301-310
ISBN (Print)978-1-4503-2029-0
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event45th ACM Symposium on the Theory of Computing (STOC 2013), June 1-4, 2013, Palo Alto, CA, USA - Palo Alto, CA, United States
Duration: 1 Jun 20134 Jun 2013
http://theory.stanford.edu/stoc2013/

Conference

Conference45th ACM Symposium on the Theory of Computing (STOC 2013), June 1-4, 2013, Palo Alto, CA, USA
Abbreviated titleSTOC 2013
CountryUnited States
CityPalo Alto, CA
Period1/06/134/06/13
Internet address

Fingerprint Dive into the research topics of 'Fast Hamiltonicity checking via bases of perfect matchings'. Together they form a unique fingerprint.

Cite this