# Exponential-time algorithm

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

\begin{question} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. Is there an algorithm that decides, for input graphs $G$ and $H$, whether there exists a homomorphism from $G$ to $H$ in time $O(c^{|V(G)|+|V(H)|})$ for some constant $c$? \end{question}

Keywords: algorithm; Exponential-time algorithm; homomorphism

## Exponential Algorithms for Knapsack ★★

Author(s): Lipton

\begin{conjecture} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. The famous 0-1 Knapsack problem is: Given $a_{1},a_{2},\dots,a_{n}$ and $b$ integers, determine whether or not there are $0-1$ values $x_{1},x_{2},\dots,x_{n}$ so that $$ \sum_{i=1}^{n} a_{i}x_{i} = b.$$ The best known worst-case algorithm runs in time $2^{n/2}$ times a polynomial in $n$. Is there an algorithm that runs in time $2^{n/3}$?

\end{conjecture}

Keywords: Algorithm construction; Exponential-time algorithm; Knapsack