Clique-perfectness and balancedness of some graph classes

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P₄-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P₄-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced.     

On Triangulating Planar Graphs under the Four-Connectivity Constraint

Triangulation of planar graphs under constraints is a fundamental problem in the representation of objects. Related keywords are graph augmentation from the field of graph algorithms and mesh generation from the field of computational geometry. We consider the triangulation problem for planar graphs under the constraint to satisfy 4-connectivity. A 4-connected planar graph has no separating triangles, i.e., cycles of length 3 which are not a face. We show that triangulating embedded planar graphs without introducing new separating triangles can be solved in linear time and space. If the initial graph had no separating triangle, the resulting triangulation is 4-connected. If the planar graph is not embedded, then deciding whether there exists an embedding with at most k separating triangles is NP-complete. For biconnected graphs a linear-time approximation which produces an embedding with at most twice the optimal number is presented. With this algorithm we can check in linear time whether a biconnected planar graph can be made 4-connected while maintaining planarity. Several related remarks and results are included. Received August 1, 1995; revised July 8, 1996, and August 23, 1996.     

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs

Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.     

Graphs of linear clique-width at most 3

A graph has linear clique-width at most k if it has a clique-width expression using at most k labels such that every disjoint union operation has an operand which is a single vertex graph. We give the first characterisation of graphs of linear clique-width at most 3, and we give the first polynomial-time recognition algorithm for graphs of linear clique-width at most 3. In addition, we present new characterisations of graphs of linear clique-width at most 2. We also give a layout characterisation of graphs of bounded linear clique-width; a similar characterisation was independently shown by Gurski and by Lozin and Rautenbach.     

Rainbow graph splitting

Given an integer c, an edge colored graph G is said to be rainbow c-splittable if it can be decomposed into at most c vertex-disjoint monochromatic induced subgraphs of distinct colors. We provide a polynomial-time algorithm for deciding whether an edge-colored complete graph is rainbow c-splittable. For not necessarily complete graphs, we show that the problem is polynomial if c=2, whereas for c≥3 it is NP-complete even if the graph has maximum degree 2c−1. Finally, it remains NP-complete even for 2-edge colored graphs of maximum degree 7c−14.     

Computing the hyperbolicity constant of a cubic graph

In this paper we obtain information about the hyperbolicity constant of cubic graphs. They are a very interesting class of graphs with many applications; furthermore, they are also very important in the study of Gromov hyperbolicity, since for any graph G with bounded maximum degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. We find some characterizations for the cubic graphs which have small hyperbolicity constants, i.e. the graphs which are like trees (in the Gromov sense). Besides, we obtain bounds for the hyperbolicity constant of the complement graph of a cubic graph; our main result of this kind says that for any finite cubic graph G which is not isomorphic either to K₄ or to K_{3, 3}, the inequalities 5k/4≤δ (?)≤3k/2 hold, if k is the length of every edge in G.     

Recognizing d-Interval Graphs and d-Track Interval Graphs

A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-track interval graphs, and (2,…,2) d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unit d-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.     

Matching Algorithms Are Fast in Sparse Random Graphs

We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every non-maximum matching has an augmenting path of length O(log n). This implies that augmenting path algorithms like the Hopcroft-Karp algorithm for bipartite graphs and the Micali-Vazirani algorithm for general graphs, which have a worst case running time of O(m√n), run in time O(m log n) with high probability, where m is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least ln (n) [Average Case Analysis of Algorithms for Matchings and Related Problems, Journal of the ACM, 41(6):1329-1356, 1994]. Our results hold if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani.     

Efficient algorithms for (3, 1) graphs

In this paper, we define a class of graphs which are referred to as (3, 1) graphs. A graph is a member of this class if it has the property that within each set of three vertices, there is at least one edge. We derive a lower bound for the size of a maximum clique in a (3, 1) graph as well as an upper bound for the size of a minimum clique covering. In addition, we show that there exists a linear algorithm for constructing a Hamiltonian circuit in a connected (3, 1) graph and an n⁴-algorithm for finding a minimum coloring in a (3, 1) graph.     

Branch-and-bound algorithm for the maximum triangle packing problem

This work addresses the problem of finding the maximum number of unweighted vertex-disjoint triangles in an undirected graph G. It is a challenging NP-hard combinatorial problem and it is well-known to be APX-hard. A branch-and-bound algorithm which uses a lower bound based on neighborhood degree is presented. A naive upper bound is proposed as well as another one based on a surrogate relaxation of the related integer linear program which is analogous to a multidimensional knapsack problem. Further, a Greedy Search algorithm and a genetic algorithm are described to improve the lower bound. A computational comparison of lower bounds, branch-and-bound algorithm and CPLEX solver is provided using randomly generated benchmarks and well-known DIMACS implementation challenges. The empirical study shows that the branch-and-bound finds the optimal triangle packing solution for small randomly generated MTP instances (up to 100 vertices and 200 triangles) and some DIMACS graphs. For some larger instances and DIMACS challenges graphs, we remark that our lower bound outperforms CPLEX solver regarding the triangle packing solution and the computation time.     

Updating the complexity status of coloring graphs without a fixed induced linear forest

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph P_k denotes a path on k vertices. The ?-Coloring problem is the problem to decide whether a graph can be colored with at most ? colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P₈-free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P₉-free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P₈-free graphs. Additionally, we prove that the precoloring extension version of 4-Coloring is NP-complete for P₇-free graphs, but that the precoloring extension version of 3-Coloring can be solved in polynomial time for (P₂+P₄)-free graphs, a subclass of P₇-free graphs. Here P₂+P₄ denotes the disjoint union of a P₂ and a P₄. We denote the disjoint union of s copies of a P₃ by sP₃ and involve Ramsey numbers to prove that the precoloring extension version of 3-Coloring can be solved in polynomial time for sP₃-free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H-free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

