Exact Covers via Determinants

Abstract : Given a k-uniform hypergraph on n vertices, partitioned in k equal parts such that every hyperedge includes one vertex from each part, the k-dimensional matching problem asks whether there is a disjoint collection of the hyperedges which covers all vertices. We show it can be solved by a randomized polynomial space algorithm in time O*(2^(n(k-2)/k)). The O*() notation hides factors polynomial in n and k. When we drop the partition constraint and permit arbitrary hyperedges of cardinality k, we obtain the exact cover by k-sets problem. We show it can be solved by a randomized polynomial space algorithm in time O*(c_k^n), where c_3=1.496, c_4=1.642, c_5=1.721, and provide a general bound for larger k. Both results substantially improve on the previous best algorithms for these problems, especially for small k, and follow from the new observation that Lovasz' perfect matching detection via determinants (1979) admits an embedding in the recently proposed inclusion-exclusion counting scheme for set covers, despite its inability to count the perfect matchings.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.95-106, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455349
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 10:51:51
Dernière modification le : mercredi 10 février 2010 - 11:26:11
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:53:22

Fichier

bjorklund.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455349, version 1

Collections

Citation

Andreas Björklund. Exact Covers via Determinants. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.95-106, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455349〉

Partager

Métriques

Consultations de la notice

138

Téléchargements de fichiers

139