Algorithmic Bounds for Presumably Hard Combinatorial Problems

Abstract

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.

• author: Björklund, Andreas
• supervisor: Thore Husfeldt
• opponent: Professor Fomin, Fedor, University of Bergen, Norway
• organization: Department of Computer Science; Parallel Systems
• publishing date: 2007
• type: Thesis
• publication status: published
• subject: Computer Science
• keywords: numerisk analys, system, control, Datalogi, numerical analysis, systems, Computer science, Approximation algorithms, Exact algorithms, NP-hard problems, Algorithm theory, kontroll
• pages: 71 pages
• defense location: E:1406, E-huset, Ole Römers väg 3, Lunds Tekniska Högskola, Lund
• defense date: 2007-01-19 13:15:00
• ISBN: 91-628-7030-0
• language: English
• LU publication?: yes
• id: 91a7594b-95d1-4741-a065-4c3470393e46 (old id 547846)
• date added to LUP: 2016-04-01 15:38:28
• date last changed: 2021-05-06 17:20:04