An efficient exact algorithm for triangle listing in large graphs

This paper presents a new efficient exact algorithm for listing triangles in a large graph. While the problem of listing triangles in a graph has been considered before, dealing with large graphs continues to be a challenge. Although previous research has attempted to tackle the challenge, this is the first contribution that addresses this problem on a compressed copy of the input graph. In fact, the proposed solution lists the triangles without decompressing the graph. This yields interesting improvements in both storage requirement of the graphs and their time processing.     

Complexity of graph self-assembly in accretive systems and self-destructible systems

Self-assembly is a process in which small objects autonomously associate with each other to form larger complexes. It is ubiquitous in biological constructions at the cellular and molecular scale and has also been identified by nanoscientists as a fundamental method for building nano-scale structures. Recent years have seen convergent interest and efforts in studying self-assembly from mathematicians, computer scientists, physicists, chemists, and biologists. However most complexity theoretical studies of self-assembly utilize mathematical models with two limitations: (1) only attraction, while no repulsion, is studied; (2) only assembled structures of two dimensional square grids are studied. In this paper, we study the complexity of the assemblies resulting from the cooperative effect of repulsion and attraction in a more general setting of graphs. This allows for the study of a more general class of self-assembled structures than the previous tiling model. We define two novel assembly models, namely the accretive graph assembly model and the self-destructible graph assembly model, and identify a fundamental problem in them: the sequential construction of a given graph. We refer to it as the Accretive Graph Assembly Problem (AGAP) and the Self-Destructible Graph Assembly Problem (DGAP), in the respective models. Our main results are: (i) AGAP is NP-complete even if the maximum degree of the graph is restricted to 4 or the graph is restricted to be planar with maximum degree 5; (ii) counting the number of sequential assembly orderings that result in a target graph (#AGAP) is #P-complete; and (iii) DGAP is PSPACE-complete even if the maximum degree of the graph is restricted to 6 (this is the first PSPACE-complete result in self-assembly). We also extend the accretive graph assembly model to a stochastic model, and prove that determining the probability of a given assembly in this model is #P-complete.     

Super-connected but not super edge-connected graphs

A connected graph G is super-connected (resp. super edge-connected) if every minimum vertex-cut (resp. edge-cut) isolates a vertex of G. In [Super connectivity of line graphs, Inform. Process. Lett. 94 (2005) 191-195], Xu et al. shows that a super-connected graph with minimum degree at least 4 is also super edge-connected. In this paper, a characterization of all super-connected but not super edge-connected graphs is given. It follows from this result that there is a unique super-connected but not super edge-connected graph with minimum degree 3, that is, the Ladder graph L₃ of order 6, and that there are infinitely many super-connected but not super edge-connected graphs with minimum degree 1 or 2.     

Counting triangles in real-world networks using projections

Triangle counting is an important problem in graph mining. Two frequently used metrics in complex network analysis that require the count of triangles are the clustering coefficients and the transitivity ratio of the graph. Triangles have been used successfully in several real-world applications, such as detection of spamming activity, uncovering the hidden thematic structure of the web and link recommendation in online social networks. Furthermore, the count of triangles is a frequently used network statistic in exponential random graph models. However, counting the number of triangles in a graph is computationally expensive. In this paper, we propose the EigenTriangle and EigenTriangleLocal algorithms to estimate the number of triangles in a graph. The efficiency of our algorithms is based on the special spectral properties of real-world networks, which allow us to approximate accurately the number of triangles. We verify the efficacy of our method experimentally in almost 160 experiments using several Web Graphs, social, co-authorship, information, and Internet networks where we obtain significant speedups with respect to a straightforward triangle counting algorithm. Furthermore, we propose an algorithm based on Fast SVD which allows us to apply the core idea of the EigenTriangle algorithm on graphs which do not fit in the main memory. The main idea is a simple node-sampling process according to which node i is selected with probability \fracd_i2m{\frac{d_i}{2m}} where d _i is the degree of node i and m is the total number of edges in the graph. Our theoretical contributions also include a theorem that gives a closed formula for the number of triangles in Kronecker graphs, a model of networks which mimics several properties of real-world networks.     

Tree spanners on chordal graphs: complexity and algorithms

A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The T t-S problem asks whether a graph admits a tree t-spanner, given t. We substantially strengthen the hardness result of Cai and Corneil (SIAM J. Discrete Math. 8 (1995) 359–387) by showing that, for any t4, T t-S is NP-complete even on chordal graphs of diameter at most t+1 (if t is even), respectively, at most t+2 (if t is odd). Then we point out that every chordal graph of diameter at most t−1 (respectively, t−2) admits a tree t-spanner whenever t2 is even (respectively, t3 is odd), and such a tree spanner can be constructed in linear time.

The complexity status of T 3-S still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), 1-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide T 3-S efficiently.     

Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds

Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree. This paper studies enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings of graphs. One part deals with the enumeration of all edge 3-colorings, all total 4-colorings and all L(2,1)-labelings of span 5 of a given connected cubic graph. Branching algorithms to solve these enumeration problems are established. They imply upper bounds on the maximum number of edge 3-colorings, total 4-colorings and L(2,1)-labelings of span 5 in any n-vertex connected cubic graphs. Corresponding combinatorial lower bounds are also provided. The other part of the paper studies dynamic programming algorithms solving counting problems. On one hand, algorithms to count the number of edge k-colorings and total k-colorings for graphs of bounded pathwidth are given. On the other hand, an algorithm to count the number of L(2,1)-labelings of span 4 for graphs of maximum degree three are given.