Exact Covers via DeterminantsReportar como inadecuado

Exact Covers via Determinants - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Department of Computer Science Lund

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^nk-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.

Keywords : moderately exponential time algorithms exact set cover k-dimensional matching

Autor: Andreas Björklund -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados