Algorithmic Bounds for Presumably Hard Combinatorial Problems

Sammanfattning: In this thesis we present new worst case computational bounds on algorithms for some of the most well-known NP-complete and #P-complete problems and their optimization variants. We consider graph problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number, as well as Maximum k-Satisfiability and Set Cover. Our results include I a) There is a polynomial--time algorithm always finding a path of length Omega((log n/ log log n)^2) in directed Hamiltonian graphs of constant bounded degree on n vertices. In undirected graphs on $n$ vertices with a long path of length L we give a polynomial--time algorithm finding Omega((log L/ log log L)^2) long paths. The technique used is a novel graph decomposition which inspired Hal Gabow to find the strongest approximation algorithm for Longest Path in undirected graphs known to date. I b) You cannot always in polynomial time find simple paths of length f(n) log^2 n or cycles of length f(n)log n for any non-decreasing function f(n) which is omega(1) and computable in subexponential time in directed Hamiltonian graphs of constant bounded degree on n vertices, unless there are 2^{o(n)} time deterministic algorithms for n-variable 3SAT. II a) There is a PTAS for MAXCUT on d-regular unweighted graphs on n vertices, containing O(d^4 log n) simple 4-cycles, for $d$ of omega(sqrt{n log n}). In particular, there is always a PTAS for d of Omega(n/log n) regardless of the number of 4-cycles. Moreover, MAXkSAT on n variables for constant k can be approximated in polynomial time with an absolute error of (epsilon+o(1))n^ksqrt{log log n/log n} for any fixed epsilon>0. The techniques used are low rank approximations, exhaustive search in few dimensions, and linear programming. II b) There is no PTAS for MAXCUT on unweighted graphs on n vertices of average degree delta for any delta less than n/(log n(log log n)^{omega(1)}), unless there are 2^{o(n)} time randomized algorithms for n-variable 3SAT. III) For any family S of subsets S_1,...,S_m of a ground set U of size n it is possible to count the number of covers of U in k pieces from S in time 2^nn^{O(1)} for any k as long as S is enumerable in that time bound. In particular the chromatic polynomial of a graph can be computed in time O(2^nn^3). The Chromatic Number in an n-vertex graph can be computed in time O(2.2461^n) using only polynomial space. The technique used is counting over an inclusion--exclusion formula.