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)
Random intersection graphs naturally exhibit a certain amount of transitivity and hence can
be used to model real--world networks. We study the evolution of the chromatic number
of a random intersection graph and show that, in a certain range of parameters,
these random graphs can be coloured optimally with high probability using different greedy
algorithms.
Experiments on real network data confirm the positive theoretical predictions and
suggest that heuristics for the clique and the chromatic number can work hand in hand
proving mutual optimality.
Let H_d(n, p) signify a random d-uniform hypergraph with n vertices in which each of the possible edges is present with probability p = p(n) independently, and let H_d(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of H_d(n, p) and H_d(n,m). As an application, we obtain an asymptotic formula for the probability that H_d(n, p) is connected, and a corresponding formula for H_d(n,m). In addition, we infer a local limit theorem for the conditional distribution of the number of edges in H_d(n, p) given that H_d(n, p) is connected. While most prior work on this subject relies on techniques from enumerative combinatorics, we present a new, purely probabilistic approach.
In a database of about 2000 approved drugs, represented by 105 structural conformers,
we have performed 2D comparisons (Tanimoto coefficients) and 3D superpositions. For one class of drugs the correlation
between structural resemblance and similar action was analysed in detail.
In general Tanimoto cofficients and 3D scores give similar results, but we
find that 2D similarity measures neglect important structural/funtional
features. Examples for both over- and underestimation of similarity by
2D metrics are discussed. The required additional effort for 3D superpositions
is assessed by implementation of a fast algorithm with a processing
time below 0:01 seconds and a more sophisticated approach (0:5 seconds
per superposition). According to the improvement of similarity detection
compared to 2D screening and the pleasant rapidity on a desktop PC,
full{atom 3D superposition will be an upcoming method of choice for
library prioritization or similarity screening approaches.
The weighted matching problem is to find a matching in a weighted graph
that has maximum weight. The fastest known algorithm for this problem has running time
O(nm +n2 log n). Many real world problems require graphs of such large size that this running
time is too costly. We present a linear time approximation algorithm for the weighted
matching problem with a performance ratio of 2
3 ???? ". This improves the previously best
performance ratio of 1
2 .
Recently two different linear time approximation algorithms for the weighted matching problem in graphs have been suggested [5][17]. Both these algorithms have a performance ratio of 1/2. In this paper we present a set of local improvement operations and prove that it guarantees a performance ratio of 2/3. We show that a maximal set of these local improvements can be found in linear time.
To see how these local improvements behave in practice we conduct an experimental comparison of four different approximation algorithms for calculating maximum weight matchings in weighted graphs. One of these algorithms is the commonly used Greedy algorithm which achieves a performance ratio of 1/2 but has O(m log n) runtime. The other three algorithms all have linear runtime. Two of them are the above mentioned 1/2 approximation algorithms. The third algorithm may have an arbitrarily bad performance ratio but in practice produces reasonably good results. We compare the quality of the algorithms on a test set of weighted graphs and study the improvement achieved by our local improvement operations. We also do a comparison of the runtimes of all algorithms.
We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259–269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.
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
p ?? ln6(n)/n, we give algorithms which approximate the chromatic
number within a factor of O(? np). We also obtain an O(?
np/ ln(np))-
approximation algorithm for the independence number. As an application,
we propose an algorithm for deciding satisfiability of random 2k-
SAT formulas (with sufficiently many clauses) in
polynomial expected time.
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.