Exact algorithms for exact satisfiability and number of perfect matchings
(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:
https://lup.lub.lu.se/record/1249695
- author
- Björklund, Andreas LU and Husfeldt, Thore LU
- organization
- publishing date
- 2008
- 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
- 2016-04-01 12:01:10
- date last changed
- 2022-01-26 21:39:33
@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}},
keywords = {{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}},
doi = {{10.1007/s00453-007-9149-8}},
volume = {{52}},
year = {{2008}},
}