A hybrid heuristic for the maximum clique problem

In this paper we present a heuristic based steady-state genetic algorithm for the maximum clique problem. The steady-state genetic algorithm generates cliques, which are then extended into maximal cliques by the heuristic. We compare our algorithm with three best evolutionary approaches and the overall best approach, which is non-evolutionary, for the maximum clique problem and find that our algorithm outperforms all the three evolutionary approaches in terms of best and average clique sizes found on majority of DIMACS benchmark instances. However, the obtained results are much inferior to those obtained with the best approach for the maximum clique problem.     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.     

Greedy maximum-clique decompositions

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. We have recently shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. A greedy max-clique decomposition is a particular kind cf greedy clique decomposition where maximum cliques are removed, instead of just maximal ones. In this paper, we show that any greedy max-clique decompositionC of a graph of ordern has, wheren(C) is the number of vertices inC.     

The Logistic Diffusion of Information through Randomly Overlapped Cliques

The logistic model expects: If an item is told and heard in a set of people and periods under conditions of steady, pairing off, with equal opportunity, then Δ_t = kp _t q _t , i.e. increments in knowers are proportional to joint probabilities.Unequal opportunities result (among many causes) from “clique effects” where people communicate more within their daily circles of contacts (in homes, work, transit, eating and in leisure or other activities) than between such cliques.We hypothesized that if cliques are randomly overlapped in membership, then as clique size increases from 2 to all N persons, the diffusion-retarding effect of clique barriers will tend to vanish. “Larger cliques accelerate diffusion.”Previous experiments confirmed this hypothesis up to 4-man cliques and contradicted it thereafter, as larger cliques exceeded logistic expectations, and did so systematically. This was due to a constraint of “seeking out non-knowers” which was eliminated in the present experiments.With three replications from a population of playing cards, simulating increasing sizes of cliques, the curves rose steadily towards the logistic as upper limit just as hypothesized. The parameter r_ic measuring agreement of observed with expected increments rose from zero for the 2-man cliques up to r_ic = 0·98 for the N-man clique-of-the-whole.From this and other experiments, we infer that logistic diffusion of items is likely to be approximated in so far as populations are homogeneous with very diversely overlapped cliques which are larger than pairs. As cliques enlarge, the diffusion curve approaches the simplest logistic model. At cliques of four persons, acceleration from “seeking non-knowers” offset deceleration from clique barriers.     

Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation

Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin–Straus formulation and can compete with a sophisticated combinatorial heuristic.     

A Localized Implementation of the Iterative Proportional Scaling Procedure for Gaussian Graphical Models

In this article, we propose localized implementations of the iterative proportional scaling (IPS) procedure by the strategy of partitioning cliques for computing maximum likelihood estimations in large Gaussian graphical models. We first divide the set of cliques into several nonoverlapping and nonempty blocks, and then adjust clique marginals in each block locally. Thus, high-order matrix operations can be avoided and the IPS procedure is accelerated. We modify the Swendsen–Wang Algorithm and apply the simulated annealing algorithm to find an approximation to the optimal partition which leads to the least complexity. This strategy of partitioning cliques can also speed up the existing IIPS and IHT procedures. Numerical experiments are presented to demonstrate the competitive performance of our new implementations and strategies.     

On cliques in graphs

A clique is a maximal complete subgraph of a graph. The maximum number of cliques possible in a graph withn nodes is determined. Also, bounds are obtained for the number of different sizes of cliques possible in such a graph.     

Timetabling University Examinations

The problem of timetabling examinations is one which is faced by most educational institutions, with the problem becoming particularly acute in institutions of higher education. The situation may be formulated generally as a 0-1 integer pregramming problem but, in common with a number of other timetabling problems which have been reported, a heuristic approach is more practical and produces an acceptable solution. The procedure described takes account of the obvious constraints imposed by examination-room availability and capacity, and the need to avoid clashes between common examination papers. In addition, the examinations are scheduled such that the students are faced with a minimum number of occasions when two papers have to be taken in the same day and, for ease of marking, the larger courses are examined early. A computer program to implement the heuristic was developed and was found to produce a better timetable than the previous manual procedure as well as a considerable saving in clerical effort.     

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.     

A multiobjective framework for heavily constrained examination timetabling problems

