Talks
Fall 2015

More Needles in the Hay Might Make it Harder to Find One?

Monday, November 2nd, 2015, 11:00 am11:30 am

Add to Calendar

We give two recent examples of algorithms that are the fastest known for their respective problem and parametrization when there are few solutions. However, as the number of solutions grows the algorithms get slower and other algorithms give the best bounds. Is this evidence that there are hard problems where uniqueness helps, or does it just mean that we haven't yet found the best algorithms for these problems? The two problems considered are directed hamiltonicity parametrized by the number of vertices, and vertex coloring in bounded degree graphs parametrized by pathwidth. These results are in stark contrast to cnf satisfiability where we know that uniqueness doesn't help, a faster exponential time algorithm for unique SAT implies a faster algorithm for general SAT.