research-article

Fast Hamiltonicity Checking Via Bases of Perfect Matchings

Authors:

Stefan Kratsch,

Jesper NederlofAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 3

Article No.: 12, Pages 1 - 46

https://doi.org/10.1145/3148227

Published: 13 March 2018 Publication History

Abstract

For an even integer t ≥ 2, the Matching Connectivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph on t vertices; an entry H_t[M₁, M₂] is 1 if M₁ and M₂ form a Hamiltonian cycle and 0 otherwise. Motivated by applications for the Hamiltonicity problem, we show that H_t has rank exactly 2^t/2−1 over GF(2). The upper bound is established by an explicit factorization of H_t as the product of two submatrices; the matchings labeling columns and rows, respectively, of the submatrices therefore form a basis X_t of H_t. The lower bound follows because the 2^t/2−1 × 2^t/2−1 submatrix with rows and columns labeled by X_t can be seen to have full rank.

We obtain several algorithmic results based on the rank of H_t and the particular structure of the matchings in X_t. First, we present a 1.888ⁿ n^O(1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Second, we give a Monte Carlo algorithm that solves the problem in (2 + √ 2)^pwn^O(1) time when provided with a path decomposition of width pw for the input graph. Moreover, we show that this algorithm is best possible under the Strong Exponential Time Hypothesis, in the sense that an algorithm with running time (2 + √2 − ϵ)^pwn^O(1), for any ϵ > 0, would imply the breakthrough result of a (2 − ϵ^′)ⁿ-time algorithm for CNF-Sat for some ϵ^′ > 0.

References

[1]

Sanjeev Arora. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 5 (Sept. 1998), 753--782.

Digital Library

[2]

Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press. Retrieved from http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.

Digital Library

[3]

Eric T. Bax. 1993. Inclusion and exclusion algorithm for the Hamiltonian path problem. Inform. Process. Lett. 47, 4 (1993), 203--207.

Digital Library

[4]

Richard E. Bellman. 1958. Combinatorial processes and dynamic programming. Rand Corporation.

[5]

Richard E. Bellman. 1962. Dynamic programming treatment of the travelling salesman problem. J. ACM 9, 1 (1962), 61--63.

Digital Library

[6]

Andreas Björklund. 2014. Determinant sums for undirected hamiltonicity. SIAM J. Comput. 43, 1 (2014), 280--299.

Digital Library

[7]

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2010. Trimmed Möbius inversion and graphs of bounded degree. Theory Comput. Syst. 47, 3 (2010), 637--654.

Digital Library

[8]

Hans L. Bodlaender. 2007. Treewidth: Structure and algorithms. In Structural Information and Communication Complexity, Giuseppe Prencipe and Shmuel Zaks (Eds.). Lecture Notes in Computer Science, Vol. 4474. Springer, Berlin, 11--25.

Digital Library

[9]

Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. 2015. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243 (2015), 86--111.

Digital Library

[10]

Hans L. Bodlaender and Arie M. C. A. Koster. 2008. Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51, 3 (2008), 255--269.

Digital Library

[11]

Hajo Broersma, Fedor V. Fomin, Pim van’t Hof, and Daniël Paulusma. 2009. Fast exact algorithms for hamiltonicity in claw-free graphs. In WG (Lecture Notes in Computer Science), Christophe Paul and Michel Habib (Eds.), Vol. 5911. 44--53.

Digital Library

[12]

Nicos Christofides. 1976. Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Technical Report 388. Graduate School of Industrial Administration, Carnegie Mellon University.

[13]

Bruno Courcelle. 1990. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85, 1 (1990), 12--75.

Digital Library

[14]

Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. 2016. On problems as hard as CNF-SAT. ACM Trans. Algorithms 12, 3 (2016), 41.

Digital Library

[15]

Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. 2011. Solving connectivity problems parameterized by treewidth in single exponential time. In FOCS, Rafail Ostrovsky (Ed.). IEEE, 150--159. http://ieeexplore.ieee.org/document/6108160/?reload=true.

Digital Library

[16]

Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. 2012. Catalan structures and dynamic programming in H-minor-free graphs. J. Comput. Syst. Sci. 78, 5 (2012), 1606--1622.

Digital Library

[17]

Stuart E. Dreyfus and Robert A. Wagner. 1972. The Steiner problem in graphs. Networks 1 (1972), 195--207.

[18]

David Eppstein. 2007. The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl. 11, 1 (2007), 61--81. Retrieved from http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf.

[19]

Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov. 2009. On two techniques of combining branching and treewidth. Algorithmica 54, 2 (2009), 181--207.

Digital Library

[20]

Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer-Verlag New York, New York.

Digital Library

[21]

Heidi Gebauer. 2011. Enumerating all hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs. Electr. J. Comb. 18, 1 (2011). Retrieved from http://www.combinatorics.org/Volume_18/Abstracts/v18i1p132.html.

[22]

Mika Göös and Jukka Suomela. 2011. Locally checkable proofs. In PODC, Cyril Gavoille and Pierre Fraigniaud (Eds.). ACM, 159--168.

Digital Library

[23]

Michael Held and Richard M. Karp. 1961. A dynamic programming approach to sequencing problems. In Proceedings of the 1961 16th ACM National Meeting (ACM’61). ACM, New York, 71.201--71.204.

Digital Library

[24]

Illya V. Hicks, Arie M. C. A. Koster, and Elif Kolotoǧlu. 2005. Branch and tree decomposition techniques for discrete optimization. Tutorials Oper Res 2005 (2005), 1--19.

[25]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 4 (2001), 512--530.

Digital Library

[26]

Kazuo Iwama and Takuya Nakashima. 2007. An improved exact algorithm for cubic graph TSP. In Proceedings of the 13th Annual International Conference on Computing and Combinatorics (COCOON’07) (Lecture Notes in Computer Science), Guohui Lin (Ed.), Vol. 4598. Springer, 108--117.

Digital Library

[27]

Richard M. Karp. 1982. Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1 (1982), 49--51.

Digital Library

[28]

Jon Kleinberg and Éva Tardos. 2005. Algorithm Design. Addison-Wesley 2006, pp. I-XXIII, 1--838.

Digital Library

[29]

Ton Kloks. 1994. Treewidth, Computations and Approximations. Lecture Notes in Computer Science, Vol. 842. Springer.

[30]

Samuel Kohn, Allan Gottlieb, and Meryle Kohn. 1977. A generating function approach to the traveling salesman problem. In Proceedings of the 1977 Annual Conference (ACM’77). ACM, New York, 294--300.

Digital Library

[31]

Shen Lin and Brian W. Kernighan. 1973. An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21, 2 (1973), 498--516. Retrieved from http://www.jstor.org/stable/169020.

Digital Library

[32]

Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. 2011. Known algorithms on graphs on bounded treewidth are probably optimal. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’11), Dana Randall (Ed.). SIAM, 777--789.

