On the maximum small-world subgraph problem

A clique (or a complete subgraph) is a popular model for an “ideal” cluster in a network. However, in many practical applications this notion turns out to be overly restrictive as it requires the existence of all pairwise links within the cluster. Thus, the researchers and practitioners often rely on various clique relaxation ideas for more flexible models of highly connected clusters. In this paper, we propose a new clique relaxation model referred to as a small-world subgraph, which represents a network cluster with “small-world” properties: low average distance and high clustering coefficient. In particular, we demonstrate that the proposed small-world subgraph model has better “cohesiveness” characteristics than other existing clique relaxation models in some worst-case scenarios. The main focus of the paper is on the problem of finding a small-world subgraph of maximum cardinality in a given graph. We describe a mixed integer programming (MIP) formulation of the problem along with several algorithmic enhancements. For solving large-scale instances of the problem we propose a greedy-type heuristic referred to as the iterative depth-first search (IDF) algorithm. Furthermore, we show that the small-world subgraphs identified by the IDF algorithm have an additional property that may be attractive from the practical perspective, namely, 2-connectivity. Finally, we perform extensive computational experiments on real-world and randomly generated networks to demonstrate the performance of the developed computational approaches that also reveal interesting insights about the proposed clique relaxation model.     

Finding maximum subgraphs with relatively large vertex connectivity

We consider a clique relaxation model based on the concept of relative vertex connectivity. It extends the classical definition of a k-vertex-connected subgraph by requiring that the minimum number of vertices whose removal results in a disconnected (or a trivial) graph is proportional to the size of this subgraph, rather than fixed at k. Consequently, we further generalize the proposed approach to require vertex-connectivity of a subgraph to be some function f of its size. We discuss connections of the proposed models with other clique relaxation ideas from the literature and demonstrate that our generalized framework, referred to as f-vertex-connectivity, encompasses other known vertex-connectivity-based models, such as s-bundle and k-block. We study related computational complexity issues and show that finding maximum subgraphs with relatively large vertex connectivity is NP-hard. An interesting special case that extends the R-robust 2-club model recently introduced in the literature, is also considered. In terms of solution techniques, we first develop general linear mixed integer programming (MIP) formulations. Then we describe an effective exact algorithm that iteratively solves a series of simpler MIPs, along with some enhancements, in order to obtain an optimal solution for the original problem. Finally, we perform computational experiments on several classes of random and real-life networks to demonstrate performance of the developed solution approaches and illustrate some properties of the proposed clique relaxation models.     

Introducing subclasses of basic chordal graphs

Basic chordal graphs arose when comparing clique trees of chordal graphs and compatible trees of dually chordal graphs. They were defined as those chordal graphs whose clique trees are exactly the compatible trees of its clique graph.In this work, we consider some subclasses of basic chordal graphs, like hereditary basic chordal graphs, basic DV and basic RDV graphs, we characterize them and we find some other properties they have, mostly involving clique graphs.     

On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems

Permutation diagrams have been used in circuit design to model a set of single point nets crossing a channel, where the minimum number of layers needed to realize the diagram equals the clique number ω(G) of its permutation graph, the value of which can be calculated in O(nlogn) time. We consider a generalization of this model motivated by “standard cell” technology in which the numbers on each side of the channel are partitioned into consecutive subsequences, or cells, each of which can be left unchanged or flipped (i.e., reversed). We ask, for what choice of flippings will the resulting clique number be minimum or maximum. We show that when one side of the channel is fixed (no flipping), an optimal flipping for the other side can be found in O(nlogn) time for the maximum clique number, and that when both sides are free this can be solved in O(n²) time. We also prove NP-completeness of finding a flipping that gives a minimum clique number, even when one side of the channel is fixed, and even when the size of the cells is restricted to be less than a small constant. Moreover, since the complement of a permutation graph is also a permutation graph, the same complexity results hold for the stable set (independence) number. In the process of the NP-completeness proof we also prove NP-completeness of a restricted variant of a scheduling problem. This new NP-completeness result may be of independent interest.     

Four-Cycled Graphs with Topological Applications

We call a simple graph G a 4-cycled graph if either it has no edges or every edge of it is contained in an induced 4-cycle of G. Our interest on 4-cycled graphs is motivated by the fact that their clique complexes play an important role in the simple-homotopy theory of simplicial complexes. We prove that the minimal simple models within the category of flag simplicial complexes are exactly the clique complexes of some 4-cycled graphs. We further provide structural properties of 4-cycled graphs and describe constructions yielding such graphs. We characterize 4-cycled cographs, and 4-cycled graphs arising from finite chessboards. We introduce a family of inductively constructed graphs, the external extensions, related to an arbitrary graph, and determine the homotopy type of the independence complexes of external extensions of some graphs.     

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.     

Equivariant collapses and the homotopy type of iterated clique graphs

The clique graph K(G) of a simple graph G is the intersection graph of its maximal complete subgraphs, and we define iterated clique graphs by K⁰(G)=G, Kⁿ⁺¹(G)=K(Kⁿ(G)). We say that two graphs are homotopy equivalent if their simplicial complexes of complete subgraphs are so. From known results, it can be easily inferred that Kⁿ(G) is homotopy equivalent to G for every n if G belongs to the class of clique-Helly graphs or to the class of dismantlable graphs. However, in both of these cases the collection of iterated clique graphs is finite up to isomorphism. In this paper, we show two infinite classes of clique-divergent graphs that satisfy G?Kⁿ(G) for all n, moreover Kⁿ(G) and G are simple-homotopy equivalent. We provide some results on simple-homotopy type that are of independent interest.     

