Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyFast Hamiltonicity Checking Via Bases of Perfect Matchings
| cris.lastimport.scopus | 2024-02-12T20:29:29Z |
| dc.abstract.en | 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 on t vertices; an entry Ht[M1, M2] is 1 if M1 and M2 form a Hamiltonian cycle and 0 otherwise. Motivated by applications for the Hamiltonicity problem, we show that Ht has rank exactly 2t/2−1 over GF(2). The upper bound is established by an explicit factorization of Ht as the product of two submatrices; the matchings labeling columns and rows, respectively, of the submatrices therefore form a basis Xt of Ht. The lower bound follows because the 2t/2−1 × 2t/2−1 submatrix with rows and columns labeled by Xt can be seen to have full rank. We obtain several algorithmic results based on the rank of Ht and the particular structure of the matchings in Xt. First, we present a 1.888n nO(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)pwnO(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 − ϵ)pwnO(1), for any ϵ > 0, would imply the breakthrough result of a (2 − ϵ′)n-time algorithm for CNF-Sat for some ϵ′ > 0. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Nederlof, Jesper |
| dc.contributor.author | Kratsch, Stefan |
| dc.contributor.author | Cygan, Marek |
| dc.date.accessioned | 2024-01-25T00:16:42Z |
| dc.date.available | 2024-01-25T00:16:42Z |
| dc.date.issued | 2018 |
| dc.description.finance | Nie dotyczy |
| dc.description.number | 3 |
| dc.description.volume | 46 |
| dc.identifier.doi | 10.1145/3148227 |
| dc.identifier.issn | 0004-5411 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/106998 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.ispartof | Journal of the ACM |
| dc.relation.pages | 1-46 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.title | Fast Hamiltonicity Checking Via Bases of Perfect Matchings |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |