An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments

We present an exact and efficient branch-and-bound algorithm MCR for finding a maximum clique in an arbitrary graph. The algorithm is not specialized for any particular type of graph. It employs approximate coloring to obtain an upper bound on the size of a maximum clique along with an improved appropriate sorting of vertices. We demonstrate by computational experiments on random graphs with up to 15,000 vertices and on DIMACS benchmark graphs that in general, our algorithm decidedly outperforms other existing algorithms. The algorithm has been successfully applied to interesting problems in bioinformatics, image processing, design of quantum circuits, and design of DNA and RNA sequences for biomolecular computation.     

线图上的团染色问题

设G=(V,E)为简单图, G的每个至少有两个顶点的极大完全子图称为G的一个团. 图的团染色定义为给图的点进行染色使得图中没有单一颜色的团, 也就是说每一个团具有至少2种颜色.图的一个k-团染色 是指用k 种颜色给图的点着色使得图G 的每一个团至少有2种颜色.图G的团染色数\chi_{C}(G)是指最小的数k使得图G 存在k-团染色. 首先指出了完全图的线图的团染色数与推广的Ramsey 数之间的一个联系, 其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.     

Matroid representation of clique complexes

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.     

Optimizing weakly triangulated graphs

A graph is weakly triangulated if neither the graph nor its complement contains a chordless cycle with five or more vertices as an induced subgraph. We use a new characterization of weakly triangulated graphs to solve certain optimization problems for these graphs. Specifically, an algorithm which runs inO((n + e)n ³) time is presented which solves the maximum clique and minimum colouring problems for weakly triangulated graphs; performing the algorithm on the complement gives a solution to the maximum stable set and minimum clique covering problems. Also, anO((n + e)n ⁴) time algorithm is presented which solves the weighted versions of these problems.The author acknowledges the support of an N.S.E.R.C. Canada postgraduate scholarship.The author acknowledges the support of the U.S. Air Force Office of Scientific Research under grant number AFOSR 0271 to Rutgers University.     

Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane

An intersection graph of rectangles in the (x, y)-plane with sides parallel to the axes is obtained by representing each rectangle by a vertex and connecting two vertices by an edge if and only if the corresponding rectangles intersect. This paper describes algorithms for two problems on intersection graphs of rectangles in the plane. One is an O(n log n) algorithm for finding the connected components of an intersection graph of n rectangles. This algorithm is optimal to within a constant factor. The other is an O(n log n) algorithm for finding a maximum clique of such a graph. It seems interesting that the maximum clique problem is polynomially solvable, because other related problems, such as the maximum stable set problem and the minimum clique cover problem, are known to be NP-complete for intersection graphs of rectangles. Furthermore, we briefly show that the k-colorability problem on intersection graphs of rectangles is NP-complete.     

A new trust region technique for the maximum weight clique problem

A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of other stationary points of the program. We formulate and prove a condition when a Motzkin-Straus optimum coincides with such a point. The developed method has complexity O(n³), where n is the number of vertices of the graph. It was implemented in a publicly available software package QUALEX-MS.Computational experiments indicate that the algorithm is exact on small graphs and very efficient on the DIMACS benchmark graphs and various random maximum weight clique problem instances.     

Approximating the maximum vertex/edge weighted clique using local search

This paper extends the recently introduced Phased Local Search (PLS) algorithm to more difficult maximum clique problems and also adapts the algorithm to handle maximum vertex/edge weighted clique instances. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current sub-graph, and plateau search, where vertices of the current sub-graph are swapped with vertices not contained in the current sub-graph. These sub-algorithms differ in firstly their vertex selection techniques in that selection can be solely based on randomly selecting a vertex, randomly selecting within highest vertex degree, or random selecting within vertex penalties that are dynamically adjusted during the search. Secondly, the perturbation mechanism used to overcome search stagnation differs between the sub-algorithms. PLS has no problem instance dependent parameters and achieves state-of-the-art performance for maximum clique and maximum vertex/edge weighted clique problems over a large range of the commonly used DIMACS benchmark instances.     

A parallel maximum clique algorithm for large and massive sparse graphs

This paper describes BBMCPara, a new parallel exact maximum clique algorithm tailored for large and massive sparse graphs. The paper first presents a sequential algorithm BBMCSP, which builds on ideas from a leading bit-parallel published algorithm for middle-size graphs. It employs heavy pre-processing and a new sparse bitset encoding to outperform other state-of-the-art algorithms by up to several orders of magnitude over a set of real networks. BBMCPara parallelizes BBMCSP by splitting according to a preprocessing step of the latter. On a 20-core computer, it averages speedups close to an order of magnitude over real graphs of up to 3 million vertices. According to the reported results, BBMCPara appears to be the current fastest algorithm for large and massive real networks to the best of our knowledge.     

Coloring Clique-free Graphs in Linear Expected Time

This article presents a linear expected time algorithm to color every graph which does not contain a clique on l + 1 vertices as a subgraph with a minimal number of colors. This extends a result of Dyer and Frieze for l-colorable graphs. For the proof we develop a new method which allows us to precisely estimate the number of graphs with certain structural properties.     

Extremal interval graphs

An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for the numbers of such graphs. © 1993 John Wiley & Sons, Inc.     

A study on oriented relative clique number

An oriented graph is a directed graph with no directed cycle of length one or two. The relative clique number of an oriented graph is the cardinality of a largest subset $X$ of vertices such that each pair of vertices is either adjacent or connected by a directed 2-path. It is known that the oriented relative clique number of a planar graph is at most 80. Here we improve the upper bound to 32. We also prove an upper bound of 14 for oriented relative clique number of triangle-free planar graphs. Furthermore, we determine the exact values of oriented relative clique number for the families of outerplanar graphs with girth at least $g$ and planar graphs with girth at least $g+2$ for all $g\ge 3$. Moreover, we study the relation of oriented relative clique number with oriented chromatic number, oriented absolute clique number and maximum degree of a graph. We also show that oriented relative clique number of a connected subcubic graph is at most seven which weakly supports a conjecture by Sopena (JGT 1997).     

A generalization of simplicial elimination orderings

We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P₄ and no 2K₂. We prove that Berge's Strong Perfect Graph Conjecture holds for such graphs. The class generalizes several well-known families of perfect graphs, such as triangulated graphs and bipartite graphs. Testing membership in this class and computing the maximum clique size for a graph in this class is not hard, but finding an optimal coloring is NP-hard. We give a polynomial-time algorithm for optimally coloring the vertices of such a graph when it is perfect. © 1996 John Wiley & Sons, Inc.     

Disjoint clique cutsets in graphs without long holes

A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class of biclique separable graphs contains several well‐studied graph classes, including triangulated graphs. We prove that for the class of biclique separable graphs, the recognition problem, the vertex coloring problem, and the clique problem can be solved efficiently. Our algorithms also yield a proof that biclique separable graphs are perfect. Our coloring algorithm is actually more general and can be applied to graphs that can be decomposed via a special type of biclique cutset. Our algorithms are based on structural results on biclique separable graphs developed in this paper. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 277–298, 2005     

On the tree representation of chordal graphs

We introduce the notion of the boundary clique and the k-overlap clique graph and prove the following: Every incomplete chordal graph has two nonadjacent simplicial vertices lying in boundary cliques. An incomplete chordal graph G is k-connected if and only if the k-overlap clique graph g_k(G) is connected. We give an algorithm to construct a clique tree of a connected chordal graph and characterize clique trees of connected chordal graphs using the algorithm.     

Solving maximum clique in sparse graphs: an O(nm+n2^{d/4}) algorithm for d-degenerate graphs

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\) . The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\) . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.     

A fast algorithm for coloring Meyniel graphs

We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph. We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This O(n³) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Hoàng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs.     

若干图类的Wiener指数的极值

一个图的Wiener指数是指这个图中所有点对的距离和.Wiener指数在理论化学中有广泛应用. 本文刻画了给定顶点数及特定参数如色数或团数的图中Wiener指数达最小值的图, 同时也刻画了给定顶点数及团数的图中Wiener指数达最大值的图.     

Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

Restricted unimodular chordal graphs

A chordal graph is called restricted unimodular if each cycle of its vertex‐clique incidence bipartite graph has length divisible by 4. We characterize these graphs within all chordal graphs by forbidden induced subgraphs, by minimal relative separators, and in other ways. We show how to construct them by starting from block graphs and multiplying vertices subject to a certain restriction, which leads to a linear‐time recognition algorithm. We show how they are related to other classes such as distance‐hereditary chordal graphs and strongly chordal graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 121–136, 1999     

Clique trees of chordal graphs: leafage and 3-asteroidals

Chordal graphs were characterized as those graphs having a tree, called clique tree, whose vertices are the cliques of the graph and for every vertex in the graph, the set of cliques that contain it form a subtree of clique tree. In this work, we study the relationship between the clique trees of a chordal graph and its subgraphs. We will prove that clique trees can be described locally and all clique trees of a graph can be obtained from clique trees of subgraphs. In particular, we study the leafage of chordal graphs, that is the minimum number of leaves among the clique trees of the graph. It is known that interval graphs are chordal graphs without 3-asteroidals. We will prove a generalization of this result using the framework developed in the present article. We prove that in a clique tree that realizes the leafage, for every vertex of degree at least 3, and every choice of 3 branches incident to it, there is a 3−asteroidal in these branches.