All reports by Author Thore Husfeldt:

__
TR10-078
| 27th April 2010
__

Holger Dell, Thore Husfeldt, Martin Wahlén#### Exponential Time Complexity of the Permanent and the Tutte Polynomial

Revisions: 1

__
TR06-044
| 24th January 2006
__

Andreas Björklund, Thore Husfeldt#### Inclusion-Exclusion Based Algorithms for Graph Colouring

__
TR03-032
| 16th April 2003
__

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna#### Approximating Longest Directed Path

Holger Dell, Thore Husfeldt, Martin Wahlén

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting ... more >>>

Andreas Björklund, Thore Husfeldt

We present a deterministic algorithm producing the number of

$k$-colourings of a graph on $n$ vertices in time

$2^nn^{O(1)}$.

We also show that the chromatic number can be found by a

polynomial space algorithm running in time $O(2.2461^n)$.

Finally, we present a family of ...
more >>>

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

We investigate the hardness of approximating the longest path and

the longest cycle in directed graphs on $n$ vertices. We show that

neither of these two problems can be polynomial time approximated

within $n^{1-\epsilon}$ for any $\epsilon>0$ unless

$\text{P}=\text{NP}$. In particular, the result holds for

more >>>