Algorithmic Bounds for Presumably Hard Combinatorial Problems
Author
Summary, in English
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.
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.
Department/s
Publishing year
2007
Language
English
Document type
Dissertation
Publisher
Datavetenskap LTH
Topic
- Computer Science
Keywords
- numerisk analys
- system
- control
- Datalogi
- numerical analysis
- systems
- Computer science
- Approximation algorithms
- Exact algorithms
- NP-hard problems
- Algorithm theory
- kontroll
Status
Published
Supervisor
ISBN/ISSN/Other
- ISBN: 91-628-7030-0
Defence date
19 January 2007
Defence time
13:15
Defence place
E:1406, E-huset, Ole Römers väg 3, Lunds Tekniska Högskola, Lund
Opponent
- Fedor Fomin (Professor)