Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR06-044 | 24th January 2006
Andreas Björklund, Thore Husfeldt

Inclusion-Exclusion Based Algorithms for Graph Colouring

We present a deterministic algorithm producing the number of
$k$-colourings of a graph on $n$ vertices in time
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 >>>

TR03-032 | 16th April 2003
Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

Approximating Longest Directed Path

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 >>>

ISSN 1433-8092 | Imprint