Advanced

Exact algorithms for exact satisfiability and number of perfect matchings

Björklund, Andreas LU and Husfeldt, Thore LU (2008) In Algorithmica 52(2). p.226-249
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 2(m)l(O(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 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) 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.... (More)
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 2(m)l(O(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 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) 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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
exact algorithms, set partition, exact satisfability, number, of perfect matchings, set cover
in
Algorithmica
volume
52
issue
2
pages
226 - 249
publisher
Springer
external identifiers
  • wos:000258717200008
  • scopus:50849086130
ISSN
0178-4617
DOI
10.1007/s00453-007-9149-8
project
Exact algorithms
language
English
LU publication?
yes
id
c9b512bf-d79f-40b5-b1e9-ce1ad5ab422e (old id 1249695)
date added to LUP
2008-11-06 12:37:47
date last changed
2017-09-10 03:39:48
@article{c9b512bf-d79f-40b5-b1e9-ce1ad5ab422e,
  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 2(m)l(O(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 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) 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.},
  author       = {Björklund, Andreas and Husfeldt, Thore},
  issn         = {0178-4617},
  keyword      = {exact algorithms,set partition,exact satisfability,number,of perfect matchings,set cover},
  language     = {eng},
  number       = {2},
  pages        = {226--249},
  publisher    = {Springer},
  series       = {Algorithmica},
  title        = {Exact algorithms for exact satisfiability and number of perfect matchings},
  url          = {http://dx.doi.org/10.1007/s00453-007-9149-8},
  volume       = {52},
  year         = {2008},
}