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)
Project
- A5 (22)
Application Area
- A (22)
We investigate the problem of colouring random graphs G ? G(n, p) in polynomial expected time. For the case p < 1.01/n, we present an algorithm that finds an optimal colouring in linear expected time. For suficiently large values of p, we give algorithms which approximate the chromatic number within a factor of O(?np). As a byproduct, we obtain an O(?np/ ln(np))-approximation algorithm for the independence number which runs in polynomial expected time provided p ? ln6 n/n.
Motivation: The Dictionary of Interfaces in Proteins (DIP) is a database collecting the 3D structure of interacting parts of proteins that are called patches. It serves as a repository, in which patches similar to given query patches can be found. The computation of the similarity of two patches is time consuming and traversing the entire DIP requires some hours. In this work we address the question of how the patches similar to a given query can be identified by scanning only a small part of DIP. The answer to this question requires the investigation of the distribution of the similarity of patches.
Results: The score values describing the similarity of two patches can roughly be divided into three ranges that correspond to different levels of spatial similarity. Interestingly, the two iso-score lines separating the three classes can be determined by two different approaches. Applying a concept of the theory of random graphs reveals significant structural properties of the data in DIP. These can be used to accelerate scanning the DIP for patches similar to a given query. Searches for very similar patches could be accelerated by a factor of more than 25. Patches with a medium similarity could be found 10 times faster than by brute-force search.
A relational structure is a core, if all its endomorphisms are embeddings. This notion is important for the classification for the computational complexity of constraint satisfaction problems. It is a fundamental fact that every finite structure S has a core, i.e., S has an endomorphism e such that the structure induced by e(S) is a core; moreover, the core is unique up to isomorphism.
We prove that this result remains valid for countably categorical structures, and prove that every countably categorical structure has a core, which is unique up to isomorphism, and which is again countably categorical. We thus reduced the classification for the complexity of constraint satisfaction problems with countably categorical templates to the classifiaction for constraint satisfaction problems where the templates are countably categorical cores. We also show that a core of a countably categorical structure Gamma is model complete, and therefore universal-existential axiomatizable. If Gamma contains all primitive positive definable relations, then the core of Gamma admits quantifier elimination. We discuss consequences for constraint satisfaction with countably categorical templates.
Dominance constraints are logical descriptions of trees. Efficient algorithms for the subclass of normal dominance constraints were recently proposed. We present a new and simpler graph algorithm solving these constraints more efficiently, in quadratic time per solved form. It also applies to weakly normal dominance constraints as needed for an application to computational linguistics. Subquadratic running time can be achieved employing decremental graph biconnectivity algorithms.
An instance of a constraint satisfaction problem is k-consistent if any k constraints of it can be simultaneously satisfied. We focus on constraint languages with a single binary constraint. In this case, the constraint satisfaction problem is equivalent to the question whether there is a homomorphism from an input digraph G to a fixed target digraph H. The instance corresponding to G is k-consistent if every subgraph of G of size at most k is homomorphic to H. Let r_k(H) be the largest r such that every k-consistent G contains a subgraph G' of size at least r ||E(G)|| that is homomorphic to H. The ratio r_k(H) reflects the fraction of constraints of a k-consistent instance that can be always satisfied. We determine r_k(H) for all digraphs H that are not acyclic and show that lim r_k(H)=1 for k tending to infinity if H has tree duality. For the latter case we design an efficient algorithm that computes in linear time for a given input graph G and epsilon>0 either a homomorphism from almost the entire graph G to H or a subgraph of G of bounded size that is not homomorphic to H.
We consider instances of the maximum independent set problem that are constructed
according to the following semirandom model. Let Gn,p be a random graph, and let
S be a set of k vertices, chosen uniformly at random. Then, let G0 be the graph
obtained by deleting all edges connecting two vertices in S. Finally, an adversary may
add edges to G0 that do not connect two vertices in S, thereby producing the instance
G = G ∗ n,p,k . We present an algorithm that on input G = G ∗ n,p,k finds an independent
set of size ≥ k within polynomial expected time, provided that k ≥ C(n/p)1/2 for a
certain constant C > 0. Moreover, we prove that in the case k ≤ (1 − ε) ln(n)/p this
problem is hard.
We study semirandom k-colorable graphs made up as follows. Partition the vertex set
V = {1, ... , n} randomly into k classes V1, ... , Vk of equal size and include each Vi-Vj -edge
with probability p independently (1 ≤ i < j ≤ k) to obtain a graph G0. Then, an adversary may
add further Vi-Vj -edges (i 6= j) to G0, thereby completing the semirandom graph G = G ∗ n,p,k.
We show that if np ≥ max{(1 + ε)k ln n,C0k2} for a certain constant C0 > 0 and an arbitrarily
small but constant ε > 0, an optimal coloring of G ∗ n,p,k can be found in polynomial time with high
probability. Furthermore, if np ≥ C0 max{k ln n, k2}, a k-coloring of G ∗ n,p,k can be computed in
polynomial expected time. Moreover, an optimal coloring of G ∗ n,p,k can be computed in expected
polynomial time if k ≤ ln1/3 n and np ≥ C0k ln n. By contrast, it is NP-hard to k-color G ∗ n,p,k
w.h.p. if np ≤ (1/2 − ε)k ln(n/k).
Approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be
solved in polynomial time. The weighted matching problem is to find a matching in an
edge weighted graph that has maximum weight. The first polynomial time algorithm for this problem was given by Edmonds in 1965. The fastest known algorithm for the weighted matching problem has a running time of O(nm + n2 log n). Many real world problems require graphs of such large size that this running time is too costly. Therefore there is considerable need for faster approximation algorithms for the weighted matching problem. We present a linear time approximation algorithm for the weighted matching problem with a performance ratio arbitrarily close to 2/3 . This improves the previously best performance ratio of 1/2. Our algorithm is not only of theoretical interest but because it is easy to implement and the constants involved are quite small it is also useful in practice.
We study the evolution of the size of the largest and the second largest
component in the random intersection graph model which is suited to re
ect
the transitivity (or clustering property) visible in real-world networks. We
show that certain random intersection graphs differ from Gn;p in that they
have only a polynomial jump in the evolution of the size of the largest
component. On the other hand the moment for the jump is still at the
point where the expected vertex degree becomes 1 which is similar to Gn;p.
We also describe a test of our result on a protein network.
The terminal Steiner tree problem is a special version of
the Steiner tree problem, where a Steiner minimum tree has to be found
in which all terminals are leaves. We prove that no polynomial time approximation
algorithm for the terminal Steiner tree problem can achieve
an approximation ratio less than (1 - o(1)) ln n unless NP has slightly superpolynomial
time algorithms. Moreover, we present a polynomial time
approximation algorithm for the metric version of this problem with a performance
ratio of 2 , where denotes the best known approximation ratio
for the Steiner tree problem. This improves the previously best known
approximation ratio for the metric terminal Steiner tree problem of +2.
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.