Many problems can be formulated as maximum clique problems. Hence, it is highly important to develop algorithms that can find a maximum clique very fast in practice. We propose new approximate ...coloring and other related techniques which markedly improve the run time of the branch-and-bound algorithm MCR (J. Global Optim., 37, pp.95-111, 2007), previously shown to be the fastest maximum-clique-finding algorithm for a large number of graphs. The algorithm obtained by introducing these new techniques in MCR is named MCS. It is shown that MCS is successful in reducing the search space quite efficiently with low overhead. Extensive computational experiments confirm the superiority of MCS over MCR and other existing algorithms. It is faster than the other algorithms by orders of magnitude for several graphs. In particular, it is faster than MCR for difficult graphs of very high density and for very large and sparse graphs, even though MCS is not designed for any particular type of graph. MCS can be faster than MCR by a factor of more than 100,000 for some extremely dense random graphs. This paper demonstrates in detail the effectiveness of each new techniques in MCS, as well as the overall contribution.
Clique-coloring UE and UEH graphs Cerioli, Márcia R.; Petito, Priscila
Electronic notes in discrete mathematics,
02/2008, Volume:
30
Journal Article
We consider the clique-coloring problem, that is, coloring the vertices of a given graph such that no maximal clique of size at least two is monocolored. More specifically, we investigate the problem ...of giving a class of graphs, to determine if there exists a constant
C such that every graph in this class is
C-clique-colorable. We consider the classes of UE and UEH graphs.
A graph
G is called an UE graph if it is the edge intersection graph of a family of paths in a tree. If this family satisfies the Helly Property we say that
G is an UEH graph.
We show that every UEH graph is 3-clique-colorable. Moreover our proof is constructive and provides a polynomial-time algorithm. We also describe, for each
k
≥
2
, an UE graph that is not
k-clique-colorable. The UE graphs form one of the few known classes for which the clique-chromatic number is unbounded.
Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs has attracted many research efforts, ...mainly due to its interesting structure and its numerous applications, especially in DNA sequence analysis and resource allocation, among others. In one of the most natural generalizations of tolerance graphs, namely
multitolerance
graphs, two tolerances are allowed for each interval—one from the left and one from the right side of the interval. Then, in its interior part, every interval tolerates the intersection with others by an amount that is a convex combination of its two border-tolerances. In the comparison of DNA sequences between different organisms, the natural interpretation of this model lies on the fact that, in some applications, we may want to treat several parts of the genomic sequences differently. That is, we may want to be more tolerant at some parts of the sequences than at others. These two tolerances for every interval—together with their convex hull—define an infinite number of the so called
tolerance-intervals
, which make the multitolerance model inconvenient to cope with. In this article we introduce the first non-trivial intersection model for multitolerance graphs, given by objects in the 3-dimensional space called
trapezoepipeds
. Apart from being important on its own, this new intersection model proves to be a powerful tool for designing efficient algorithms. Given a multitolerance graph with
n
vertices and
m
edges along with a multitolerance representation, we present algorithms that compute a minimum coloring and a maximum clique in
optimal
O
(
n
log
n
) time, and a maximum weight independent set in
O
(
m
+
n
log
n
) time. Moreover, our results imply an
optimal
O
(
n
log
n
) time algorithm for the maximum weight independent set problem on tolerance graphs, thus closing the complexity gap for this problem. Additionally, by exploiting more the new 3D-intersection model, we completely classify multitolerance graphs in the hierarchy of perfect graphs. The resulting hierarchy of classes of perfect graphs is
complete
, i.e. all inclusions are strict.
The maximum clique (MC) problem has long been concentrating the attention of many researchers within the combinatorial optimization community.
Most formulations proposed in the literature for the MC ...problem were adapted from the maximum independent set (MIS) problem, which is known to be equivalent to the MC. In fact, independent sets can be easily modelled within the natural variables space.
In the present paper we propose new formulations for the MC problem, using additional and extra indexed variables, leading to extended and discretized formulations. The number of variables and constraints of the new models depend on the range of variation of an interval containing the clique number (
ω
) of the graph. Therefore, tight lower and upper bounds for
ω
may strongly benefit the dimension of the new models.
Computational results have been conducted on some DIMACS benchmark and biological instances. These results indicate that, among sparse graphs, the linear programming relaxation of the discretized formulations may produce stronger upper bounds than the known models, being faster to find an optimum clique when embedded into the branch-and-bound. Furthermore, the new models can be used to address other related problems, namely to find a maximum size
k-plex, or a maximum size component involving two overlapping cliques.
In this paper we present an exact algorithm for the Maximum Common Induced Subgraph Problem (
MCIS
) by addressing it directly, using Integer Programming (
IP
) and polyhedral combinatorics. We study ...the
MCIS
polytope and introduce strong valid inequalities, some of which we prove to define facets. Besides, we show an equivalence between our
IP
model for
MCIS
and a well-known formulation for the Maximum Clique problem. We report on computational results of branch-and-bound (
B&B
) and branch-and-cut (
B&C
) algorithms we implemented and compare them to those yielded by an existing combinatorial algorithm.
The maximum clique in an undirected graph is the largest subset of a set of graph's vertices where each pair of elements in the subset is connected. In this paper I would like to propose an algorithm ...for quantum computers that finds a maximum clique in an arbitrary undirected graph. An algorithm has O(|V|2|V|/2) worst case time complexity and O(2|V|/2) best case time complexity. Algorithm's space complexity for each case is O(|V|). An algorithm is based on a version of Grover's quantum algorithm for finding element in an unsorted list in which there can be an unknown number of solutions.
In this note, we show that if the maximum clique problem can be solved by a polynomial time δ-approximation algorithm, then the maximum edge clique partitioning problem (Max-ECP) can be solved by a ...polynomial time 2(pδ−1)p−1-approximation algorithm for any fixed integer p≥2. This improves the best known bound on the performance ratio of an approximation algorithm for Max-ECP problem and also corrects an error in an earlier work on the topic.
In a paper published in 1978, McEliece, Rodemich and Rumsey improved the Lovász bound θ for the maximum clique problem. This strengthening has become well known under the name Lovász-Schrijver bound ...and is usually denoted by θ′. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound and the actual clique number can be arbitrarily large, we establish homomorphy results for this bound under cosums and products of graphs. In particular we show that for circulant graphs of prime order there must be a positive gap between the clique number and the bound.
PDF
