Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

A graph isomorphism algorithm using pseudoinverses

For a graph ofm nodes andn edges, an algorithm for testing the isomorphism of graphs is given. The complexity of the algorithm is a maximum ofO(mn ²) in almost all cases, with a considerable reduction if sparsity is exploited. If isomorphism is present, the pseudoinverses of the Laplace matrices of the graphs will be row and column permutations of each other. Advantage can be taken of certain features of the incidence matrices or of properties of the graphs to reduce computation time.     

On 3-colorable non-4-choosable planar graphs

An L-list coloring of a graph G is a proper vertex coloring in which every vertex v gets a color from a list L(v) of allowed colors. G is called k-choosable if all lists L(v) have exactly k elements and if G is L-list colorable for all possible assignments of such lists. Verifying conjectures of Erdos, Rubin and Taylor it was shown during the last years that every planar graph is 5-choosable and that there are planar graphs which are not 4-choosable. The question whether there are 3-colorable planar graphs which are not 4-choosable remained unsolved. The smallest known example far a non-4-choosable planar graph has 75 vertices and is described by Gutner. In fact, this graph is also 3 colorable and answers the above question. In addition, we give a list assignment for this graph using 5 colors only in all of the lists together such that the graph is not List-colorable. © 1997 John Wiley & Sons, Inc.     

Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces

A sequential graph coloring algorithm and a strict distributed (broadcasting type) algorithm , and an analysis of their performance in scales of random graph spaces is presented. For a space of graphs with n vertices and a mean degree d(n), the number of colors produced is almost surely bounded by about d(n)/logd(n), which is almost surely not more than twice the chromatic number, and the distributed algorithm terminates in O(Max(d(n),logn)) steps.     

Infinitely many pairs of cospectral integral regular graphs

A graph G is called integral if all the eigenvalues of the adjacency matrix A(G) of G are integers. In this paper, the graphs G ₄(a, b) and G ₅(a, b) with 2a+6b vertices are defined. We give their characteristic polynomials from matrix theory and prove that the (n+2)-regular graphs G ₄(n, n+2) and G ₅(n, n+2) are a pair of non-isomorphic connected cospectral integral regular graphs for any positive integer n.     

The Number of Unlabeled Orders on Fourteen Elements

Lacking an explicit formula for the numbers T ₀(n) of all order relations (equivalently: T ₀ topologies) on n elements, those numbers have been explored only up to n=13 (unlabeled posets) and n=15 (labeled posets), respectively.In a new approach, we used an orderly algorithm to (i) generate each unlabeled poset on up to 14 elements and (ii) collect enough information about the posets on 13 elements to be able to compute the number of labeled posets on 16 elements by means of a formula by Erné. Unlike other methods, our algorithm avoids isomorphism tests and can therefore be parallelized quite easily. The underlying principle of successively adding new elements to small objects is applicable to lattices and other kinds of order structures, too.     

Brooks-type theorems for choosability with separation

We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = K_n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998     

AnO(m + n log n) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs

We present an algorithm to compute, inO(m + n log n) time, a maximum clique in circular-arc graphs (withnvertices andmedges) provided a circular-arc model of the graph is given. If the circular-arc endpoints are given in sorted order, the time complexity isO(m). The algorithm operates on the geometric structure of the circular arcs, radially sweeping their endpoints; it uses a very simple data structure consisting of doubly linked lists. Previously, the best time bound for this problem wasO(m log log n + n log n), using an algorithm that solved an independent subproblem for each of thencircular arcs. By using the radial-sweep technique, we need not solve each of these subproblems independently; thus we eliminate the log log nfactor from the running time of earlier algorithms. For vertex-weighted circular-arc graphs, it is possible to use our approach to obtain anO(m log log n + n log n) algorithm for finding a maximum-weight clique—which matches the best known algorithm.     

Enumeration of simple complete topological graphs

A simple topological graph T=(V(T),E(T)) is a drawing of a graph in the plane, where every two edges have at most one common point (an end-point or a crossing) and no three edges pass through a single crossing. Topological graphs G and H are isomorphic if H can be obtained from G by a homeomorphism of the sphere, and weakly isomorphic if G and H have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on n vertices is 2^Θ(n4). We also show that the number of weak isomorphism classes of simple complete topological graphs with n vertices and crossings is at least 2^{n(logn−O(1))}, which improves the estimate of Harborth and Mengersen.     

A Framework for Drawing Planar Graphs with Curves and Polylines

We describe a unified framework of aesthetic criteria and complexity measures for drawing planar graphs with polylines and curves. This framework includes several visual properties of such drawings, including aspect ratio, vertex resolution, edge length, edge separation, and edge curvature, as well as complexity measures such as vertex and edge representational complexity and the area of the drawing. In addition to this general framework, we present algorithms that operate within this framework. Specifically, we describe an algorithm for drawing any n-vertex planar graph in an O(n) × O(n) grid using polylines that have at most two bends per edge and asymptotically-optimal worst-case angular resolution. More significantly, we show how to adapt this algorithm to draw any n-vertex planar graph using cubic Bézier curves, with all vertices and control points placed within an O(n) × O(n) integer grid so that the curved edges achieve a curvilinear analogue of good angular resolution. All of our algorithms run in O(n) time.     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

A non-factorial algorithm for canonical numbering of a graph