Clique coverings and partitions of line graphs

A clique in a graph G is a complete subgraph of G. A clique covering (partition) of G is a collection C of cliques such that each edge of G occurs in at least (exactly) one clique in C. The clique covering (partition) numbercc(G) (cp(G)) of G is the minimum size of a clique covering (partition) of G. This paper gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained by McGuinness and Rees [On the number of distinct minimal clique partitions and clique covers of a line graph, Discrete Math. 83 (1990) 49-62]. We also employ the proof techniques to give an alternative proof for the De Brujin-Erd?s Theorem.     

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.     

Convex domination in the composition and cartesian product of graphs

In this paper we characterize the convex dominating sets in the composition and Cartesian product of two connected graphs. The concepts of clique dominating set and clique domination number of a graph are defined. It is shown that the convex domination number of a composition G[H] of two non-complete connected graphs G and H is equal to the clique domination number of G. The convex domination number of the Cartesian product of two connected graphs is related to the convex domination numbers of the graphs involved.     

Algorithms on clique separable graphs

We define a family of graphs, called the clique separable graphs, characterized by the fact that they have completely connected cut sets by which we decompose them into parts such that when no further decomposition is possible we have a set of simple subgraphs. For example the chordal graphs and the i-triangulated graphs are clique separable graphs.The purpose of this paper is to describe polynomial time algorithms for the recognition of the clique separable graphs and for finding them a minimum coloring and a maximum clique.     

Safe separators for treewidth

A set of vertices S⊆V is called a safe separator for treewidth, if S is a separator of G, and the treewidth of G equals the maximum of the treewidth over all connected components W of G-S of the graph, obtained by making S a clique in the subgraph of G, induced by W∪S. We show that such safe separators are a very powerful tool for preprocessing graphs when we want to compute their treewidth. We give several sufficient conditions for separators to be safe, allowing such separators, if existing, to be found in polynomial time. In particular, every inclusion minimal separator of size one or two is safe, every minimum separator of size three that does not split off a component with only one vertex is safe, and every inclusion minimal separator that is an almost clique is safe; an almost clique is a set of vertices W such that there is a v∈W with W-{v} a clique. We report on experiments that show significant reductions of instance sizes for graphs from probabilistic networks and frequency assignment.     

Coloring the cliques of line graphs

The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph.Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals $2$ is NP-complete. We deal with the CCHN of the graph itself as well.     

Bounds for the b-chromatic number of some families of graphs

In this paper we obtain some upper bounds for the b-chromatic number of K_1,s-free graphs, graphs with given minimum clique partition and bipartite graphs. These bounds are given in terms of either the clique number or the chromatic number of a graph or the biclique number for a bipartite graph. We show that all the bounds are tight.     

Chromatic number and complete graph substructures for degree sequences

Given a graphic degree sequence D, let χ(D) (respectively ω(D), h(D), and H(D)) denote the maximum value of the chromatic number (respectively, the size of the largest clique, largest clique subdivision, and largest clique minor) taken over all simple graphs whose degree sequence is D. It is proved that χ(D)≤h(D). Moreover, it is shown that a subdivision of a clique of order χ(D) exists where each edge is subdivided at most once and the set of all subdivided edges forms a collection of disjoint stars. This bound is an analogue of the Hajós Conjecture for degree sequences and, in particular, settles a conjecture of Neil Robertson that degree sequences satisfy the bound χ(D) ≤ H(D) (which is related to the Hadwiger Conjecture). It is also proved that χ(D) ≤ 6/5 ω(D)+ 3/5 and that χ(D) ≤ 4/5 ω(D) + 1/5 Δ(D)+1, where Δ(D) denotes the maximum degree in D. The latter inequality is related to a conjecture of Bruce Reed bounding the chromatic number by a convex combination of the clique number and the maximum degree. All derived inequalities are best possible     

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.     

Duality and perfection for edges in cliques

Given a graph G, let K(G) denote the graph whose vertices correspond with the edges of G. Two vertices of K(G) are joined by an edge if the corresponding edges in G are contained in a clique. This paper investigates some properties of G which force duality theorems for K(G).     

A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs

Let G = (V, E) be a graph with a positive number wt(v) assigned to each v ? v. A weighted clique cover of the vertices of G is a collection of cliques with a non-negative weight y_c assigned to each clique C in the collection such that σ_C:v?CY_C?wt(v) for all v ? V. The problem considered is to minimize σ_Cy_C over all weighted clique covers. A polynomial time algorithm for this problem is presented for graphs that are claw-free and perfect.     

On coloring problems with local constraints

We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ, μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique trees of different heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: first, one can observe on clique trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ, μ)-coloring, list-coloring. Second, clique trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ, μ)-coloring is NP-complete. Last, we show that the μ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from [Ann. Oper. Res. 169(1) (2009), 3–16].     

Copositivity cuts for improving SDP bounds on the clique number

Adding cuts based on copositive matrices, we propose to improve Lovász’ bound θ on the clique number and its tightening θ′ introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies starting with θ′ rapidly increases with the order (and quality requirements). By contrast, the bounds proposed here are relatively cheap in the sense that computational effort is comparable to that required for θ′.