Advanced

Algorithmic Bounds for Presumably Hard Combinatorial Problems

Björklund, Andreas LU (2007)
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Professor Fomin, Fedor, University of Bergen, Norway
organization
publishing date
type
Thesis
publication status
published
subject
keywords
numerisk analys, system, control, Datalogi, numerical analysis, systems, Computer science, Approximation algorithms, Exact algorithms, NP-hard problems, Algorithm theory, kontroll
pages
71 pages
publisher
Datavetenskap LTH
defense location
E:1406, E-huset, Ole Römers väg 3, Lunds Tekniska Högskola, Lund
defense date
2007-01-19 13:15
ISSN
1404-1219
ISBN
91-628-7030-0
language
English
LU publication?
yes
id
91a7594b-95d1-4741-a065-4c3470393e46 (old id 547846)
date added to LUP
2007-10-09 09:45:19
date last changed
2016-09-19 08:44:53
@phdthesis{91a7594b-95d1-4741-a065-4c3470393e46,
  abstract     = {In this thesis we present new worst case computational bounds on algorithms for some of the most well-known<br/><br>
<br/><br>
NP-complete and #P-complete problems and their optimization variants. We consider graph<br/><br>
<br/><br>
problems like Longest Path, Maximum Cut, Number of Perfect Matchings, Chromatic and Domatic Number,<br/><br>
<br/><br>
as well as Maximum k-Satisfiability and Set Cover.<br/><br>
<br/><br>
Our results include<br/><br>
<br/><br>
I a) There is a polynomial--time algorithm always finding a path of length Omega((log n/ log log n)^2)<br/><br>
<br/><br>
in directed Hamiltonian graphs of constant bounded degree on n vertices. In undirected graphs on<br/><br>
<br/><br>
$n$ vertices with a long path of length L we give a polynomial--time algorithm finding<br/><br>
<br/><br>
Omega((log L/ log log L)^2) long paths.<br/><br>
<br/><br>
The technique used is a novel graph decomposition which<br/><br>
<br/><br>
inspired Hal Gabow to find the strongest approximation algorithm for Longest Path in undirected graphs<br/><br>
<br/><br>
known to date.<br/><br>
<br/><br>
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<br/><br>
<br/><br>
for any non-decreasing function f(n) which is omega(1) and computable in subexponential time<br/><br>
<br/><br>
in directed Hamiltonian graphs of constant bounded degree on n vertices,<br/><br>
<br/><br>
unless there are 2^{o(n)} time deterministic algorithms for n-variable 3SAT.<br/><br>
<br/><br>
II a) There is a PTAS for MAXCUT on d-regular unweighted graphs on n vertices,<br/><br>
<br/><br>
containing O(d^4 log n) simple 4-cycles, for $d$ of omega(sqrt{n log n}).<br/><br>
<br/><br>
In particular, there is always a PTAS for d of Omega(n/log n) regardless of the number of 4-cycles.<br/><br>
<br/><br>
Moreover, MAXkSAT on n variables for constant k can be approximated in polynomial time with an absolute error of<br/><br>
<br/><br>
(epsilon+o(1))n^ksqrt{log log n/log n} for any fixed epsilon&gt;0.<br/><br>
<br/><br>
The techniques used are low rank approximations, exhaustive search in few dimensions, and linear programming.<br/><br>
<br/><br>
II b) There is no PTAS for MAXCUT on unweighted graphs on n vertices of average degree delta<br/><br>
<br/><br>
for any delta less than n/(log n(log log n)^{omega(1)}),<br/><br>
<br/><br>
unless there are 2^{o(n)} time randomized algorithms for n-variable 3SAT.<br/><br>
<br/><br>
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<br/><br>
<br/><br>
number of covers of U in k pieces from S in time 2^nn^{O(1)} for any k<br/><br>
<br/><br>
as long as S is enumerable in that time bound.<br/><br>
<br/><br>
In particular the chromatic polynomial of a graph can be computed in time O(2^nn^3).<br/><br>
<br/><br>
The Chromatic Number in an n-vertex graph can be computed in time O(2.2461^n) using<br/><br>
<br/><br>
only polynomial space.<br/><br>
<br/><br>
The technique used is counting over an inclusion--exclusion formula.},
  author       = {Björklund, Andreas},
  isbn         = {91-628-7030-0},
  issn         = {1404-1219},
  keyword      = {numerisk analys,system,control,Datalogi,numerical analysis,systems,Computer science,Approximation algorithms,Exact algorithms,NP-hard problems,Algorithm theory,kontroll},
  language     = {eng},
  pages        = {71},
  publisher    = {Datavetenskap LTH},
  school       = {Lund University},
  title        = {Algorithmic Bounds for Presumably Hard Combinatorial Problems},
  year         = {2007},
}