A graph certificate or canonical form is a short unique (up to isomorphism) representation of the graph. Thus two graphs are isomorphic iff their certificates are identical. In this paper an O(cⁿ) graph isomorphism algorithm which also yields a certificate of the graph is presented. The certificate produced by this algorithm is a canonical numbering of the vertices of the graph.     

Complete partitions of graphs

A complete partition of a graph G is a partition of its vertex set in which any two distinct classes are connected by an edge. Let cp(G) denote the maximum number of classes in a complete partition of G. This measure was defined in 1969 by Gupta [19], and is known to be NP-hard to compute for several classes of graphs. We obtain essentially tight lower and upper bounds on the approximability of this problem. We show that there is a randomized polynomial-time algorithm that given a graph G with n vertices, produces a complete partition of size Ω(cp(G)/√lgn). This algorithm can be derandomized. We show that the upper bound is essentially tight: there is a constant C > 1, such that if there is a randomized polynomial-time algorithm that for all large n, when given a graph G with n vertices produces a complete partition into at least C·cp(G)/√lgn classes, then NP ⊆ RTime(n ^{O(lg lg n)}). The problem of finding a complete partition of a graph is thus the first natural problem whose approximation threshold has been determined to be of the form Θ((lgn) ^c ) for some constant c strictly between 0 and 1. The work reported here is a merger of the results reported in [30] and [21].     

Generating random regular graphs

An algorithm is described which generates a random labeled cubic graph on n vertices. Also described is a procedure which, if successful, generates a random (0,1)-matrix with prescribed row and column sums. The latter yields procedures which, if successful, generate random labeled graphs with specified degree sequence and random labeled bipartite graphs with specified degree sequences. These procedures can be implemented so that each trial requires time which is linear in the number of vertices plus edges, but in generating a random r-regular graph, the probability of success of a given trial is about $\text{exp}\text{(}\text{(1 ? r}{}^2\text{)}\text{4}\text{)}$, which is prohibitively small for large r. Comparisons are made between the complexities of the two methods of generating random cubic graphs. The two general schemes presented derive from methods which have been used to enumerate regular graphs, both asymptotically and exactly.     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

Gromov hyperbolic cubic graphs

If X is a geodesic metric space and x ₁; x ₂; x ₃ ∈ X, a geodesic triangle T = {x ₁; x ₂; x ₃} is the union of the three geodesics [x ₁ x ₂], [x ₂ x ₃] and [x ₃ x ₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min {3n/16 + 1; n/4}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.     

Improved random graph isomorphism

Canonical labeling of a graph consists of assigning a unique label to each vertex such that the labels are invariant under isomorphism. Such a labeling can be used to solve the graph isomorphism problem. We give a simple, linear time, high probability algorithm for the canonical labeling of a G(n,p) random graph for p[ω(ln⁴n/nlnlnn),1−ω(ln⁴n/nlnlnn)]. Our result covers a gap in the range of p in which no algorithm was known to work with high probability. Together with a previous result by Bollobás, the random graph isomorphism problem can be solved efficiently for p[Θ(lnn/n),1−Θ(lnn/n)].     

Enumeration aspects of maximal cliques and bicliques

We present a general framework to study enumeration algorithms for maximal cliques and maximal bicliques of a graph. Given a graph G, we introduce the notion of the transition graph T(G) whose vertices are maximal cliques of G and arcs are transitions between cliques. We show that T(G) is a strongly connected graph and characterize a rooted cover tree of T(G) which appears implicitly in [D.S. Johnson, M. Yannakakis, C.H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters 27 (1988) 119-123; S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM Journal on Computing 6 (1977) 505-517]. When G is a bipartite graph, we show that the Galois lattice of G is a partial graph of T(G) and we deduce that algorithms based on the Galois lattice are a particular search of T(G). Moreover, we show that algorithms in [G. Alexe, S. Alexe, Y. Crama, S. Foldes, P.L. Hammer, B. Simeone, Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics 145 (1) (2004) 11-21; L. Nourine, O. Raynaud, A fast algorithm for building lattices, Information Processing Letters 71 (1999) 199-204] generate maximal bicliques of a bipartite graph in O(n²) per maximal biclique, where n is the number of vertices in G. Finally, we show that under some specific numbering, the transition graph T(G) has a hamiltonian path for chordal and comparability graphs.     

Low-diameter graph decomposition is in NC

We obtain the first NC algorithm for the low-diameter graph decomposition problem on arbitrary graphs. Our algorithm runs in O(log⁵(n)) time, and uses O(n²) processors. © 1994 John Wiley & Sons, Inc.     

Fast parallel graph searching with applications

This paper presents fast parallel algorithms for the following graph theoretic problems: breadth-depth search of directed acyclic graphs; minimum-depth search of graphs; finding the minimum-weighted paths between all node-pairs of a weighted graph and the critical activities of an activity-on-edge network. The first algorithm hasO(logdlogn) time complexity withO(n ³) processors and the remaining algorithms achieveO(logd loglogn) time bound withO(n ²[n/loglogn]) processors, whered is the diameter of the graph or the directed acyclic graph (which also represents an activity-on-edge network) withn nodes. These algorithms work on an unbounded shared memory model of the single instruction stream, multiple data stream computer that allows both read and write conflicts.