Digital Library

[33]

Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. 1987. Matching is as easy as matrix inversion. Combinatorica 7, 1 (1987), 105--113.

Digital Library

[34]

Rolf Niedermeier. 2002. Invitation to Fixed-Parameter Algorithms. Oxford University Press.

[35]

Mihai Patrascu and Ryan Williams. 2010. On the possibility of faster SAT algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’10), Moses Charikar (Ed.). SIAM, 1065--1075.

Digital Library

[36]

Ran Raz and Boris Spieker. 1995. On the “log rank”-conjecture in communication complexity. Combinatorica 15, 4 (1995), 567--588.

[37]

Neil Robertson and Paul D. Seymour. 1984. Graph minors. III. Planar tree-width. J. Comb. Theory 36, 1 (1984), 49--64.

[38]

Gerhard J. Woeginger. 2001. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization (Lecture Notes in Computer Science), Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi (Eds.), Vol. 2570. Springer, 185--208.

Digital Library

Cited By

Włodarczyk M(2025)Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by TreewidthAlgorithmica10.1007/s00453-025-01293-0Online publication date: 29-Jan-2025
https://doi.org/10.1007/s00453-025-01293-0
Lampis MVasilakis M(2024)Structural Parameterizations for Two Bounded Degree Problems RevisitedACM Transactions on Computation Theory10.1145/366515616:3(1-51)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3665156
Björklund AKaski PMohar BShinkar IO'Donnell R(2024)The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both TrueProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649656(859-870)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649656
Show More Cited By

