Refine
Keywords
- giant component (2)
- Stein’s method (1)
- colouring (1)
- complex networks (1)
- connected hypergraphs (1)
- intersection graphs (1)
- limit theorems (1)
- local limit theorems (1)
- random discrete structures (1)
- random graphs (1)
- random graphs and hypergraphs (1)
Project
- A5 (22)
Application Area
- A (22)
The Steiner tree problem is to nd a shortest subgraph
that spans a given set of vertices in a graph. This problem
is known to be NP-hard and it is well known that a polynomial time
2-approximation algorithm exists. In 1996 Zelikovsky [11] suggested
an approximation algorithm for the Steiner tree problem that is called
the relative greedy algorithm. Till today the performance ratio of this
algorithm is not known. Zelikovsky provided 1.694 as an upper bound
and Gröpl, Hougardy, Nierho and Prömel [6] proved that 1.333 is a
lower bound. In this paper we improve the lower bound for the performance
ratio of the relative greedy algorithm to 1.385.
We prove sufficient and essentially necessary conditions in terms of the
minimum degree for a graph to contain planar subgraphs with many edges.
For example, for all positive γ every sufficiently large graph G with minimum
degree at least (2/3 + γ)|G| contains a triangulation as a spanning
subgraph, whereas this need not be the case when the minimum degree is
less than 2|G|/3.
We show that it is not possible to approximate the minimum Steiner tree problem within 1+1/162 unless RP=NP. The currently best known lower bound is 1+ 1/400. The reduction is from Hastad’s nonapproximability result for maximum satisfiability of linear equation modulo 2. The improvement on the nonapproximability ratio is mainly based on the fact that our reduction does not use variable gadgets. This idea was introduced by Papadimitriou and Vempala.
Many constraint satisfaction problems have a natural formulation as a homomorphism problem. For a fixed relational structure Gamma we consider the following computational problem: Given a structure S with the same relational signature as Gamma, is there a homomorphism from S to Gamma? This problem is known as the constraint satisfaction problem CSP(Gamma) for the so-called template Gamma and is intensively studied for relational structures Gamma with a finite domain. However, many constraint satisfaction problems can not be formulated with a finite template.
If we allow arbitrary infinite templates, constraint satisfaction is very expressive. We show that it contains undecidable problems, even if the constraint language is binary. In general, a computational problem can be described as the constraint satisfaction problem of an infinite template if and only if it is closed under inverse homomorphisms and disjoint unions. It is also easy to see that we can restrict our attention to countable templates.
In this thesis we study the computational complexity of constraint satisfaction with templates that are omega-categorical. A structure Gamma is omega-categorical if all countable models of the first-order theory of Gamma are isomorphic to Gamma. This concept is central and well-studied in model-theory. On the one hand, omega-categoricity is a rather strong model-theoretic assumption on a relational structure, and we can use them to show that many techniques for constraint satisfaction with finite templates extend to omega-categorical templates.
We investigate properties of a certain countably infinite graph called the
infinite locally random graph, written R_N. The graph R_N arises in the study
of models for massive, self-organizing networks like the web-graph. We
characterize the isomorphism type of R_N as the limit of a random process, and
via a domination elimination ordering. We prove that R_N satisfies vertex
deletion properties generalizing inexhaustibility. As is the case for the
infinite random graph R, R_N has a universal automorphism group and
endomorphism monoid. Unlike R, R_N isometrically embeds all finite graphs.