Exponential-Time Algorithms and Complexity of NP-Hard Graph Problems

NP-hard problems are deemed highly unlikely to be solvable in polynomial time. Still, one can often find algorithms that are substantially faster than brute force solutions. This thesis concerns such algorithms for problems from graph theory; techniques for constructing and improving this type of algorithms, as well as investigations into how far such improvements can get under reasonable assumptions.
     The first part is concerned with detection of cycles in graphs, especially parameterized generalizations of Hamiltonian cycles. A remarkably simple Monte Carlo algorithm is presented for the problem of finding a cycle through a specified subset of vertices or edges. The running time is exponential only in the number k of specified elements, with a dependence of 2^k. Previously, the best upper bound for this problem was doubly exponential in k¹⁰. The algorithm never reports a false positive, and with high probability any found solution is shortest possible. Moreover, the algorithm can be used to find a cycle of given parity through the specified elements.
     The second part concerns the hardness of problems encoded as evaluations of the Tutte polynomial at some fixed point in the rational plane, referred to as the Tutte plane in this context. Under the Exponential Time Hypothesis, which claims a certain exponential-time requirement for solving the problem 3-Sat, superpolynomial lower bounds are given for problems restricted to simple or planar graphs. The restriction to simple graphs has been studied previously and lower bounds exist for most of the Tutte plane; the contribution here is a first result for points on the line corresponding to computation of all-terminal network reliability. For these points, a novel reduction provides a lower bound that is asymptotically tight up to a polylogarithmic factor in the exponent. For planar graphs, lower bounds are found by examining and combining existing reductions. An asymptotically tight bound is found for points corresponding to evaluation of the 3-state Potts model partition function; for remaining points the obtained lower bounds are significantly further from the best known upper bound. These are the first results of this type for planar graphs, to the best of the knowledge of the author. Along one particular line in the Tutte plane this is also the first such result for general graphs.