All reports by Author Martin Wahlén:

__
TR10-078
| 27th April 2010
__

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

Revisions: 1

__
TR04-039
| 21st April 2004
__

Andrzej Lingas, Martin Wahlén#### On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems

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

Andrzej Lingas, Martin Wahlén

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>