Index Terms

Fast Hamiltonicity Checking Via Bases of Perfect Matchings
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Matchings and factors
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
    2. Parameterized complexity and exact algorithms

Recommendations

Fast hamiltonicity checking via bases of perfect matchings
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

For an even integer t ≥ 2, the Matching Connectivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertices; an entry H_t[M₁,M₂] is 1 if M₁∪ M₂ is a Hamiltonian cycle and 0 otherwise. ...
On the complexity of some colorful problems parameterized by treewidth

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.1.The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C"v. The ...
Disconnected matchings
Abstract
In 2005, Goddard et al. (2005) [12] asked the computational complexity of determining the maximum cardinality of a matching whose vertex set induces a disconnected graph. In this paper, we answer this question. In fact, we consider the ...
Highlights
- NP-complete even for bipartite graphs, for every fixed c at least 2.
- NP-...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 65, Issue 3

June 2018

285 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3191817

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 March 2018

Accepted: 01 October 2017

Revised: 01 September 2016

Received: 01 June 2015

Published in JACM Volume 65, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Polish National Science Centre
European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program
NWO grant “Space and Time Efficient Structural Improvements of Dynamic Programming Algorithms.”

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
460
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)7

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Włodarczyk M(2025)Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by TreewidthAlgorithmica10.1007/s00453-025-01293-0Online publication date: 29-Jan-2025
https://doi.org/10.1007/s00453-025-01293-0
Lampis MVasilakis M(2024)Structural Parameterizations for Two Bounded Degree Problems RevisitedACM Transactions on Computation Theory10.1145/366515616:3(1-51)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3665156
Björklund AKaski PMohar BShinkar IO'Donnell R(2024)The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both TrueProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649656(859-870)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649656
Alkema Hde Berg Mvan der Hofstad RKisfaludi-Bak S(2024)Euclidean TSP in Narrow StripsDiscrete & Computational Geometry10.1007/s00454-023-00609-771:4(1456-1506)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00454-023-00609-7
Deligkas AMertzios GSpirakis PZamaraev V(2024)Approximate and Randomized Algorithms for Computing a Second Hamiltonian CycleAlgorithmica10.1007/s00453-024-01238-z86:9(2766-2785)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01238-z
Nederlof JPilipczuk MSwennenhuis CWęgrzycki K(2023)Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial SpaceSIAM Journal on Discrete Mathematics10.1137/22M151894337:3(1566-1586)Online publication date: 24-Jul-2023
https://doi.org/10.1137/22M1518943
de Berg MBodlaender HKisfaludi-Bak SKolay S(2023)An ETH-Tight Exact Algorithm for Euclidean TSPSIAM Journal on Computing10.1137/22M146912252:3(740-760)Online publication date: 5-Jun-2023
https://doi.org/10.1137/22M1469122
Chan TWilliams VXu YLeonardi SGupta A(2022)Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OVProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520032(1501-1514)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520032
Kowalik ŁLi SNadara WSmulewicz MWahlström M(2022)Many-visits TSP revisitedJournal of Computer and System Sciences10.1016/j.jcss.2021.09.007124:C(112-128)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.jcss.2021.09.007
Chen LTell RKhuller SVassilevska Williams V(2021)Simple and fast derandomization from very hard functions: eliminating randomness at almost no costProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451059(283-291)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451059
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents