# Exponential-time algorithm

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

**Question**

Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?

Keywords: algorithm; Exponential-time algorithm; homomorphism

## Exponential Algorithms for Knapsack ★★

Author(s): Lipton

**Conjecture**

The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?

Keywords: Algorithm construction; Exponential-time algorithm; Knapsack