Algorithmic Bounds for Presumably Hard Combinatorial Problems
(2007) Abstract
 In this thesis we present new worst case computational bounds on algorithms for some of the most wellknown
NPcomplete and #Pcomplete 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 kSatisfiability and Set Cover.
Our results include
I a) There is a polynomialtime 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 wellknown
NPcomplete and #Pcomplete 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 kSatisfiability and Set Cover.
Our results include
I a) There is a polynomialtime 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 polynomialtime 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 nondecreasing 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 nvariable 3SAT.
II a) There is a PTAS for MAXCUT on dregular unweighted graphs on n vertices,
containing O(d^4 log n) simple 4cycles, 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 4cycles.
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 nvariable 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 nvertex graph can be computed in time O(2.2461^n) using
only polynomial space.
The technique used is counting over an inclusionexclusion formula. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/547846
 author
 Björklund, Andreas ^{LU}
 supervisor

 Thore Husfeldt ^{LU}
 opponent

 Professor Fomin, Fedor, University of Bergen, Norway
 organization
 publishing date
 2007
 type
 Thesis
 publication status
 published
 subject
 keywords
 numerisk analys, system, control, Datalogi, numerical analysis, systems, Computer science, Approximation algorithms, Exact algorithms, NPhard problems, Algorithm theory, kontroll
 pages
 71 pages
 publisher
 Datavetenskap LTH
 defense location
 E:1406, Ehuset, Ole Römers väg 3, Lunds Tekniska Högskola, Lund
 defense date
 20070119 13:15
 ISSN
 14041219
 ISBN
 9162870300
 language
 English
 LU publication?
 yes
 id
 91a7594b95d14741a0654c3470393e46 (old id 547846)
 date added to LUP
 20071009 09:45:19
 date last changed
 20160919 08:44:53
@phdthesis{91a7594b95d14741a0654c3470393e46, abstract = {In this thesis we present new worst case computational bounds on algorithms for some of the most wellknown<br/><br> <br/><br> NPcomplete and #Pcomplete 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 kSatisfiability and Set Cover.<br/><br> <br/><br> Our results include<br/><br> <br/><br> I a) There is a polynomialtime 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 polynomialtime 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 nondecreasing 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 nvariable 3SAT.<br/><br> <br/><br> II a) There is a PTAS for MAXCUT on dregular unweighted graphs on n vertices,<br/><br> <br/><br> containing O(d^4 log n) simple 4cycles, 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 4cycles.<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>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 nvariable 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 nvertex 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 inclusionexclusion formula.}, author = {Björklund, Andreas}, isbn = {9162870300}, issn = {14041219}, keyword = {numerisk analys,system,control,Datalogi,numerical analysis,systems,Computer science,Approximation algorithms,Exact algorithms,NPhard problems,Algorithm theory,kontroll}, language = {eng}, pages = {71}, publisher = {Datavetenskap LTH}, school = {Lund University}, title = {Algorithmic Bounds for Presumably Hard Combinatorial Problems}, year = {2007}, }