University examination timetabling is a challenging set partitioning problem that comes in many variations, and real world applications usually carry multiple constraints and require the simultaneous optimization of several (often conflicting) objectives. This paper presents a multiobjective framework capable of solving heavily constrained timetabling problems. In this prototype study, we focus on the two objectives: minimizing timetable length while simultaneously optimizing the spread of examinations for individual students. Candidate solutions are presented to a multiobjective memetic algorithm as orderings of examinations, and a greedy algorithm is used to construct violation free timetables from permutation sequences of exams. The role of the multiobjective algorithm is to iteratively improve a population of orderings, with respect to the given objectives, using various mutation and reordering heuristics.     

On cliques in graphs

A clique is a maximal complete subgraph of a graph. Moon and Moser obtained bounds for the maximum possible number of cliques of different sizes in a graph ofn vertices. These bounds are improved in this note.     

On self-clique graphs with given clique sizes, II

The clique graph of a graph G is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques have a non-empty intersection. A graph is self-clique if it is isomorphic to its clique graph. We give a new characterization of the set of all connected self-clique graphs having all cliques but two of size 2.     

Evolution towards the Maximum Clique

As is well known, the problem of finding a maximum clique in a graph isNP-hard. Nevertheless, NP-hard problems may have easy instances. This paperproposes a new, global optimization algorithm which tries to exploit favourabledata constellations, focussing on the continuous problem formulation: maximizea quadratic form over the standard simplex. Some general connections of thelatter problem with dynamic principles of evolutionary game theory areestablished. As an immediate consequence, one obtains a procedure whichconsists (a) of an iterative part similar to interior-path methods based on theso-called replicator dynamics; and (b) a routine to escape from inefficient,locally optimal solutions. For the special case of finding a maximum clique ina graph where the quadratic form arises from a regularization of the adjacencematrix, part (b), i.e. escaping from maximal cliques not of maximal size, isaccomplished with block pivoting methods based on (large) independent sets,i.e. cliques of the complementary graph. A simulation study is included whichindicates that the resulting procedure indeed has some merits.     

An independent set approach for the communication network of the GPS III system

In this article, we describe an algorithm to find the optimal communication network for the new GPS III satellite system. Finding a possible network will be translated to a maximum clique problem and an efficient algorithm for finding all maximum cliques under these special circumstances is described.     

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.     

Two remarks on circular arc graphs

In our first remark we observe a property of circular arcs which is similar to the Helly property and is helpful in describing all maximal cliques in circular arc graphs (as well as allowing us to genralize a result of Tucker). Our main result is a new simple characterization of circular arc graphs of clique covering number two. These graphs play a crucial role in recognition algorithms for circular arc graphs, and have been characterized by several authors. Specifically, we show that a graph with clique covering number two is a circular arc graph if and only if its edges can be coloured by two colours so that no induced four-cycle contains two opposite edges of the same colour. Our proof of the characterization depends on the lexicographic method we have recently introduced. Both remarks could be useful in designing efficient algorithms for (maximum cliques in, respectively recognition of) circular arc graphs     

Subgraph extraction and metaheuristics for the maximum clique problem

The maximum clique problem involves finding the largest set of pairwise adjacent vertices in a graph. The problem is classic but still attracts much attention because of its hardness and its prominent applications. Our work is based on the existence of an order of all the vertices whereby those belonging to a maximum clique stay close enough to each other. Such an order can be identified via the extraction of a particular subgraph from the original graph. The problem can consequently be seen as a permutation problem that can be addressed efficiently by metaheuristics. We first design a memetic algorithm (MA) for this purpose. Computational experiments conducted on the DIMACS benchmark instances clearly show that our MA not only outperforms existing genetic approaches, but it also compares very well to state-of-the-art algorithms regarding the maximal clique size found after different runs. Furthermore, we show that a hybridization of MA with an iterated local search (ILS) improves the stability of the algorithm. This hybridization (MA-ILS) permits to find two distinct maximal cliques of size 79 and one of size 80 for the C2000.9 instance of the DIMACS benchmark.     

Detecting strong cliques

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs.     

Global Escape Strategies for Maximizing Quadratic Forms over a Simplex

Consider the problem of maximizing a quadratic formover the standard simplex.Problems of this type occur, e.g., in the search for the maximum (weighted)clique in an undirected graph.In this paper, copositivity-based escape proceduresfrom inefficient local solutions are rephrased into lower-dimensionalsubproblems which are again of the same type. As a result, analgorithm is obtained which tries to exploit favourable data constellationsin a systematic way, and to avoid the worst-case behaviourof such NP-hard problems whenever possible. First results onfinding large cliques in DIMACS benchmark graphs are encouraging.     

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.