@article{bae46cc0e3de11dda259000ea68e967b,
title = "Exact algorithms for exact satisfiability and number of perfect matchings",
abstract = "We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2mlo(1) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2nno(1) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732n) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.",
keywords = "Exact Algorithms, Set Cover Problems, Divide-and-Conquer, Inclusion-Exclusion Characterizations, Counting Solutions, Exact Algorithms, Set Cover Problems, Divide-and-Conquer, Inclusion-Exclusion Characterizations, Counting Solutions",
author = "Andreas Bj{\"o}rklund and Thore Husfeldt",
note = "Thore Husfeldt arbejdede i Lund skal tilknyttes som ekstern publikation Paper id:: 10.1007/s00453-007-9149-8",
year = "2008",
doi = "10.1007/s00453-007-9149-8",
language = "English",
volume = "52",
pages = "226--249",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "2",
}