Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Algorithmic Bounds for Presumably Hard Combinatorial Problems

Publiceringsår: 2007
Språk: Engelska
Dokumenttyp: Doktorsavhandling
Förlag: Datavetenskap LTH


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.


E:1406, E-huset, Ole Römers väg 3, Lunds Tekniska Högskola, Lund
  • Fedor Fomin (Professor)


  • Computer Science
  • numerisk analys
  • system
  • control
  • Datalogi
  • numerical analysis
  • systems
  • Computer science
  • Approximation algorithms
  • Exact algorithms
  • NP-hard problems
  • Algorithm theory
  • kontroll


  • Thore Husfeldt
  • ISSN: 1404-1219
  • ISBN: 91-628-7030-0

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen