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.