Thore Husfeldt

News

New Paper with Björklund

“Polynomial space algorithms for exact satisfiability and chromatic number”:

Abstract: We provide simple algorithms using polynomial space and O(cⁿ) time for variants of n-element set cover problems, based on divide-and-conquer and on inclusion–exclusion characterisations.

We show that the Exact Satisfiability problem of size l with m clauses can be solved in time l^O(1) 2^m, and that the Chromatic Number of an n-vertex graph can be found in time O(2.4423ⁿ). Both these algorithms require only polynomial space and admit efficient parallelizations, answering open problems in the literature.

We also argue that some weighted versions of the problems can be solved in polynomial space, still only using time singly exponential in m and n, respectively.

Finally we show that if we allow our Chromatic Number algorithm to use exponential space, the chromatic number of an n-vertex graph is found in time O(2.3236ⁿ), an improvement over the previously best algorithm running in time O(2.4023ⁿ).

A draft can be found under On-line papers. Comments are welcome.

Update: Some rewriting, extension, and improvement. And a title change to Exact algorithms for exact satisfiability and number of perfect matchings.

Update: To appear at ICALP 2006.

Tue, 20 Dec 2005 | Category: News | Permanent link