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.     

Small maximal matchings of random cubic graphs

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. larger than 0.3158n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

Minimum independent dominating sets of random cubic graphs

We present a heuristic for finding a small independent dominating set ?? of cubic graphs. We analyze the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations, and obtain an upper bound on the expected size of ??. A corresponding lower bound is derived by means of a direct expectation argument. We prove that ?? asymptotically almost surely satisfies 0.2641n ≤ |??| ≤ 0.27942n. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 147–161, 2002     

Ramsey-Type Results for Unions of Comparability Graphs

 It is well known that the comparability graph of any partially ordered set of n elements contains either a clique or an independent set of size at least . In this note we show that any graph of n vertices which is the union of two comparability graphs on the same vertex set, contains either a clique or an independent set of size at least . On the other hand, there exist such graphs for which the size of any clique or independent set is at most n ^0.4118. Similar results are obtained for graphs which are unions of a fixed number k comparability graphs. We also show that the same bounds hold for unions of perfect graphs. Received: November 1, 1999 Final version received: December 1, 2000     

Clique coloring of binomial random graphs

A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior of the clique chromatic number of the random graph ??(n,p) for a wide range of edge‐probabilities p = p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.     

Can visibility graphs Be represented compactly?

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graphG, a familyG={G ₁,G ₂,...,G _k } is called aclique cover ofG if (i) eachG _i is a clique or a bipartite clique, and (ii) the union ofG _i isG. The size of the clique coverG is defined as ∑ _i=1 ^k n _i , wheren _i is the number of vertices inG _i . Our main result is that there are visibility graphs ofn nonintersecting line segments in the plane whose smallest clique cover has size Ω(n ²/log² n). An upper bound ofO(n ²/logn) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of sizeO(nlog³ n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n logn). The work by the first author was supported by National Science Foundation Grant CCR-91-06514. The work by the second author was supported by a USA-Israeli BSF grant. The work by the third author was supported by National Science Foundation Grant CCR-92-11541.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

Positional Games and the Second Moment Method

Dedicated to the memory of Paul Erdős We study the fair Maker–Breaker graph Ramsey game MB(n;q). The board is , the players alternately occupy one edge a move, and Maker wants a clique of his own. We show that Maker has a winning strategy in MB(n;q) if , which is exactly the clique number of the random graph on n vertices with edge-probability 1/2. Due to an old theorem of Erdős and Selfridge this is best possible apart from an additive constant. Received March 28, 2000     

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.     

Covering cliques with spanning bicliques

The edges of the complete graph on n vertices can be covered by ⌈lg n⌉ spanning complete bipartite subgraphs. However, the sum of the number of edges in these subgraphs is roughly (n²/4)lg n, while a cover consisting of n − 1 spanning stars uses only (n − 1)² edges. We will show that the covering by spanning stars has the smallest total number of edges among all coverings of the clique by spanning complete bipartite subgraphs, except when n is 4 or 8. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 223–227, 1998     

Large cliques or stable sets in graphs with no four‐edge path and no five‐edge path in the complement

Erd?s and Hajnal [Discrete Math 25 (1989), 37–52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size n^?(H) for some ?(H)>0. The Conjecture 1. known to be true for graphs H with |V(H)|≤4. One of the two remaining open cases on five vertices is the case where H is a four‐edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four‐edge path or the complement of a five‐edge path as an induced subgraph contains either a clique or a stable set of size at least n^1/6. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Solving the maximum clique problem using a tabu search approach

We describe two variants of a tabu search heuristic, a deterministic one and a probabilistic one, for the maximum clique problem. This heuristic may be viewed as a natural alternative implementation of tabu search for this problem when compared to existing ones. We also present a new random graph generator, the -generator, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Computational results on a large set of test problems randomly generated with this new generator are reported and compared with those of other approximate methods.The authors are grateful to the Quebec Government (Fonds F.C.A.R.) and to the Canadian Natural Sciences and Engineering Research Council (grant 0GP0038816) for financial support.     

On parallelizing a greedy heuristic for finding small dominant sets

We analyse a greedy heuristic for finding small dominating sets in graphs: bounds on the size of the dominating set so produced had previously been derived in terms of the size of a smallest dominating set and the number of vertices and edges in the graph, respectively, We show that computing the resulting small dominating set isP-hard and so cannot be done efficiently in parallel (in the context of the PRAM model of parallel computation). We also consider a related non-deterministic greedy heuristic.     

Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming

In this paper, a greedy heuristic and two local search algorithms, 1-opt local search and k-opt local search, are proposed for the unconstrained binary quadratic programming problem (BQP). These heuristics are well suited for the incorporation into meta-heuristics such as evolutionary algorithms. Their performance is compared for 115 problem instances. All methods are capable of producing high quality solutions in short time. In particular, the greedy heuristic is able to find near optimum solutions a few percent below the best-known solutions, and the local search procedures are sufficient to find the best-known solutions of all problem instances with n 100. The k-opt local searches even find the best-known solutions for all problems of size n 250 and for 11 out of 15 instances of size n = 500 in all runs. For larger problems (n = 500, 1000, 2500), the heuristics appear to be capable of finding near optimum solutions quickly. Therefore, the proposed heuristics—especially the k-opt local search—offer a great potential for the incorporation in more sophisticated meta-heuristics.     

Multi-neighborhood tabu search for the maximum weight clique problem

Given an undirected graph G=(V,E) with vertex set V={1,??,n} and edge set E?V×V. Let w:V??Z ⁺ be a weighting function that assigns to each vertex i??V a positive integer. The maximum weight clique problem (MWCP) is to determine a clique of maximum weight. This paper introduces a tabu search heuristic whose key features include a combined neighborhood and a dedicated tabu mechanism using a randomized restart strategy for diversification. The proposed algorithm is evaluated on a total of 136 benchmark instances from different sources (DIMACS, BHOSLIB and set packing). Computational results disclose that our new tabu search algorithm outperforms the leading algorithm for the maximum weight clique problem, and in addition rivals the performance of the best methods for the unweighted version of the problem without being specialized to exploit this problem class.     

Finding cliques using few probes

Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an n vertex graph, and need to output a clique. We show that if the input graph is drawn at random from (and hence is likely to have a clique of size roughly ), then for every δ<2 and constant ?, there is an α<2 (that may depend on δ and ?) such that no algorithm that makes n^δ probes in ? rounds is likely (over the choice of the random graph) to output a clique of size larger than .     

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.     

The Diameter of a Scale-Free Random Graph

We consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number m of earlier vertices, where each earlier vertex is chosen with probability proportional to its degree. This process was introduced by Barabási and Albert [3], as a simple model of the growth of real-world graphs such as the world-wide web. Computer experiments presented by Barabási, Albert and Jeong [1,5] and heuristic arguments given by Newman, Strogatz and Watts [23] suggest that after n steps the resulting graph should have diameter approximately logn. We show that while this holds for m=1, for m2 the diameter is asymptotically log n/log logn.* Research supported in part by NSF grant no. DSM9971788     

Bounds and Heuristics for the Shortest Capacitated Paths Problem

Given a graph G, the Shortest Capacitated Paths Problem (SCPP) consists of determining a set of paths of least total length, linking given pairs of vertices in G, and satisfying capacity constraints on the arcs of G.We formulate the SCPP as a 0-1 linear program and study two Lagrangian relaxations for getting lower bounds on the optimal value. We then propose two heuristic methods. The first one is based on a greedy approach, while the second one is an adaptation of the tabu search meta-heuristic.