SIAM J. SCI. COMPUT.
Vol. 29, No. 3, pp. 1042–1072

c 2007 Society for Industrial and Applied Mathematics


NEW ACYCLIC AND STAR COLORING ALGORITHMS
WITH APPLICATION TO COMPUTING HESSIANS∗ASSEFAW H. GEBREMEDHIN† , ARIJIT TARAFDAR† , FREDRIK MANNE‡ , AND
ALEX POTHEN†
Abstract. Acyclic and star coloring problems are specialized vertex coloring problems that arisein the eﬃcient computation of Hessians using automatic diﬀerentiation or ﬁnite diﬀerencing, whenboth sparsity and symmetry are exploited. We present an algorithmic paradigm for ﬁnding heuristic
solutions for these two NP-hard problems. The underlying common technique is the exploitation of
the structure of two-colored induced subgraphs. For a graph G on n vertices and m edges, the timecomplexity of our star coloring algorithm is O(nd2 ), where dk , a generalization of vertex degree,denotes the average number of distinct paths of length at most k edges starting at a vertex in G.
The time complexity of our acyclic coloring algorithm is larger by a multiplicative factor involving
the inverse of Ackermann’s function. The space complexity of both algorithms is O(m). To the bestof our knowledge, our work is the ﬁrst practical algorithm for the acyclic coloring problem. For thestar coloring problem, our algorithm uses fewer colors and is considerably faster than a previously
known O(nd3 )-time algorithm. Computational results from experiments on various large-size test
graphs demonstrate that the algorithms are fast and produce highly eﬀective solutions. The use of
these algorithms in Hessian computation is expected to reduce overall runtime drastically.
Key words. acyclic coloring, star coloring, computation of Hessians, automatic diﬀerentiation,ﬁnite diﬀerences
AMS subject classiﬁcations. 05C15, 05C85, 68R10
DOI. 10.1137/050639879

1. Introduction. The cost involved in computing a Jacobian or a Hessian matrix using automatic diﬀerentiation or ﬁnite diﬀerencing is proportional to the numberof columns in the matrix. When the target derivative matrix A is sparse, huge savings in runtime can be attained by ﬁrst computing a compressed matrix B, where
each column of B is a sum of several structurally “independent” columns of A, andthen recovering the nonzero elements in A from B. Thus, an important componentof the eﬃcient computation of a sparse derivative matrix, whose sparsity pattern is
known a priori, is the problem of partitioning the columns of the matrix into thefewest groups, each consisting of structurally independent columns.
The appropriate notion of structural independence—and the corresponding partitioning problem—depends on whether the derivative matrix to be computed is symmetric or nonsymmetric, and on whether the nonzero entries are to be recoveredfrom the compressed matrix directly or via substitution. Conceptually, direct recovery
corresponds to solving a diagonal system of equations, and recovery via substitution
corresponds to solving a set of simple triangular systems of equations. Several previous studies have shown that these matrix partitioning problems can be modeled
and eﬀectively solved using specialized graph coloring problems and their algorithms[9, 12, 13, 14, 22, 27]. See our earlier work [17] for a comprehensive review.
∗ Received by the editors September 8, 2005; accepted for publication (in revised form) November
7, 2006; published electronically May 10, 2007. This work was supported by the U.S. National Science
Foundation through grants ACI 0203722 and CCF 0515218, by DOE grant DE-FC02-01ER25476 andby subcontract B 533520 from the Lawrence Livermore National Laboratory.
http://www.siam.org/journals/sisc/29-3/63987.html† Department of Computer Science and Center for Computational Science, Old Dominion University, Norfolk, VA 23529-0162 (assefaw@cs.odu.edu, tarafdar@cs.odu.edu, pothen@cs.odu.edu).
‡ Department of Informatics, University of Bergen, N-5020 Bergen, Norway (fredrikm@ii.uib.no).

1042

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1043

This paper is concerned with the design and implementation of eﬀective algorithms for star and acyclic coloring, models for eﬃcient computation of Hessians.
In a star coloring, adjacent vertices receive distinct colors (distance-1 coloring), andevery path on four vertices (P4 ) uses at least three colors. In an acyclic coloring,adjacent vertices receive distinct colors, and every cycle uses at least three colors.
Coleman and Moré [13] showed that star coloring models the partitioning problem
that occurs in the computation of a Hessian via a direct method; Coleman and Cai [9]showed that the corresponding model in a substitution-based computation is acyclic
coloring. Both problems, whose objectives are to minimize the number of colors used,
are known to be NP-hard [9, 13]. As we show in section 2, these problems are also
hard to approximate.
Star coloring as a model for direct Hessian computation was preceded by twoless accurate models: the distance-2 coloring model due to McCormick [27] and therestricted star coloring model due to Powell and Toint [28]. Similarly, acyclic coloring
as a model for Hessian computation via substitution was preceded by a less accurate
model, triangular coloring, due to Coleman and Moré [13]. These models and theinterrelationships amongst them are discussed in detail in section 5.
In a previous work [17], we suggested a simple heuristic algorithm for the starcoloring problem. In each step of that algorithm, the color of a vertex is determinedby examining every P4 starting at the vertex. The time complexity of the algorithm
for a graph on n vertices is O(nd3 ), where dk denotes the average number of pathsof length at most k edges starting at a vertex. A similar O(nd2 )-time algorithm for
restricted star coloring, originally due to Powell and Toint [28], exists. However, whenused for solving the star coloring problem, the latter algorithm uses signiﬁcantly morecolors than the O(nd3 )-time algorithm mentioned earlier.
Although Coleman and Cai [9] identiﬁed acyclic coloring as the model for computing a Hessian via a substitution method, the algorithm they suggested is an algorithm
for triangular coloring. In their approach, ﬁrst a graph G is constructed by addingedges to the input graph G, and then a distance-1 coloring algorithm is applied on
the graph G . A similar approach for triangular coloring was taken earlier by Coleman and Moré [13]. An optimal solution for the triangular coloring problem is notnecessarily an optimal solution for the acyclic coloring problem. Moreover, working
with a denser graph G is undesirable for large-scale problems, since the approach
may require excessive storage space and lead to memory overﬂow. As for the acyclic
coloring problem, we are not aware of any previous practically relevant algorithm.
In this paper, we present new algorithms for both the acyclic and the star coloring
problems. The common paradigm underlying the two algorithms is the exploitationof the structure of two-colored induced subgraphs. In the acyclic coloring case, every
subgraph induced by any two color classes is a collection of trees; the corresponding
structure in the star coloring case is a collection of stars. In both cases, the twocolored induced subgraphs partition the edge set of the input graph. Our algorithms
are based on these observations.
The algorithms presented in this paper are greedy—they progressively extend apartial coloring by processing one vertex at a time. In each step, a vertex is assigned
the smallest (assuming colors are positive integers) allowable color with respect tothe current partial coloring, and the color assigned to the vertex remains unchanged
during the course of the algorithm. Greedy coloring heuristics stand in contrast
to iterative, local improvement heuristics, where the color assigned to a vertex maychange several times during the course of an algorithm in an attempt to ultimately

1044

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

reduce the number of colors used. Greedy coloring heuristics are in general fast, whichmakes them attractive approaches for solving subproblems in scientiﬁc computing
applications, such as the case in this paper. An important issue in greedy coloringalgorithms is the order in which vertices are processed. We consider several eﬀective
ordering techniques in this paper.
A key component of our new algorithms is the eﬃcient management of two-coloredinduced subgraphs. For the acyclic coloring case, the disjoint-set data structure is used
for this purpose; for the star coloring case, a simpler data structure is shown to be
suﬃcient. In addition, a few intricate techniques which yet use simple data structures
are employed to avoid two-colored cycles in the acyclic coloring case, and two-colored
P4 ’s in the star coloring case. The time complexity of the star coloring algorithmis O(nd2 ), and that of the acyclic coloring algorithm is larger by a multiplicative
factor involving the inverse of Ackermann’s function. The space complexity of bothalgorithms is O(m), where m denotes the number of edges in a graph. The acyclic
coloring algorithm will be presented (in section 3) before the star coloring algorithm(in section 4) to reﬂect that the former in an algorithmic sense corresponds to themore general case.
We have implemented the new acyclic and star coloring algorithms presented inthis paper as well as several previously known algorithms for related coloring problems;
the latter algorithms will be discussed in section 6. Results from experiments carriedout on various large-size test graphs show that the new algorithms are highly eﬀective,
both in terms of the number of colors used and in practical runtime. On the test graphs
used, the number of colors used by the acyclic coloring algorithm is observed to bevery close to (within a factor of two) the coloring number of a graph—the numberof colors used by a greedy distance-1 coloring algorithm that employs a smallest lastvertex ordering. The coloring number is an important graph parameter with close
relationship to graph notions such as degeneracy, maximal core, and arboricity. The
runtime of the acyclic coloring algorithm is observed to be nearly the same as thatof a greedy distance-2 coloring algorithm. In comparison with our implementationof an algorithm for triangular coloring—the previously known approach for Hessiancomputation via a substitution method—the acyclic coloring algorithm runs faster,uses fewer colors, and requires less memory and storage space. In agreement with timecomplexity analyses, our new star coloring algorithm is observed to be signiﬁcantly
faster than our previous O(nd3 )-time algorithm—it oﬀers a relative speedup as highas ten on the test graphs used. Moreover, the new algorithm uses slightly fewer colors.
In comparison with the restricted star coloring algorithm of Powell and Toint [28],which is of the same time complexity as the new star coloring algorithm proposed here,
our algorithm signiﬁcantly reduces the number of colors used. In terms of observed
runtime, the new star coloring algorithm is slower than the restricted star coloringalgorithm by only a small factor, typically two.
2. Background.
2.1. Preliminary concepts and notations. Throughout this paper, we consider simple, undirected graphs without loops or parallel edges. Two classes of(sub)graphs that we have need for are trees and stars. A tree is a connected graphwithout any cycle, and a forest is a collection of trees. A star is a complete bipartite
graph in which one of the vertex sets consists of a single vertex. In a star with atleast two edges, we call the vertex at which the edges meet the hub of the star.
We denote an edge whose endpoints are the vertices v and w by vw. Two distinct
vertices v and w are distance-k neighbors if a shortest path connecting them consists

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1045

Table 2.1
Characterization of subgraphs induced by a pair of color classes. The coloring variants arelisted in an increasing order of restrictiveness; correspondingly, the two-colored induced subgraphs
get increasingly less connected as one goes from top to bottom in the table.
Coloring variant
Distance-1 coloring
Acyclic coloring
Star coloring
Distance-2 coloring

A two-colored induced subgraph
A bipartite graph
A collection of trees
A collection of stars
A distance-2 matchingof at most k edges. We denote the set of distance-k neighbors of a vertex v, excluding
the vertex v itself, by Nk (v). As usual, the degree of a vertex is the number of edges
incident on it. We extend this notion and deﬁne the degree-k of a vertex v, denotedby dk (v), to be the number of distinct paths of length at most k edges starting at v.
(Two paths are distinct if they diﬀer in at least one edge.) We denote the average
degree-k in a graph by dk . Note that degree-1 is synonymous with degree, and thatthe degree-2 of a vertex v is equal to the number of edges that are incident either onv or on vertices adjacent to v. Note also that in general dk (v) ≥ |Nk (v)|.
A distance-k coloring of a graph G = (V, E) is a mapping φ : V → {1, 2, . . . , p}such that whenever vertices v and w are distance-k neighbors, φ(v) = φ(w). By
deﬁnition, two distance-k neighboring vertices are distance-k  neighbors for k  > k,and a distance-k coloring is a distance-k  coloring for k  < k. The kth power of agraph G = (V, E) is the graph Gk = (V, F ), where vw ∈ F whenever vertices v and w
are distance-k neighbors in G. A mapping φ is a distance-k coloring of a graph G if
and only if φ is a distance-1 coloring of the graph Gk . A star coloring of a graph is adistance-1 coloring with the additional requirement that every path on four vertices
uses at least three colors. An acyclic coloring of a graph is a distance-1 coloring withthe further restriction that every cycle uses at least three colors. In a distance-k, astar, an acyclic, or any other coloring variant on a graph, a color class is a set ofvertices that have received the same color.
The names star and acyclic coloring are due to the structures of subgraphs induced
by any two color classes. In an acyclically colored graph, a subgraph induced by any
two color classes is clearly a collection of trees, and thus acyclic. Similarly, in a starcolored graph, a subgraph induced by any two color classes is a collection of stars.
It is easy to see that a two-colored connected induced subgraph here ought to be astar, for otherwise there would exist a two-colored path on four vertices, violating a
condition of star coloring. These structures are used in the design of the acyclic andstar coloring algorithms to be presented in the next two sections. Although not so
useful for algorithm design, the structures of two-colored induced subgraphs in thecases of distance-1 and distance-2 coloring are also interesting. A coloring of a graphis a distance-1 coloring if and only if every two-colored induced subgraph is a bipartite
graph. In the case of a distance-2 coloring, every two-colored induced subgraph is aset of edges in which a pair of edges is apart by a path of length at least two edges
in the original graph, a structure appropriately called a distance-2 matching. Theseobservations on two-colored induced subgraphs are summarized in Table 2.1.
2.2. Complexity results. The objective of an optimization problem associatedwith each of the coloring variants we have introduced is to minimize the number ofcolors used. Lin and Skiena [26] proved that the distance-k graph coloring problem
is NP-hard for every ﬁxed integer k ≥ 1. Coleman and Moré [13] showed that the1046

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

star coloring problem is NP-hard even if the graph is bipartite. The acyclic coloring
problem was proven to be NP-hard by Coleman and Cai [9].
The distance-1 coloring problem is also known to be hard to approximate: for agraph on n vertices, there exists δ > 0 such that approximating distance-1 coloring
within O(nδ ) is NP-hard (Corollary 10.1 in [5]). We use this to prove similar inapproximability results for acyclic and star coloring. We ﬁrst introduce some notation.
The distance-k chromatic number of a graph G, denoted by χk (G), is the least numberof colors required to distance-k color G. The acyclic and star chromatic numbers aredeﬁned analogously, and are denoted by χa and χs , respectively.
Theorem 2.1. There exists ﬁxed  > 0 such that it is NP-hard to approximate
the acyclic chromatic number χa (G) of a graph G within O(n ), where n is the numberof vertices in G.
Proof. The reduction is from distance-1 coloring, and it is a small modiﬁcationof the reduction for proving the NP-completeness of acyclic coloring in Coleman andCai [9].
Assume that we are given a graph G = (V, E) which we are required to distance-1
color; from G we create a new graph H = (W, F ) for acyclic coloring as follows. Let
Δ denote the maximum degree of a vertex in G. Each edge uv ∈ E is replaced bya subgraph (a gadget) in H consisting of vertices u , v  , and Δ new vertices w1 , w2 ,. . . , wΔ ; and edges join vertices u and v  to every one of the Δ vertices wi .
We claim that G has a distance-1 coloring using p colors if and only if H has anacyclic coloring using p colors, where 3 ≤ p ≤ Δ.
Suppose G has a distance-1 coloring with p colors. In any edge uv ∈ E, thevertices u and v receive distinct colors. In the graph H, assign u the same color asu, and v  the same color as v. Since each vertex wi is adjacent only to the pair ofvertices u and v  , it can be assigned any one of the p − 2 colors distinct from the twocolors that have been used for u and v  ; note that the quantity p − 2 is positive (there
exists a color for the vertex wi ) since p is assumed to be at least three. The coloringof H obtained by “processing” every edge in G in this fashion is acyclic. To see this,notice that every cycle in H contains one u vertex, one v  vertex, and at least one
wi vertex from the gadget we created for some edge uv ∈ E, and these three vertices
receive distinct colors in H. Hence every cycle in H uses at least three colors, andone direction of the claim follows.
Now consider an acyclic coloring of H with p colors, again where 3 ≤ p ≤ Δ.
We claim that the vertices u and v  corresponding to an edge uv ∈ E receive
distinct colors. Suppose not. Then every pair of vertices wi and wj in this gadget
would have to be colored with distinct colors, or else there would be a cycle u , wi , v  ,wj , u which would be colored with two colors. But then this subgraph of H would
need Δ + 1 colors, contradicting the choice of p.
Thus in every gadget the vertices u and v  receive distinct colors in the acyclic
coloring, and these same colors can be assigned to the vertices u and v to obtain adistance-1 coloring of G using at most p colors.
There exists δ > 0 such that approximating distance-1 coloring within O(nδ ) is
NP-hard [5], where n = |V |, the number of vertices in G. Let N denote the numberof vertices in H. Then N = n + Δ|E| = O(n + n3 ). Thus it follows that there exists
an  > 0 such that approximating acyclic coloring within O(N  ) is NP-hard.
Under stronger complexity conjectures (N P = ZP P , the class of problems withpolynomial time zero-error randomized algorithms), we can prove that it is hard to
approximate acyclic coloring within O(n1/3− ), using a technique similar to that inNEW ACYCLIC AND STAR COLORING ALGORITHMS

1047

Agnarsson and Halldórsson [3].
We can also prove inapproximability results for star coloring, using the samegadget used in the acyclic coloring proof. We omit the details.
Theorem 2.2. There exists ﬁxed  > 0 such that it is NP-hard to approximate
the star chromatic number χs (G) of a graph G within O(n ).
2.3. Related work. Some of the coloring problems introduced in section 2.1
have been studied by other authors, from an application or a pure graph-theoretic
point of view. Krumke, Marathe, and Ravi [24] studied the role of distance-2 coloringin channel assignment problems in radio networks. Kumar et al. [25] have undertakena related study on scheduling problems in wireless networks. In these two studies,
several approximation and distributed algorithms for distance-2 coloring of disk andother special classes of graphs have been suggested. Balakrishnan et al. [6] showedthat the problem of maximizing concurrent transmissions in certain ad-hoc wirelessnetworks can be modeled as a maximum cardinality distance-2 matching problem, aproblem related to distance-2 coloring as discussed at the end of section 2.1. The
distance-2 matching problem was ﬁrst studied and shown to be NP-hard by Stockmeyer and Vazirani [29].
Agnarsson and Halldórsson [2] have studied distance-k coloring of planar graphs,
and a similar study of chordal graphs is available in Agnarsson, Greenlaw, andHalldórsson [1]. Acyclic colorings were ﬁrst deﬁned and studied by Grünbaum [21],who asked whether the acyclic chromatic number χa (G) of a graph G satisﬁes the inequality χa (G) ≤ Δ + 1. A negative answer to this question was given by Erdös, whoproved probabilistically the existence of graphs where χa (G) ≥ Δ4/3− [23]. Borodin[7] proved that every planar graph can be acyclically colored using at most ﬁve colors. Star coloring has recently been studied by Albertson et al. [4], who showed thatevery acyclic coloring that uses q colors can be reﬁned to a star coloring with at most
2q 2 − q colors. These authors also prove that planar graphs have star colorings withat most 20 colors, and they exhibit an example in which 10 colors are required. For
more pointers to theoretical works on distance-k, acyclic, and star coloring, see themonograph by Jensen and Toft [23] and our earlier work [17]. The focus of this paper
is on practical, fast, suboptimal algorithms for acyclic and star coloring.
3. The new acyclic coloring algorithm.
3.1. Overview. Suppose a subset U ⊂ V of the vertices of a graph G = (V, E)
has been colored satisfying the two requirements of an acyclic coloring. As discussed
in section 2.1, every subgraph of G induced by a set of vertices assigned any twocolors is a forest. Furthermore, every edge in G both of whose endpoints are in theset U of colored vertices belongs to a unique tree (in a two-colored forest). Therefore,
the union of all possible two-colored forests induced by the vertices in the set U is acollection of edge-disjoint trees. Our algorithm maintains such a collection of trees
eﬃciently and extends the partial coloring by processing one vertex at a time.
We use the illustration in Figure 3.1 to provide an overview of the algorithm.
The graph shown at the left is the input graph G which has been partially colored,
and v is the only vertex that remains to be colored. The right half of Figure 3.1
shows two-colored forests induced by the rest of the vertices of the graph. The input
graph currently uses four colors, red, blue, green, and yellow (to ease black-and-white
viewing, each colored vertex in the ﬁgure has been labeled with a letter reﬂecting thecolor used). Thus there could exist at most six two-colored induced forests. Out ofthese, the subgraph induced by green and yellow vertices is a graph whose edge set

1048

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN
R

B

G
v

v
R

B

G

v
R

B

G

B

Y

B

G
R

v

Y

R

B

G

B

G

R

B

G
B
R

Y

B

R
v

G

v

Y

G
B

B

R

Y

Fig. 3.1. Left: A partial acyclic coloring of a graph; vertex v is the only vertex that remains to
be colored. Every other vertex has been assigned one of the four colors red, blue, green, or yellow;
the label on each vertex reﬂects the color used. Right: All of the nonempty, two-colored induced
subgraphs; each subgraph is a forest.

is empty. The remaining ﬁve forests are depicted in the ﬁgure. Each of the red-blueand blue-green forests consists of two trees, while each of the other forests consists ofa single tree. In the example, all of the two-colored trees are incident on the vertex v.
The task of choosing a valid color for the vertex v can be divided into two naturalparts. The ﬁrst part involves excluding the colors of each of the distance-1 neighborsof v from its set of allowable colors. In our illustration, this results in the exclusion of
the colors red and blue from the allowable set of colors for v. The second part involves
ensuring that a color chosen for the vertex v does not lead to a two-colored cycle in
the graph G. Since the vertex v (and, in general, any vertex in a graph) could be partof many, arbitrarily long cycles, the second part is more diﬃcult than the ﬁrst, whichis conﬁned to the distance-1 neighborhood of v in G.
The key point in our algorithm is the detection of a potential two-colored cyclethat involves the vertex v in an eﬃcient way. In particular, the cycle detection isdone eﬃciently by examining two-colored trees incident on v, a task accomplishedby visiting the distance-2 (and not any further) neighborhood of v once. Due to the
distance-1 coloring requirement in an acyclic coloring, an odd cycle would necessarily
use at least three colors. Thus in avoiding two-colored cycles, we will be concerned
only with even cycles.
A two-colored cycle that involves the vertex v can arise only if the following two
conditions are satisﬁed:
1. the vertex v is adjacent to two vertices in a two-colored tree, and2. these adjacent vertices are of the same color.
Note that condition 2 restricts the concern to only even cycles, for if the vertex v isadjacent to two vertices with diﬀerent colors in a two-colored tree, the corresponding
cycle involving v is of odd length and thus uses three colors, posing no concern. For
example, in Figure 3.1, though vertex v is adjacent to two vertices in the upper redblue tree, v will not induce a cycle in that tree since the adjacent vertices have distinct
colors.
Now let Fv denote a collection of two-colored trees that are incident on the vertex

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1049

v and satisfy the aforementioned two conditions. For each tree Tv ∈ Fv , let c1 denotethe color of the vertices adjacent to the vertex v, and let c2 be the other color usedin the tree Tv . Then, for each tree Tv , we exclude the color c2 from the allowable setof colors for the vertex v, for otherwise v might be assigned the color c2 , creating a
two-colored cycle involving v. In Figure 3.1 this process would lead to the exclusionof the color yellow from the allowable set of colors for the vertex v, for otherwise a
two-colored cycle could arise in the red-yellow tree.
When both the ﬁrst and the second tasks discussed above are completed for thevertex v, we know exactly the colors that cannot be assigned to v, and thus we canchoose the smallest allowable color for v.
To complete the overview of the algorithm, we now need to update the collectionof two-colored trees to reﬂect the fact that the vertex v has been colored. The update
can be performed in two stages. In the ﬁrst stage, edges vw that connect the vertex
v and an already colored vertex w are grouped into two-colored stars. In the second
stage, these stars are merged with existing two-colored trees as needed. A point thatshould be noted here is that the second stage of the update may cause previously
disconnected trees in a two-colored forest to be connected. For example, if the vertex
v in Figure 3.1 receives the color green, then the two (currently disconnected) trees in
the green-blue forest need to be merged. Just as the task of choosing a color for thevertex v, we will show that the task of updating the collection of two-colored trees
after v is assigned a color can be accomplished by visiting the distance-2 neighborhoodof v once.
3.2. Detailed description. For an eﬃcient implementation of the algorithm
sketched in section 3.1, we use the disjoint-set data structure to maintain the collectionof two-colored trees. For a discussion of the disjoint-set data structure, see, e.g., [15].
A set in our context corresponds to a two-colored tree, and an element of a set
corresponds to an edge. The disjoint-set data structure supports three operations:
makeSet, find, and union. Operation makeSet(e) creates a new set consistingof the element e. Operation find(e) returns the representative element of the set towhich element e belongs, and operation union(e1 , e2 ) merges the two sets S(e1 ) andS(e2 ) to which elements e1 and e2 belong.
Further, in our implementation of the sketched algorithm, we use the two arrays
color and forbiddenColors for coloring purposes. The vertex-indexed array color is used
to store the colors assigned to vertices. In particular, color[u] = c indicates that thevertex u has been assigned the color c, a value that once set remains unchanged during
the course of the algorithm. The color-indexed array forbiddenColors is used to markthe colors that are forbidden to a speciﬁc vertex. In particular, forbiddenColors[c] = u
indicates that the color c is impermissible for the vertex u; otherwise the color c is acandidate color for the vertex u. Unlike the array color, the value stored at a particularindex in the array forbiddenColors varies during the course of the algorithm, an issue
that will be clear in a moment.
3.2.1. The main routine. The driver routine in our acyclic coloring algorithm
is outlined in Algorithm 3.1 and the current section is devoted to its discussion. The
subroutines called by Algorithm 3.1 will be presented in section 3.2.2.
Leaving the initialization of various data structures in line 2 aside for a moment,
the body of the outermost for-loop of Algorithm 3.1 consists of two parts. The ﬁrst
part (lines 4–10) is concerned with ﬁnding a color for the vertex v, the current vertex
in the iteration over the vertex set V . The second part (lines 11–16) deals with
updating the collection of two-colored trees incident on the vertex v.

1050

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

Algorithm 3.1. Input: a graph G. Eﬀect: ﬁnds an acyclic coloring of G.
1: procedure AcyclicColoring(G = (V, E))
2:
Initialize data structures3:
for each v ∈ V do
4:for each colored w ∈ N1 (v) do
5:forbiddenColors[color[w]] ← v
6:for each colored w ∈ N1 (v) do
7:for each colored x ∈ N1 (w) do
8:
if forbiddenColors[color[x]] = v then9:
preventCycle(v, w, x)
10:color[v] ← min{i > 0, forbiddenColors[i] = v}
11:for each colored w ∈ N1 (v) do grow two-colored stars around the vertex v
growStar(v, w)
12:
13:
for each colored w ∈ N1 (v) do
14:
for each colored x ∈ N1 (w), x = v do
15:
if color[x] = color[v] then16:mergeTrees(v, w, x)  merge trees T1  vw and T2  wx if T1 = T2

Finding a color. Pursuant to the ﬁrst requirement of acyclic coloring, the for-loop
in lines 4–5 marks the colors of the distance-1 neighbors of the vertex v as forbidden
colors to v. The subsequent for-loop in lines 6–9 forbids additional colors that can
result in two-colored cycles involving the vertex v, to enforce the second requirementof acyclic coloring. Here, a subset of the two-colored trees incident on the vertex
v—through edges wx, where w is an already colored vertex adjacent to v and x is analready colored vertex adjacent to w—is examined. The routine preventCycle (tobe discussed in section 3.2.2) checks whether the vertex v is connected to the twocolored tree containing the edge wx via two edges. If this turns out to be the case, theroutine forbids the color of the vertex x from being a candidate color for the vertex
v by updating the global array forbiddenColors. The if-test in line 8 ensures that a
two-colored tree incident on the vertex v is investigated only if there is a potential fora two-colored cycle to arise in the same tree; recall that the upper red-blue tree in
Figure 3.1 need not be examined while coloring the vertex v since it cannot lead toa two-colored cycle involving v. The if-test also avoids an unnecessary computation:
once a color c in a two-colored tree T is forbidden to the vertex v to prevent a potential
two-colored cycle C (that involves T and v), then the tree T need not be investigatedany further in the determination of a color for the vertex v, for the existence of any
other cycle C  (that also involves T and v) would only result in the exclusion of thesame color c.
Once all the colors that are not allowed for the vertex v are marked in the arrayforbiddenColors, the array is scanned sequentially in search of the ﬁrst index in which
a value other than v is stored. This corresponds to the smallest allowable color forthe vertex v and is chosen as the color for v (line 10). The array forbiddenColors is
initialized at the beginning of the algorithm with some value outside the set V . This
array can be used without being reinitialized while coloring another vertex, since ineach iteration a unique vertex is colored (i.e., the identity of a vertex serves as a“time-stamp”).
Updating the collection of two-colored trees. The remainder of Algorithm 3.1 isconcerned with creating and updating two-colored trees incident on the vertex v. ThisNEW ACYCLIC AND STAR COLORING ALGORITHMS

1051

task is done in two stages, reﬂected by the two for-loops in lines 11–12 and lines 13–16.
In the ﬁrst stage (the ﬁrst for-loop), two-colored trees consisting only of edges incident
on the vertex v are grown. More precisely, the structures grown are two-colored stars,
and the hub of each star is the vertex v. To this end, for every edge vw that connects
the vertex v with an already colored vertex w, (1) a new two-colored star consisting
only of the edge vw is created, and (2) if there is already a similarly two-colored star
S with one or more edges of the form vw (hence color[w] = color[w ]), then the newly
created star (edge vw) is merged with S. Both of these items are achieved by the callto the routine growStar in line 12; the details of this routine will be discussed in
section 3.2.2.
At the end of the for-loop in lines 11–12, every edge vw connecting v and an
already colored vertex w has been placed in a star in the right two-colored forest.
There may now be a need for another level of merges in a forest, constituting thesecond stage of the data structure update. Such merges involve stars grown at thecurrent iteration, and trees grown in iterations prior to the coloring of v. The pieceof code in lines 13–16 determines whether there is a need for such merges, and if so,
updates the disjoint-set data structure appropriately. In particular, for each coloredvertex w adjacent to v, and each colored vertex x adjacent to w with color[x] = color[v],the routine mergeTrees is called in line 16 with the arguments v, w, and x. The
routine checks whether the tree that contains the edge vw is the same as the tree that
contains the edge wx; if the two trees turn out to be diﬀerent, then they are merged.
To illustrate the points discussed in the previous two paragraphs without revealing
the details of the routines growStar and mergeTrees, consider the example in
Figure 3.1. Suppose the vertex v has been assigned the color green. At the end of
the for-loop in lines 11–12, two stars are grown around the vertex v. These are thestar (path) B–v–B and the star R–v–R, where B and R stand for a blue and a redneighbor of the vertex v, respectively. In the subsequent for-loop, the star R–v–R ismerged with the only tree in the current red-green forest. In the same loop, the star
B–v–B is ﬁrst merged with one of the two disconnected trees in the current blue-green
forest, and then the resulting tree is further merged with the other tree. As a result,the blue-green forest now becomes a single tree (to be more precise, a path on eight
vertices).
3.2.2. The subroutines. Let us now take an inside look at the routines preventCycle, growStar, and mergeTrees. In the discussion below, we will referto the actions performed on the vertex v in lines 4–16 of Algorithm 3.1 as processing
vertex v.
Avoiding two-colored cycles. The routine preventCycle (see Algorithm 3.2)
takes three vertices v, w, and x as input parameters: v is the vertex currently being
processed, w is a colored vertex adjacent to v, and x is a colored vertex adjacent tow. The primary task of the routine is to forbid the color of the vertex x from being
chosen as a color for the vertex v, if it could lead to a two-colored cycle in the input
graph. This would happen if the vertex v is incident on the two-colored tree to which
the edge wx belongs via two edges. An auxiliary task of the routine is to update an
associated data structure.
To determine whether or not a vertex v is connected to a two-colored tree via
two edges in an eﬃcient way, we mark each two-colored tree containing an edge wx
incident on the vertex v. While doing so, if a tree is marked twice, then we knowthat the vertex v is incident on the tree via two edges. We use an edge-indexed arraycalled ﬁrstVisitToTree for this purpose. An index of the array ﬁrstVisitToTree is the1052

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

Algorithm 3.2. Input: the vertex v being colored, a colored neighbor w of v, and acolored neighbor x of w. Associated data structure: ﬁrstVisitToTree[e] = (p, q) indicates thatﬁrstVisitToTree[e] was last set when processing vertex p and at that time the tree represented
by the edge e was ﬁrst visited through the edge pq. Eﬀect: (1) updates the array ﬁrstVisitToTree, or (2) excludes color[x] from the allowable set of colors for v if it could otherwise
lead to a two-colored cycle involving v.
1: procedure preventCycle(v, w, x)
2:e ← find(wx) edge wx belongs to the 2-colored tree T represented by edge e
3:
4:
5:
6:
7:

(p, q) ← ﬁrstVisitToTree[e]if p = v then
 T is being visited from vertex v for the ﬁrst timeﬁrstVisitToTree[e] ← (v, w)
else if q = w then
 T is connected to vertex v via at least two edges
forbiddenColors[color[x]] ← v

ID of the representative edge of a two-colored tree. A vertex pair (p, q) is stored atindex e of the array to indicate that ﬁrstVisitToTree[e] was last set when processing
the vertex p, and at that time the two-colored tree whose representative edge ise was ﬁrst visited through the edge pq. In ﬁrstVisitToTree and other similar data
structures used elsewhere in this paper, the word ﬁrst refers to the context in which
the neighborhood of the vertex p being processed is visited. The array ﬁrstVisitToTree
is globally declared and initialized at the beginning of Algorithm 3.1 with a pair ofvalues not corresponding to any vertex. As in the array forbiddenColors, the “marker”
vertex p in the array ﬁrstVisitToTree serves as a time-stamp. Hence, this array neednot be reinitialized while processing another vertex.
The routine preventCycle begins by getting the two-colored tree T to which
the edge wx belongs. Let e be the representative edge of T returned by the findoperation. In line 3, the vertex pair (p, q) stored at index e of the array ﬁrstVisitToTree
is retrieved. If p = v, then the implication is that the tree T is being visited fromthe vertex v for the ﬁrst time. To reﬂect this, the vertex pair (v, w) is stored atﬁrstVisitToTree[e]. If, on the other hand, p = v, then there are two possibilities,
corresponding to the cases q = w and q = w. The case q = w implies that the tree
T has previously been visited from the vertex v, but the visit was through the sameedge vw. This occurs if the vertex w is adjacent to at least two vertices (besides thevertex v) in the tree T , and does not cause the color of the vertex x to be a forbidden
color for the vertex v. The second case, q = w, implies that the tree T has previously
been visited from the vertex v through an edge other than vw. In this case, settingcolor[v] = color[x] would create a two-colored cycle, and therefore color[x] is forbiddenfrom being a color for the vertex v.
Updating the collection of two-colored trees. As discussed earlier, the ﬁrst stage of
updating the collection of two-colored trees incident on the vertex v being processed
involves growing two-colored stars around the vertex v. This is achieved by the calls
growStar(v, w) made in line 12 of Algorithm 3.1 for each colored vertex w adjacentto the vertex v.
To achieve the desired merging of edges into two-colored stars in an eﬃcientmanner, we maintain a color-indexed array, ﬁrstNeighbor, in which we store pairsof vertices. The array is used to determine whether or not a particular color isencountered for the ﬁrst time while visiting the distance-1 neighborhood of a particularvertex. Speciﬁcally, we let ﬁrstNeighbor[c] = (p, q) to indicate that while processing
the vertex p, the vertex q was the ﬁrst-to-be-encountered neighbor having the color

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1053

Algorithm 3.3. Input: the vertex v being processed and a colored neighbor w of v.
Associated data structure: ﬁrstNeighbor[c] = (p, q) indicates that the vertex q is the ﬁrst-tobe-encountered neighbor of the vertex p having the color c. Eﬀect: (1) creates a new twocolored tree Tvw consisting only of the edge vw, and (2) either updates the array ﬁrstNeighboror merges the tree Tvw with a two-colored star being grown around v.
1: procedure growStar(v, w)
2:
3:
4:
5:
6:
7:
8:

makeSet(vw) create a new tree Tvw consisting only of edge vw(p, q) ← ﬁrstNeighbor[color[w]]if p = v then
 a neighbor of v with color color[w] encountered for 1st time
ﬁrstNeighbor[color[w]] ← (v, w)
else
 merge Tvw with a two-colored star being grown around v
e1 ← find(vw); e2 ← find(pq)union(e1 , e2 )Algorithm 3.4. Input: the vertex v being processed, a colored neighbor w of v, and aneighbor x of w having the same color as v. Eﬀect: merges the tree containing the edge vw
with the tree containing the edge wx, if the two trees are distinct.
1: procedure mergeTrees(v, w, x)
2:
3:
4:

e1 ← find(vw); e2 ← find(wx)if e1 = e2 thenunion(e1 , e2 )c. As the array ﬁrstVisitToTree discussed earlier, the array ﬁrstNeighbor is globallydeclared and initialized in Algorithm 3.1, and can be used without reinitialization
while iterating through the vertex set V .
The routine growStar (Algorithm 3.3) begins by creating a two-colored tree
(star) consisting only of the edge vw, a task accomplished by the call makeSet(vw).
The routine then retrieves the vertex pair (p, q) stored at the index color[w] of thearray ﬁrstNeighbor. If p = v, then the implication is that the color used by the vertex
w is encountered for the ﬁrst time while visiting the vertices adjacent to the vertex
v. To signify this, the vertex pair (v, w) is stored at the index color[w] of the arrayﬁrstNeighbor. Otherwise, if p = v, then the implication is that a vertex q (distinct
from w) that has the same color as the vertex w has already been encountered while
visiting the neighbors of the vertex v. In this case, the edge vw—the two-colored star
just created—is merged with the (growing) two-colored star containing the edge pq.
The second stage of the update involves merging the two-colored stars just grownwith existing two-colored trees as needed. This is achieved by the calls to mergeTrees
made in line 16 of Algorithm 3.1. Each such call is made with the arguments v, w,
and x, where v is the vertex currently being processed, w is a colored vertex adjacentto v, and x is a colored vertex adjacent to w with color[x] = color[v]. The routine
mergeTrees (Algorithm 3.4) ﬁrst queries for the representative edges e1 and e2 of
the two-colored trees T1 and T2 to which the edges vw and wx, respectively, belong.
If e1 = e2 , then it means that the two trees T1 and T2 are distinct, and therefore theyneed to be merged. Otherwise no further action needs to be taken.
3.3. Complexity. The outermost for-loop in Algorithm 3.1 consists of n = |V |iterations. In each iteration, the two visits to the distance-2 neighborhood of thevertex v being processed, i.e., the for-loops in lines 6–9 and 13–16, constitute thedominant part of the computation. On each visited neighbor, a constant number

1054

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

of operations is performed. Thus, disregarding the time spent on updating andquerying
the disjoint-set data structure, the time complexity of the algorithm isO( v∈V d2 (v)) = O(nd2 ).
The disjoint-set data structure in our context contains at most m distinct elements, the edges of G. Thus there can be at most m − 1 union calls and m makeSet
calls. Further, there can be at most m = 2n · d1 + 3n · d2 ≤ 5n · d2 find calls, since theroutine find is called once in the procedure PreventCycle and twice in each of theprocedures growStar and mergeTrees. In our implementation of the disjoint-set
data structure, we use path compression for the find operation and union-by-size forthe union operation to achieve the best runtime performance. When these techniques
are used, the average time spent on each such operation is at most α(m , m), where α
is the inverse of Ackermann’s function [15]. Thus the overall time complexity of ouracyclic coloring algorithm is O(nd2 · α(m , m)). Clearly, the space complexity of thealgorithm is O(m).
4. The new star coloring algorithm.
4.1. Overview. Our star coloring algorithm is based on the same idea as theacyclic coloring algorithm presented in section 3. Instead of managing a collectionof edge-disjoint two-colored trees, we now manage a collection of edge-disjoint twocolored stars. Recall that the hub of a star is the vertex at which the edges meet.
The key diﬀerence between the acyclic and the star coloring algorithms stems fromthe following fact: An edge may be added to a tree at any vertex of the tree, whereas
the only way an edge may be added to a star is at the hub of the star. A consequenceof this fact is that the addition of an edge to a star does not lead to the merging of
two existing stars. Hence, a simpler data structure than disjoint-set suﬃces. We use
a one-dimensional array that maps edges to stars, and a similar array that maps stars
to hubs, to manage the collection of two-colored stars.
Figure 4.1 provides an overview of the algorithm. Part (a) of the ﬁgure shows
the input graph G where every vertex except v has been colored consistent with therequirements of a star coloring. The illustration uses the six colors red, blue, green,
yellow, pink, and black (Bk). Parts (b) through (f) show a subset of the two-coloredstars with nonempty edge sets that are incident on v.
Since a star coloring is also a distance-1 coloring, the set of colors used by vertices adjacent to the vertex v is impermissible for v. Enforcing this requirement isstraightforward. In addition, any color that leads to a two-colored path involving v
and three other vertices is impermissible for v. There are exactly two cases that need
to be considered to identify and forbid a color of this type.
• Case 1. If vertex v has two adjacent vertices w and x of the same color, thenthe color of every vertex adjacent to w, and the color of every vertex adjacent
to x should be excluded from the allowable set of colors for v.
• Case 2. If vertex v has exactly one adjacent vertex w of color c, and w belongs
to a star S containing at least two edges but is not the hub of S, then thecolor used by the hub of S should be disallowed from being a candidate color
for v.
Parts (b) and (c) of Figure 4.1 illustrate Case 1; neither the color blue nor the color
green can be assigned to the vertex v. Similarly, parts (d) and (e) illustrate Case 2;
the colors green and pink used by the hubs of the respective stars are not allowed forthe vertex v. As illustrated in part (f), if the star S in a situation similar to Case 2
has only one edge, then it does not impose any additional color restriction on thevertex v. We say that the hub of such a star consisting of a single edge is undeﬁned.

1055

NEW ACYCLIC AND STAR COLORING ALGORITHMS
Bk

P

Y

Y

B
B

v

(a)

Y

Bk

Y

Y
Y

G

Y

R

G

P

G

R

R

v

(b)

R

R

v

(c)

R

v

v

(d)

v

(e)

(f)

Fig. 4.1. (a): A partial star coloring of a graph; vertex v is the only vertex that remains to
be colored. (b)–(f): A subset of the two-colored induced subgraphs incident on the vertex v; eachsubgraph is a collection of stars. The illustration uses the six colors red, blue, green, yellow, pink,
and black (Bk).

The hub is deﬁned later if and when another edge joins the star, in which case thepoint of incidence between the two edges becomes the hub.
Like the acyclic coloring algorithm, our star coloring algorithm iterates over thevertex set V in some order, coloring one vertex at a time. In the step where a vertex v
is colored, the color used by each adjacent vertex and every additional color identiﬁedby checking Cases 1 and 2 is excluded from the allowable set of colors for v. Thenthe smallest permissible color is chosen and assigned to the vertex v. After this,every edge vw connecting the vertex v and an already colored vertex w is placed in
the appropriate two-colored star. In particular, if an edge vw is incident on some(color[v],color[w])-star S, then the edge vw joins the star S; otherwise, the edge vw
forms a star on its own with an undeﬁned hub. Unlike the acyclic coloring algorithm
in which the addition of an edge to a two-colored tree may result in the merging of
two existing trees, the addition of an edge to a two-colored star does not lead to themerging of two existing stars.
4.2. Detailed description. To maintain the collection of two-colored stars effectively, we use an edge-indexed array, star, that maps edges to stars, and a starindexed array, hub, that maps stars to hubs. In particular, star[vw] = s signiﬁes thatthe edge vw belongs to the star s, and hub[s] = u indicates that the hub of the stars is the vertex u. We work with the two separate arrays, star and hub, in order todistinguish between stars consisting of at least two edges (having deﬁned hubs) andstars consisting of a single edge (having undeﬁned hubs). In addition, we make use of
the two arrays color and forbiddenColors in just the same way as in section 3.
Our star coloring algorithm is outlined in Algorithm 4.1. The body of the outerfor-loop has two parts. The ﬁrst part, the piece of code in lines 4–16, is concernedwith ﬁnding a color for the vertex v, the current vertex in the iteration over the vertex
set. The second part deals with updating the collection of two-colored stars incident
on the vertex v, and is achieved by the call to updateStars in line 17. Hereafter,
we shall refer to the actions performed on the vertex v in lines 4–17 as processing thevertex v.
Finding a color. The for-loop in lines 4–15 of Algorithm 4.1 determines the colors
that cannot be assigned to the vertex v. In line 5, the color used by a vertex w
adjacent to the vertex v is marked as a forbidden color for v, since a star coloringis also a distance-1 coloring. To determine and forbid additional colors that lead totwo-colored paths involving v and three other vertices, Cases 1 and 2 outlined earlier
need to be checked. To detect Case 1 in an eﬃcient manner, we use the color-indexedarray ﬁrstNeighbor which stores pairs of vertices: ﬁrstNeighbor[c] = (p, q) indicates

1056

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

Algorithm 4.1. Input: a graph G. Associated data structure: ﬁrstNeighbor[c] = (p, q)
indicates that the vertex q is the ﬁrst-to-be-encountered neighbor of the vertex p having thecolor c; treated[y] = x indicates that the color of every vertex adjacent to the vertex y isalready forbidden from being a color for the vertex x. Eﬀect: ﬁnds a star coloring of G.
1: procedure StarColoring(G = (V, E))
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Initialize data structures
for each v ∈ V dofor each colored w ∈ N1 (v) do
forbiddenColors[color[w]] ← v(p, q) ← ﬁrstNeighbor[color[w]]if p = v then Case 1
if treated[q] = v thentreat(v, q)
 forbid colors of neighbors of q
treat(v, w)
 forbid colors of neighbors of w
else
ﬁrstNeighbor[color[w]] ← (v, w)
for each colored x ∈ N1 (w), x = v do
if x = hub[star[wx]] then potential Case 2
forbiddenColors[color[x]] ← v
color[v] ← min{i > 0, forbiddenColors[i] = v}
updateStars(v)Algorithm 4.2. Input: the vertex v being processed and a colored vertex w adjacent tov. Eﬀect: excludes the colors used by vertices adjacent to w from the allowable set of colors
for v, and updates the array treated to reﬂect this.
1: procedure treat(v, w)
2:
3:
4:

for each colored x ∈ N1 (w) do
forbiddenColors[color[x]] ← v
treated[w] ← v

that when processing the vertex p, the vertex q was the ﬁrst neighbor with color c to
be encountered. (An array with the same name was used for a similar purpose in theacyclic coloring algorithm discussed in the previous section.) In line 6, a lookup in
the table ﬁrstNeighbor at the index color[w] is made and the stored value is retrievedin the vertex pair (p, q).
If p = v, then the implication is that a vertex which is distinct from, but has
the same color as, the vertex w—the vertex q—has already been encountered while
visiting the distance-1 neighbors of the vertex v. This clearly corresponds to Case
1. The appropriate action to be taken is to forbid the colors used by the vertices
adjacent to q and the colors used by the vertices adjacent to w. The calls to thesubroutine treat (outlined in Algorithm 4.2) in lines 9 and 10 do precisely that. In
connection with this case, we use the vertex-indexed array treated in which we store
vertices; treated[y] = x indicates that the color of every vertex adjacent to the vertex
y has already been marked as a forbidden color for the vertex x. The if-test in line 8 is
performed to avoid unnecessary computation in the case where color[w] is encountered
for a third time or later.
If, on the other hand, p = v, then the implication is that the color used by thevertex w is encountered for the ﬁrst time while visiting the distance-1 neighborhood

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1057

Algorithm 4.3. Input: the vertex v being processed. Eﬀect: adds edges vw, where w iscolored, to appropriate two-colored stars.
1: procedure updateStars(v)
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

for each colored w ∈ N1 (v) do
if ∃x ∈ N1 (w) where x = v and color[x] = color[v] then vw, wx ∈ E
hub[star[wx]] ← w
 this may already be truestar[vw] ← star[wx]else(p, q) ← ﬁrstNeighbor[color[w]]if (p = v) and (q = w) then vw, vq ∈ E ∧ color[w] = color[q]hub[star[vq]] ← v
 this may already be truestar[vw] ← star[vq]else vw forms a new star
starID ← starID + 1
star[vw] ← starIDof the vertex v. This information is recorded in line 12 for future use. The piece ofcode in the subsequent for-loop takes a proactive measure in anticipation of Case 2. In
particular, the loop iterates over edges wx that belong to existing two-colored stars.
For each star to which an edge wx belongs, if the star has a deﬁned hub and the hub
is the vertex x, then the color of x is forbidden from being a color for the vertex v(line 14). Potentially, this corresponds to Case 2; if the vertex v is later found to havea neighbor vertex w = w with the same color as w, then it reduces to Case 1. Recall
that only stars containing at least two edges have deﬁned hubs; for a star with only
one edge the test in line 14 will fail and therefore will not impose an additional color
restriction (cf. Figure 4.1 (f)).
At the end of the for-loop in lines 4–15, every color that is not allowed to be acolor for the vertex v is marked in the array forbiddenColors. The smallest permissible
color is then chosen and assigned to the vertex v in line 16.
As with the arrays used in section 3, in the arrays ﬁrstNeighbor and treated themarker vertex p serves as a time-stamp; it is used to determine whether the information stored in the data structures concerns the vertex currently being processed.
These data structures are initialized at the beginning of Algorithm 4.1, and no reinitialization is required in the course of iteration over the vertex set.
Updating the collection of two-colored stars. The call to the routine updateStars(outlined in Algorithm 4.3) is made at line 17 to update the collection of two-coloredstars to reﬂect the fact that the vertex v has been assigned a color. In Algorithm 4.3,
each edge vw that joins the vertex v with an already colored vertex w is placed in
an existing or a new two-colored star depending on the colors of the vertex v and its
distance-2 neighbors. The edge vw joins an existing star if (1) there exists an edge wx
and color[v] = color[x], or (2) there exists an edge vq and color[w] = color[q]. The ﬁrst
case can be detected by looking at the distance-1 neighborhood of the vertex w; for thesecond case, the information in the array ﬁrstNeighbor, which is set in Algorithm 4.1,
is utilized. Clearly, in the ﬁrst case the vertex w becomes the hub of the resulting star
(if it was not already so), and in the second case the vertex v becomes the hub (again,
if it was not already so). If neither of cases (1) or (2) turns out to be positive, thenthe edge vw forms a new two-colored star on its own with an undeﬁned hub. Noticethat the deﬁnitions of the hubs in lines 4 and 9 are necessary, since the edges wx and1058

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

vq could be single-edge-stars with undeﬁned hubs at the time the routine is called.
4.3. Complexity. Given a graph on n vertices and m edges, the computational
work involved in each of the n iterations of the outer for-loop in Algorithm 4.1 is
proportional to d2 (v). Hence the overall time complexity of our star coloring algorithmis O(nd2 ). Its space complexity is clearly O(m).
5. Coloring models in Hessian computation. We have experimentally compared the new algorithms for acyclic and star coloring presented in this paper withpreviously suggested algorithms for these and other related coloring problems that
occur in the computation of sparse Hessians. In this section, we brieﬂy review suchcoloring models and discuss their interrelationships. In section 6, we will discuss
corresponding greedy algorithms.
One step in an eﬃcient computation of a sparse derivative matrix A using automatic diﬀerentiation (or ﬁnite diﬀerencing) is to use structural information about A
to partition its n columns into p disjoint groups, with p as small as possible. This
step can be posed as a problem of seeking an n × p seed matrix S whose (j, k) entry
is deﬁned as follows:
1 if column aj belongs to group k,
(5.1)
sjk =
0 otherwise.
Since the matrix S speciﬁed by (5.1) corresponds to a partitioning of the columns of
the matrix A, in every row r of the matrix S there exists exactly one column c inwhich the entry src is equal to one. In the automatic diﬀerentiation literature, there
exist approaches that use a seed matrix where a row-sum is not necessarily equal toone [19]. Such approaches are not partitioning-based as they allow a column of A tobe placed in more than one group. In this paper we consider only seed matrices thatdeﬁne a partition.
The speciﬁc criteria used to deﬁne a seed matrix S depend on whether the entriesof the matrix A are to be recovered from the compressed representation AS directly(by conceptually solving a diagonal system of equations) or via substitution (by conceptually solving a set of triangular systems of equations). The criteria also depend onwhether the derivative matrix A is Jacobian (nonsymmetric) or Hessian (symmetric).
In general, a seed matrix S suitable for a direct method requires a larger p compared
to one suitable for a substitution method. On the other hand, the recovery of entries
via substitution incurs an additional, but aﬀordable, computational cost.
5.1. Models for direct methods. Curtis, Powell, and Reid [16] observed thata structurally orthogonal partition of a Jacobian matrix A—a partition of the columnsof A in which no two columns in a group share a nonzero at the same row index—
gives a seed matrix S where the entries of A can be directly recovered from thecompressed representation AS. Obviously, a structurally orthogonal partition could
also be used in the context of computing a Hessian if one were to settle for not
exploiting the available symmetry. Following this approach, McCormick [27] showedthat a structurally orthogonal partition of a Hessian is equivalent to a distance-2
coloring of its adjacency graph.
The adjacency graph G(A) of a Hessian A has a vertex for each column, and anedge joins column vertices ai and aj whenever the entry aij , i = j, is nonzero; thediagonal entries in A are assumed to be nonzero, and they are not explicitly represented by edges in G(A). In the distance-2 coloring model for structurally orthogonal

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1059

partition as well as in other models discussed in this section, a set of vertices having
the same color corresponds to a set of columns that belong to the same group in the
induced partition. In other words, each column of the seed matrix corresponds to acolor class.
Powell and Toint [28] were the ﬁrst to suggest symmetry-exploiting partitions forboth direct and substitution-based methods for computing Hessians. When translated
to a coloring φ of the adjacency graph, the partition Powell and Toint suggested fora direct Hessian computation requires that (1) φ be a distance-1 coloring, and (2)in every path on three vertices P3 = v, w, x, the vertices v and x receive diﬀerent
colors whenever φ(w) > min{φ(v), φ(x)}. We call a coloring that satisﬁes these two
requirements a restricted star coloring. Notice that, unlike in a distance-2 coloring, ina restricted star coloring, the terminal vertices v and x in a path v, w, x are allowed
to have the same color as long as the color of the middle vertex w is lower in value.
Coleman and Moré [13] generalized the approach of Powell and Toint and showedthat a symmetrically orthogonal partition of a Hessian suﬃces for a direct recovery
of its entries from a compressed representation. A partition of the columns of a
Hessian matrix A is symmetrically orthogonal if for every nonzero element aij , either(1) the group containing column aj has no other column with a nonzero in row i,or (2) the group containing column ai has no other column with a nonzero in row j.
Coleman and Moré established that a symmetrically orthogonal partition of a Hessian
is equivalent to a star coloring of its adjacency graph.
5.2. Models for substitution methods. Based on the work of Powell andToint [28], Coleman and Moré [13] found a coloring model for a partitioning of a
Hessian matrix A that deﬁnes a seed matrix S such that the nonzero entries of A canbe recovered from the compressed representation AS via a (restricted) substitution
method. The recovery of the entries of the matrix A from the matrix AS requires
solving a triangular system of equations, a system that heavily relies on the structureof A. Appropriately, Coleman and Moré called the model triangular coloring. Givena graph G = (V, E), a mapping φ : V → {1, 2, . . . , p} is a triangular coloring if
there exists a vertex ordering π such that (1) φ is a distance-1 coloring, and (2) inevery P3 = v, w, x, the vertices v and x receive diﬀerent colors whenever π(w) >max{π(v), π(x)}. A vertex ordering π that is well suited for triangular coloring exists
and will be discussed in section 5.3.
Triangular coloring exploits symmetry only to a limited extent. This limitation
was later addressed by Coleman and Cai [9], who introduced a generalized notion ofsubstitutable partitions for which they provided a simple graph-theoretic characterization. In particular, they proved that an acyclic coloring of the adjacency graph ofa Hessian induces a substitutable partition of its columns. They also showed that,using an acyclic coloring, the nonzeros of the Hessian can be recovered from its compressed representation by considering a pair of color classes (groups of columns) at atime. The key diﬀerence between a partition induced by a triangular coloring and apartition induced by an acyclic coloring is the following. Triangular coloring induces
a partition that deﬁnes one large, coupled triangular system of equations, whereas
acyclic coloring induces a partition that deﬁnes several smaller, decoupled triangularsystems of equations, each deﬁned by a pair of color classes.
Table 5.1 summarizes the coloring models in Hessian computation discussed thus
far. In the table, the coloring variants are listed in an increasing order of restrictiveness, with the least constrained variant at the top and the most constrained variant
at the bottom. In the following subsection, we present results that make the interre-

1060

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

Table 5.1
Overview of coloring models used in Hessian computation. In each case, the adjacency graph
G = (V, E) of the underlying Hessian is used, and the mapping φ : V → {1, 2, . . . , p} deﬁnes
a coloring. In addition to the input graph G, the deﬁnition of triangular coloring assumes theexistence of a vertex ordering π. *Powell and Toint [28] stated these models using their equivalentmatrix partitioning counterparts; the translations into graph colorings are due to Coleman andMoré [13].
NameColoring conditions

Computation modeled

Acyclic

1. vw ∈ E ⇒ φ(v) = φ(w)2. every cycle uses ≥ 3 colors
1. vw ∈ E ⇒ φ(v) = φ(w)2. in every P3 = v, w, x :π(w) > max{π(v), π(x)} ⇒ φ(v) = φ(x)1. vw ∈ E ⇒ φ(v) = φ(w)2. every P4 uses ≥ 3 colors
1. vw ∈ E ⇒ φ(v) = φ(w)2. in every P3 = v, w, x :φ(w) > min{φ(v), φ(x)} ⇒ φ(v) = φ(x)1. vw ∈ E ⇒ φ(v) = φ(w)2. P3 = v, w, x ∈ G ⇒ φ(v) = φ(x)substitution
Coleman and Cai [9]restricted substitution
Powell and Toint [28]∗Coleman and Moré [13]directColeman and Moré [13]restricted direct
Powell and Toint [28]∗Coleman and Moré [13]direct (ignores symm.)
McCormick [27]Triangular

Star
Restricted
starDistance-2

lationships among these variations more precise.
5.3. Interrelationships. Recall that we denote specialized chromatic numbersby χ with an appropriate subscript. For example, χa (G) denotes the acyclic chromatic
number of G. In Lemma 5.1, we relate the acyclic, star, and restricted star chromatic
numbers of a graph. Similarly, in Lemma 5.2 we show the relationship among theacyclic, triangular, and restricted star chromatic numbers of a graph.
Lemma 5.1. For every graph G, χa (G) ≤ χs (G) ≤ χrs (G).
Proof. Let φ be a star coloring of a graph G. Observe that a cycle in G on threevertices uses three colors, since φ is also a distance-1 coloring of G. Moreover, a cycleon at least four vertices contains a P4 and therefore uses at least three colors. Hence
φ is an acyclic coloring of G, and the ﬁrst inequality follows.
For the second inequality, we show that if φ is a restricted star coloring of G, thenφ is also a star coloring of G. Let P = v, w, x be a P3 in G. Since φ is a restricted
star coloring, φ(v) = φ(w) and φ(w) = φ(x). Furthermore, either φ(v) = φ(x)or φ(v) = φ(x) > φ(w) holds. In the former case, in any P4 in G that contains
the path P , adjacent vertices have diﬀerent colors, and the P4 uses at least threecolors, satisfying the requirements of a star coloring. To see that the latter case also
fulﬁlls the requirements of a star coloring, consider any P4 = v, w, x, y in G that
extends the path P in one of its ends. (A similar argument would hold for a pathu, v, w, x that extends P in the other end.) Again, since φ is a restricted star coloring,φ(y) = φ(x). Moreover, the relationship φ(y) = φ(w) holds, since otherwise therelationship φ(x) > φ(w) = φ(y) in the path w, x, y would hold, contradicting thefact that φ is a restricted star coloring. Hence, in the path v, w, x, y, adjacent vertices
have diﬀerent colors, and at least three colors are used. Therefore φ is a star coloringof G.
Lemma 5.2. For every graph G, χa (G) ≤ χt (G) ≤ χrs (G).
Proof. Suppose φ is a triangular coloring of a graph G for a vertex ordering π.
We show that φ is then an acyclic coloring of G. Consider any cycle C in G, and let

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1061

z be the vertex in C with the highest index in the ordering π. Since C is a cycle,
there exists a path P = u, z, v in C for some vertices u and v. Further, since φ is atriangular coloring, φ(u) = φ(v) by choice of z. Since φ is also a distance-1 coloring,both of these colors are distinct from φ(z). Hence, the cycle C uses at least threecolors, and therefore φ is an acyclic coloring of G.
We now show the second inequality. Suppose φ is a restricted star coloring ofa graph G on n vertices. Consider a vertex ordering π = v1 , v2 , . . . , vn such thatthe sequence {φ(vi )} is nondecreasing. In other words, the ordering π is such thatvertices in the same color class are listed consecutively, and the color classes in turnare listed in increasing order. Consider any path P = v, w, x on three vertices in G.
Since φ is a restricted star coloring, a pair of adjacent vertices in the path P havediﬀerent colors. There are two possibilities regarding the terminal vertices v and x
in P : either φ(v) = φ(x) or φ(v) = φ(x) > φ(w). In the former case, the path P
trivially satisﬁes the requirements of a triangular coloring. Given the ordering π asdeﬁned in the proof, the path P in the latter case also satisﬁes the requirements ofa triangular coloring, since π(w) < min{π(v), π(x)}. Hence, the coloring φ and theordering π together deﬁne a triangular coloring of G.
The inequalities in Lemmas 5.1 and 5.2 can easily be extended in both ends.
Clearly, χ1 (G) ≤ χa (G) holds, since an acyclic coloring is also a distance-1 coloring. In a distance-2 colored graph, the vertices in every P3 use three distinct colors.
Hence, a distance-2 coloring is also a restricted star coloring, implying the relationshipχrs (G) ≤ χ2 (G). We summarize these relationships in Theorem 5.3.
Theorem 5.3. For every graph G, the following relationships hold:χ1 (G) ≤ χa (G) ≤ χt (G) ≤ χrs (G) ≤ χ2 (G) = χ1 (G2 ),χ1 (G) ≤ χa (G) ≤ χs (G) ≤ χrs (G) ≤ χ2 (G) = χ1 (G2 ).
The relationship between χt (G) and χs (G) is not clear. There are examples ofstar colorings where there does not exist a vertex ordering that makes a given starcoloring a triangular coloring. An example would be a star coloring of a graph inwhich every vertex is the hub of a two-colored P3 . Conversely, there are examples ofcolorings that are triangular but not star. A simple example is a two-colored P4 in
which adjacent vertices have diﬀerent colors. Thus the class Cs (G) of star coloringsof a graph G and the class Ct (G) of triangular colorings of G are such that neither
Ct (G) ⊆ Cs (G) nor Cs (G) ⊆ Ct (G) holds. However, the relationship χt (G) ≤ χs (G)might still hold. We leave settling the latter issue as an open problem.
The last equality in Theorem 5.3 follows from the fact that a distance-2 coloringof G is equivalent to a distance-1 coloring of the square graph G2 . In fact, most of
the coloring variants on a graph G = (V, E) listed in Table 5.1 can also be viewed asa distance-1 coloring of an appropriately deﬁned “ﬁlled” graph G = (V, E ∪ F ).
When the original graph G is the adjacency graph of a Hessian, the ﬁlled graphs inthe distance-2 and triangular coloring cases have interesting interpretations. The ﬁlled
graph in the distance-2 coloring case (the square graph G2 ) is the column intersection
graph of the underlying Hessian A. The column intersection graph of a matrix has
a vertex for each column, and an edge between a pair of columns exists whenever
the two columns share nonzero entries at some common row index. In the case of atriangular coloring for a given vertex ordering π, the ﬁlled graph G , in which eachﬁll edge f is generated as per the speciﬁcation(5.2)∀P3 = v, w, x in G : π(w) > max{π(v), π(x)} ⇒ f = vx,

1062

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

is the column intersection graph of the lower triangular part Lπ of the permuted
matrix P T AP , where P is a permutation matrix deﬁned by the ordering π. These
relationships were observed and used by Coleman and Moré [13], who showed thata smallest last (SL) vertex ordering as a choice for π is particularly well suited fortriangular coloring.
Given a graph on n vertices, a vertex ordering v1 , v2 , . . . , vn is an SL ordering
if for all 1 ≤ i ≤ n, the vertex vi is a vertex with the smallest degree in the graphinduced by vertices v1 , . . . , vi . Here is why an SL ordering is well suited for triangularcoloring: Among the n! possible orderings (permutations) π, an SL ordering minimizes
the maximum number of nonzeros in a row in Lπ . Thus, an SL ordering provides alower bound on the triangular chromatic number, a result proven by Coleman andMoré [13].
Orthogonal to its role in triangular coloring, an SL ordering is also known to
be one of the eﬀective ordering techniques for reducing the number of colors usedby a greedy coloring algorithm. The number of colors used by a greedy distance-1
coloring algorithm that employs an SL ordering to color a graph G is an importantgraph parameter. The parameter is known as the coloring number col(G) of G andis closely related to several other graph notions, including degeneracy, maximal core,
and arboricity [17]. In our context, since an SL ordering can be computed in linear
time in the number of edges, the coloring number is an easy-to-compute, nontrivial
upperbound for the distance-1 chromatic number. As mentioned in the previous
paragraph, the coloring number is also a lower bound for the triangular chromatic
number. Theorem 5.4 summarizes these relationships.
Theorem 5.4. For every graph G, χ1 (G) ≤ col(G) ≤ χt (G).
6. Previous algorithms. Coleman and Cai [9] accurately modeled the partitioning problem that occurs in substitution-based Hessian computation as the acyclic
coloring problem. However, the algorithm they suggested is an algorithm for triangular coloring. Speciﬁcally, they suggested that a ﬁlled graph G be explicitly
constructed as described by the expression (5.2), using an SL vertex ordering for π,
and then that G be distance-1 colored. The same approach has been taken earlier
by Coleman and Moré [13] and in the related software papers [10, 11]. However, as
we will soon show in the current section, it is possible to achieve a triangular coloring of G by using a greedy algorithm that works directly on G. This section also
discusses previously known greedy algorithms for star and distance-k coloring. All of
the algorithms discussed in this section are included in our experiments.
In a previous work [17], we suggested an algorithm for star coloring that enforces
the coloring requirements in a straightforward manner—by checking paths on four
vertices. We refer to this algorithm here as NaiveStarColoring (NS ). Powell andToint [28] suggested an algorithm of the same spirit, formulated in the language ofmatrices, for the restricted star coloring problem. We will call this algorithm here
RestrictedStarColoring (RS ).
Algorithms NS and RS are both greedy. In determining a set of forbidden colors
for a vertex v, algorithm NS consults the colors used by the distance-3 neighbors of v,
whereas algorithm RS checks the colors used by only the distance-2 neighbors. Oncethe set of forbidden colors is obtained, both algorithms choose the smallest color notincluded in the set as the color for the vertex v. In a similar fashion, one can design
greedy algorithms for distance-1 coloring, distance-2 coloring, and triangular coloring
for a given ordering π. We refer to such algorithms as Distance1Coloring (D1),Distance2Coloring (D2), and TriangularColoring (T-π). The suﬃx in theNEW ACYCLIC AND STAR COLORING ALGORITHMS

1063

v

w
x2

x1

x

y
Fig. 6.1. Visualizing a step in greedy coloring algorithms; v is the vertex currently being colored.
Table 6.1 shows how the set of forbidden colors for v is determined in various cases.
Table 6.1
Conditions under which a particular color is forbidden to v (see in conjunction with Figure 6.1).
Here φ is a coloring, and π is a vertex ordering.

D1
D2
NS
RS
T-π

w
alwaysalwaysalwaysalwaysalwaysx1

x2

alwaysalwaysalwaysonly ifπ(w) > max{π(v), π(x)}alwaysonly if φ(w) = φ(y)only if φ(w) > φ(x)only ifπ(w) > max{π(v), π(x)}notation T-π signiﬁes that a speciﬁc vertex ordering π is used by the algorithm.
We use Figure 6.1 in conjunction with Table 6.1 to illustrate how the set of
forbidden colors for a vertex is determined by the various greedy algorithms in coloringa graph G on n vertices and m edges. The tree depicted in Figure 6.1 is not a
subgraph of G, but rather a visualization of the classiﬁcation of the neighborhood
Nk (v) of the vertex v being colored at the current step of the particular algorithm.
The classiﬁcation is based on whether a vertex in the set Nk (v) is already coloredor not. In the ﬁgure, the vertices of the graph G that are one, two, and three edges
away from the vertex v are represented by the tree nodes at the levels w, x, and y,
respectively. A shaded node signiﬁes already colored vertices and an unshaded nodesigniﬁes vertices not yet colored. The shaded nodes at level x are further labeled x1
and x2 , to distinguish between the cases where a vertex w in a path v, w, x is alreadycolored or not.
Table 6.1 summarizes the conditions under which a color used by a vertex in the
scenario described in Figure 6.1 is forbidden to the vertex v for the various algorithms.
Cases x1 and x2 correspond to distinct decisions in algorithms NS and RS. These twocases are indistinguishable in algorithms D2 and T-π and are irrelevant to algorithm
D1. As column x1 in Table 6.1 shows, in algorithms NS and RS, the color of vertex
x in a path v, w, x where vertex w is not yet colored is immediately forbidden to thevertex v. This ensures that any extension v, w, x, y of the path v, w, x would end
up using at least three colors, as desired, since in the step in which the vertex w iscolored, the distance-1 coloring requirement guarantees that the vertex w gets a color
distinct from the colors of vertices v and x. In contrast, in the case where vertex
w is already colored (see column x2 in the table), determining whether the color ofvertex x should be forbidden to vertex v or not requires a further check. In algorithm
NS, the check involves vertices w and y (note that y is three edges away from v). In1064

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

algorithm RS, the check involves vertices w and x. In each of the algorithms listed inTable 6.1, once the set of forbidden colors to the vertex v is determined, the smallest
color not included in the set is chosen as the color for v.
The illustration should make it clear that the complexity of algorithm D1 isO(nd1 ) = O(m), the complexity of each of algorithms D2, RS, and T-π is O(nd2 ),and the complexity of algorithm NS is O(nd3 ).
7. Experimental results.
7.1. Setup. To demonstrate the performance of our new algorithms, we ran
experiments on 29 graphs obtained from molecular dynamics applications [8, 30].
The test graphs were chosen because of their large size and irregular structure. The
left half of Table 7.1 shows the number of vertices |V |, the number of edges |E|, themaximum degree Δ, and the average degree d1 in each test graph. The right half of thetable shows certain computed values that we will discuss shortly. All of the algorithms
used in our experiments were implemented in C++. The hardware used was a Linuxmachine equipped with Dual AMD Opteron Processor 244, 1.8 GHz, 2 GB memory,and 1 GB cache. The operating system was RHEL 3 and the compiler was GCC.
7.2. Algorithms compared and orderings used. In addition to the newacyclic and star coloring algorithms presented in sections 3 and 4—abbreviated henceforth as A and S—in this section, we report experimental results on the algorithms
D1, D2, RS, NS, and T-sl discussed in section 6. The suﬃx sl in the triangularcoloring algorithm indicates that we used an SL vertex ordering as the ordering π
to deﬁne the coloring, since this is optimal as discussed in the paragraph leading to
Theorem 5.4. Algorithms D1 and D2 are included in our experiments primarily toserve as references against which quantities could be normalized.
The order in which vertices are colored in a greedy algorithm determines thenumber of colors used by the algorithm. As mentioned earlier, an SL ordering (moreprecisely, a distance-1 SL ordering) is one of the eﬀective known ordering techniques
for distance-1 coloring. As a natural extension, for algorithms such as D2, where thedistance-2 neighborhood of a vertex is explored at each step, a distance-2 SL ordering(D2SL) can be deﬁned and used to attain a similar beneﬁt. Speciﬁcally, we deﬁne a
D2SL ordering using the quantity |N2 (v)| associated with each vertex v in a graph.
Using linear-time sorting techniques, a D2SL ordering can be computed within thesame order of time as a subsequent distance-2 coloring, i.e., in O(nd2 ) time.
In our experiments (results to be presented in section 7.3), for each of the algorithms D1, D2, RS, NS, S, and A, we used one of the orderings among natural(the order in which vertices appear in the input graph), D1SL, and D2SL orderings
that led to the fewest colors on a majority of the test cases. For algorithm D1, thisordering was D1SL; for algorithms D2, RS, NS, and S, this was the D2SL ordering;and for algorithm A, it was the natural ordering. We have also experimented withappropriately extended variants of incidence degree and largest degree ﬁrst orderings[17]. The results we obtained using these are in general similar to or worse than theones obtained using the SL orderings and hence are not reported here.
In a greedy algorithm for triangular coloring, vertex orderings arise in two diﬀerent
contexts: (1) as part of the deﬁnition of the coloring, and (2) as part of the coloringalgorithm. In terms of an ordering (π) that deﬁnes the coloring, a D1SL orderingin the input graph G is optimal. The same ordering can be used while coloring thevertices sequentially, and that is what we did in algorithm T-sl. To (potentially)
reduce the number of colors used, one could also use a D1SL coloring order based on

1065

NEW ACYCLIC AND STAR COLORING ALGORITHMS

Table 7.1
Test graph statistics (left half ) and computed values (right half ). Column col(G) lists thecoloring number of each graph, and columns D1 and D2 list the runtime in seconds of algorithms
D1 and D2. The last column shows the ratio of number of edges in a derived graph G to that in an
original G; the graph G is obtained from the graph G as per the speciﬁcation in expression (5.2)
where π is an SL vertex ordering in G. The symbol *** indicates that a graph G , being too large
to ﬁt in memory, could not be computed.

ID

Name

|V |

|E|

Δ

d1

col(G)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

er-gre-2
apoa1-2HIV-3er-gre-3
popc-br-3
apoa1-3mol1-2HIV-4
apoa1-4
er-gre-4
popc-br-4
popc-br-5
apoa1-5HIV-6er-gre-6
popc-br-6
apoa1-6mol1-3
popc-br-7
popc-br-8
popc-br-9
er-gre-10
popc-br-10

36,57392,224
11,41436,57324,916
92,224
131,072
11,414
92,22436,57324,916
24,916
92,224
11,41436,57324,916
92,224
131,072
24,916
24,916
24,91636,57324,91653,046
139,351
64,134
169,787
102,058456,220
1,179,648
130,332
1,131,436
451,355
255,047
497,269
2,254,805
412,623
1,482,904
850,0433,864,429
5,636,096
1,316,771
1,914,476
2,668,555
6,511,122
3,587,724

8
8
20
19
22
20
18
39
43
42
43
75
73
116
116
125
123
86
192
275
380
460
514

3
3
11
9
8
10
18
23
25
25
20
40
49
72
81
68
84
86
106
154
214
356
288

24
25
26
27
28
29
tot
tot

mol1-4HIV-10
apoa1-10
HIV-12er-gre-12
popc-br-12(1–23)(1–29)

131,072
11,414
92,224
11,41436,57324,916
1,139,699
1,447,312

14,680,064
1,655,383
17,100,850
2,683,956
10,928,521
5,924,137
35,129,231
88,102,142

224
454
503
760
775
855

224
290
371
470
598
476

|E  |
|E|

4
4
8
8
9
9
11
14
15
15
15
24
25
34
36
38
38
42
54
72
98
124
126

Runtime (sec)
D1
D2
0.01 4.44
0.00 31.74
0.00 0.44
0.00 4.34
0.01 2.05
0.02 26.85
0.08 65.47
0.00 0.58
0.04 28.39
0.01 4.91
0.01 2.35
0.01 3.16
0.08 33.02
0.01 1.74
0.04 9.76
0.03 4.89
0.11 42.14
0.27 123.59
0.04 8.39
0.05 14.67
0.06 25.78
0.16 92.92
0.08 43.83

1.1
1.1
1.6
1.7
1.6
1.7
2.8
2.5
3
3
2.7
4.2
5.2
6
7.8
6.4
8.1
9.8
9
12.4
16.4
30
21

104
115
135
183
198
199

0.59
0.03
0.39
0.05
0.24
0.14

***
***
***
***
***
***

354.3418.29
305.5247.78
275.53116.7

vertex degrees in the ﬁlled graph G derived from G according to the speciﬁcation
given by expression (5.2).
In a method they call slsl, Coleman and Moré [13] explicitly construct such a ﬁlled
graph G using a D1SL ordering in G as π, and then distance-1 color the graph G
using a D1SL ordering in G to obtain a triangular coloring of the original graph G.
We have implemented this method as well; here we call it T-slsl to reﬂect that it is atriangular coloring of the original graph. The last column of Table 7.1 shows the ratioof the number of edges in the derived graph G to that in the original graph G. For 6
out of the 29 test graphs we used (the last six in Table 7.1), the graph G could not
be computed as it was too big to ﬁt in the size of the available memory. The asterisks
used in the corresponding entries in the last column of Table 7.1 indicate this.

1066

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN
6
D2
RS
NS
S
MaxDeg5.5

Colors normalized wrt D1

5

4.5

4

3.5

3

2.5

2

1.5

0

5

10

15
Graph id

20

25

30

10

15
Graph id

20

25

30

4.5
MaxDegT−sl
A
4

Colors normalized wrt D1

3.5

3

2.5

2

1.5

1

0

5

Fig. 7.1. Normalized number of colors used by various greedy algorithms. In algorithm T-sl,
a D1SL ordering of the vertices in G is used to both deﬁne and perform the coloring. Algorithm
D1 uses a D1SL ordering for coloring. In algorithms D2, RS, NS, and S, vertices are colored ina D2SL ordering in G; in algorithm A, vertices are colored in the natural order they appear in G.
The plots are normalized relative to the number of colors used by algorithm D1, i.e., the coloring
numbers of the graphs. These numbers are listed in Table 7.1.

7.3. Results. We will now describe a few ﬁgures and tables that show our experimental results. The ﬁgures will be discussed collectively in section 7.4.
The upper graph of Figure 7.1 displays plots of the number of colors used byalgorithms D2, RS, NS, and S normalized relative to the number of colors used byalgorithm D1, the coloring numbers of the graphs. The bottom graph shows analogous

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1067

2

10

NS
S
RS
T−sl
A

1

Runtime normalized wrt D2

10

0

10

−1

10

−2

10

−3

10

0

5

10

15
Graph id

20

25

30

Fig. 7.2. Execution time comparison. Vertices are colored in the orderings speciﬁed in Figure 7.1. The plots, in semilog scale, are normalized relative to the runtime of Algorithm D2, values
listed under column D2 of Table 7.1.

plots for algorithms T-sl and A. The common curve in the two parts is the plot of the
maximum degrees in the graphs, again normalized relative to the coloring numbers.
The coloring numbers of the graphs, sorted in increasing order, are listed under columncol(G) in Table 7.1.
Figure 7.2 shows semilog plots of the runtimes of algorithms RS, NS, S, T-sl,
and A normalized relative to the runtime of algorithm D2, the values of which arelisted in the column labeled D2 in Table 7.1. Column D1 in the same table shows
the runtimes of algorithm D1. In these two columns as well as in execution times
reported elsewhere in this section, the reported times include time spent on ordering,when applicable, but not time for reading test graph ﬁles from disk.
Figure 7.3 shows a comparison between algorithms A and T-slsl. The results
reported in the ﬁgure concern the test graphs on which the latter could be run successfully, the ﬁrst 23 of the 29 test graphs used.
Table 7.2 shows a summary of the results for the various algorithms; the upperrow gives data summed over all test cases, and the lower row shows data summed
over test cases on which algorithm T-slsl was successfully run.
To show the reduction in number of colors that algorithms D1, D2, RS, NS,
and S were able to get through their use of D1SL or D2SL orderings, we ran thesealgorithms with natural vertex ordering as well. Table 7.3 summarizes the results
obtained. In addition to absolute ﬁgures, the table shows the savings in number ofcolors (as a percentage) and the relative time cost in comparison with a coloring thatuses an appropriate SL ordering (data listed in Table 7.2).

1068

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN
2

3.5

10
T−slslA

T−slslA

1

10

Runtime normalized wrt D2

Colors normalized wrt D1

3

2.5

2

−1

10

−2

1.5

1

0

10

10

−3

0

5

10
15
Graph id

20

25

10

0

5

10
15
Graph id20

25

Fig. 7.3. Comparison of normalized number of colors (left) and normalized runtimes (right)
between algorithms A and T-slsl. The number of colors are normalized relative to that used byalgorithm D1, and the runtimes are normalized relative to that of algorithm D2.
Table 7.2
Top row: Total number of colors and runtime summed over all test graphs. Bottom row: Totals
over test graphs on which algorithm T-slsl could be run successfully (i.e., graphs without asterisks
in Table 7.1). The order in which vertices are colored is as speciﬁed in Figure 7.1.

Colors
Runtime (min)Colors
Runtime (min)

D2
9,240
28.2
3,951
9.6

RS
8,749
34.4
3,734
11

NS
7,636
930
3,207
128

S
7,558
162
3,191
34.5

T-sl
5,065
12.4
2,189
3.8

T-slsl

2,149
41.8

A
4,110
32.5
1,709
7

D1
1,757
0.04
823
0.02

Table 7.3
Top row: Total number of colors and runtime summed over all test graphs, when vertices arecolored in their natural order in an input graph (Nat). Bottom row: Color savings and relative time
cost in comparison with coloring using an appropriate SL ordering (numbers listed in Table 7.2).

Colors
Runtime (min)SL vs. Nat colors saved (%)
SL to Nat time ratio

D2
11,429
4.32
19
6.5

RS
11,275
9.60
22
3.6

NS
9,973
679
23
1.4

S
9,470
126
20
1.3

D1
2,384
0.03
26
1.3

7.4. Discussion. A reader can make several observations from Figures 7.1–7.3
and Tables 7.1–7.3. We highlight the following few points to supplement such observations in the context of Hessian computation.
• The advantage of exploiting sparsity using coloring cannot be overstated. If
all of the Hessians (with the nonzero structures of the test graphs) were to becomputed without exploiting sparsity or symmetry, the time required would
be proportional to 1.5 million steps (the sum total of the vertices in Table 7.1).

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1069

If the strongest coloring model considered here—acyclic coloring—were to be
used, all of these Hessians could be evaluated in about four thousand time
steps (the number of colors, or compressed columns, in the A column at the
top half of Table 7.2). Moreover, in general, coloring constitutes only a small
fraction (typically far less than 10%) of the overall computation time involvedin obtaining numerical values in a derivative matrix [18, 19]. Note that the
total coloring time required to acyclic-color all of the test graphs, totalingover 88 million edges, is about 30 minutes.
• As the upper part of Figure 7.1 shows, among the three algorithms RS, NS,
and S for direct Hessian computation where symmetry is exploited, algorithm
S uses the fewest colors. Algorithm RS uses slightly fewer colors than thesymmetry-ignoring algorithm D2. The diﬀerence in the number of colors
used by algorithms RS and S is signiﬁcant, whereas that between NS and S
is marginal.
• The maximum degree Δ in a graph is a lower bound for the distance-2 chromatic number; this fact is clearly reﬂected in Figure 7.1. One can also seethat for a majority of our test graphs, algorithms RS, NS, and S used morethan Δ colors. However, there were cases, noticeably among the relatively
sparse graphs of ID less than 10, where these algorithms used fewer than Δcolors.
• The more important advantage of algorithm S over algorithm NS is its lower
time complexity, a fact supported by the nearly sixfold reduction in observed
running times, as Figure 7.2 and Table 7.2 attest. Algorithms S and RS havethe same theoretical complexity, and, in practice, algorithm S is observed tobe slower by a small factor.
• As the bottom graph of Figure 7.1 illustrates, the coloring algorithms for
Hessian computation via substitution—algorithms T-sl and A—use many
fewer colors than the coloring algorithms for direct Hessian computation—
algorithms RS, NS, and S. On the test graphs we used, our acyclic coloringalgorithm A consistently used fewer colors than the triangular coloring algorithm T-sl. Moreover, in all of our test cases, algorithm A used fewer than Δcolors, while for algorithm T-sl the statement holds true for a majority, but
not all, of the test cases. Interestingly, the exceptions in the latter case areregular graphs (graphs 7, 18, and 24 in Table 7.1). Note that the reference
against which the number of colors in Figures 7.1 and 7.3 are normalized isa lower bound for triangular coloring.
• As Figure 7.3 shows, our acyclic coloring algorithm A also used fewer colors
than algorithm T-slsl. On the subset of the test cases on which algorithm Tslsl could be run successfully, algorithm A used 20% fewer colors than T-slsl.
In terms of runtime, algorithms A and T-sl are comparable, whereas T-slsl ismuch slower.
• In comparison with a natural ordering, an appropriate SL vertex (re)ordering
for coloring reduced the number of colors used by algorithms D1, D2, RS,
NS, and S by roughly 20% (see Table 7.3). In contrast, the numbers listed
in Table 7.2 show that the savings in number of colors rendered by algorithm
T-slsl compared to algorithm T-sl is only 1.8%, obtained at a cost of runtime
that is larger by a factor of 11. The acyclic coloring algorithm A did not
beneﬁt from an SL ordering.
• Disregarding time for computing vertex orderings, the practical runtimes ofalgorithms D2, RS, S, T-sl, and A are expected to be similar since the time

1070

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN

complexity of each of these algorithms is nearly O(nd2 ). In the observed
runtimes in Figure 7.2, the plots for T-sl and A for the most part lie below
the line y = 1, which corresponds to the runtime of algorithm D2. This ismainly due to the variation in the orderings used: for algorithm D2 (as well
as RS and S) a D2SL ordering in G was used, for algorithm T-sl a D1SL in
G was used, and for algorithm A the natural ordering was used.
• Even when vertices were colored in natural order, the acyclic coloring algorithm A was observed to be slightly faster than the star coloring algorithm S.
On the other hand, time complexity analyses of the two algorithms show A
to be slightly slower than S. The most likely reason for S being slower than A
in practice is that there are many more two-colored stars to be maintained inalgorithm S than there are two-colored trees to be maintained in algorithm A,
which in turn makes the former use more memory operations, and therefore
more runtime.
8. Conclusion. We have presented new algorithms for star and acyclic coloring,models for eﬃcient Hessian computation via direct and substitution methods. We
experimentally demonstrated that the new algorithms outperform previously known
methods. Our acyclic coloring algorithm runs faster, uses fewer colors, and requires
less memory and storage space than the T-slsl triangular coloring method of Coleman
and Moré [13]. In comparison with our implementation of the T-sl triangular coloringalgorithm—which unlike the original algorithm of Coleman and Moré works directly
on an input graph G—the new acyclic coloring algorithm produces fewer colors at
comparable runtime. Our new star coloring algorithm runs faster and uses fewer
colors than our previous algorithm for the same problem [17]. In comparison with thepreviously known restricted star coloring algorithm, our new star coloring algorithm
yields a signiﬁcant reduction in number of colors at the cost of a slight increase inobserved runtime.
Using an acyclic coloring, Coleman and Cai [9] showed that the nonzero entries
of a Hessian can be evaluated via substitution by considering a pair of color classes
at a time. Our new acyclic coloring algorithm has such structures (two-colored trees)in place, which facilitates an eﬃcient implementation of a procedure for recoveringa Hessian from a compressed representation. We have implemented such a routine.
In collaboration with Andrea Walther at the Technical University of Dresden, ourcoloring and Hessian recovery codes have been incorporated in the automatic diﬀerentiation tool ADOL-C [20]. A paper that demonstrates the eﬃcacy of the new star
and acyclic coloring algorithms in the overall process of computing the Hessian ofa given function using automatic diﬀerentiation has been submitted for publicationelsewhere [18]. The results we obtained in our experiments using ADOL-C show thatthe new coloring algorithms render huge savings in overall runtime, and that Hessiancomputation via substitution using acyclic coloring is faster than a direct computation
using star coloring, considering the overall process.
The underlying idea in the new algorithms, the exploitation of two-colored structures, can be extended to bicoloring models in eﬃcient computation of Jacobians [14].
We are currently working in this direction.
We conclude this paper by pointing out a few other directions for further work.
• As discussed in the paragraph immediately after Theorem 5.3, the relationship between the triangular and star chromatic numbers of a graph is notclear. Prove or disprove the claim χt (G) ≤ χs (G).

NEW ACYCLIC AND STAR COLORING ALGORITHMS

1071• The size of a largest clique in a graph is an obvious lower bound for the
distance-1 chromatic number χ1 (G). Analogously, Δ + 1 is a lower bound forthe distance-2 chromatic number χ2 (G), since there exists a clique of thatsize in the square graph G2 . Finding nontrivial lower bounds for acyclic andstar chromatic numbers is a worthwhile issue.
• Appropriate extensions of orderings such as smallest last, largest ﬁrst, andincidence degree helped reduce the number of colors used by our star coloring algorithm, but not that of the acyclic coloring algorithm. It would beinteresting to ﬁnd orderings suitable for the latter algorithm.
Acknowledgments. We thank Jorge Moré for suggesting a comparison between
acyclic and triangular coloring and for his helpful comments on a draft of this paper.
We also thank Paul Hovland for making the test graphs available to us. Our sincere
thanks go to the anonymous referees for their valuable comments on the content andpresentation of this paper and for bringing related works in the literature to ourattention.
REFERENCES[1] G. Agnarsson, R. Greenlaw, and M. M. Halldórsson, On powers of chordal graphs andtheir colorings, Congr. Numer., 100 (2000), pp. 41–65.
[2] G. Agnarsson and M. M. Halldórsson, Coloring powers of planar graphs, SIAM J. Discrete
Math., 16 (2003), pp. 651–662.
[3] G. Agnarsson and M. M. Halldórsson, Coloring powers of planar graphs, in Proceedings ofthe Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia,
2000, pp. 654–662.
[4] M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kündgen, and R. Ramamurthi,Coloring with no 2-colored P4 ’s, Electron. J. Combin., 11 (2004), article R26.
[5] S. Arora and C. Lund, Hardness of approximations, in Approximation Algorithms for NPHard Problems, D. S. Hochbaum, ed., PWS Publishing, Boston, MA, 1997, Chap. 10, pp.
399–446.
[6] H. Balakrishnan, C. L. Barrett, V. S. A. Kumar, M. V. Marathe, and S. Thite, The
distance-2 matching problem and its application to the MAC-layer capacity of ad hoc
wireless networks, IEEE J. Selected Areas in Commun., 22 (2004), pp. 1069–1079.
[7] O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math., 25 (1979), pp. 211–236.
[8] B. Brooks, R. Bruccoleri, B. Olafson, D. States, S. Swaminathan, and M. Karplus,
CHARMM: A program for macromolecular energy, minimization, and dynamics calculations, J. Comput. Chem., 4 (1983), pp. 187–217.
[9] T. F. Coleman and J.-Y. Cai, The cyclic coloring problem and estimation of sparse Hessian
matrices, SIAM J. Algebraic Discrete Methods, 7 (1986), pp. 221–235.
[10] T. F. Coleman, B. Garbow, and J. J. Moré, Software for estimating sparse Jacobian matrices, ACM Trans. Math. Softw., 10 (1984), pp. 329–347.
[11] T. F. Coleman, B. Garbow, and J. J. Moré, Software for estimating sparse Hessian matrices, ACM Trans. Math. Softw., 11 (1985), pp. 363–377.
[12] T. F. Coleman and J. J. Moré, Estimation of sparse Jacobian matrices and graph coloring
problems, SIAM J. Numer. Anal., 20 (1983), pp. 187–209.
[13] T. F. Coleman and J. J. Moré, Estimation of sparse Hessian matrices and graph coloring
problems, Math. Program., 28 (1984), pp. 243–270.
[14] T. F. Coleman and A. Verma, The eﬃcient computation of sparse Jacobian matrices using
automatic diﬀerentiation, SIAM J. Sci. Comput., 19 (1998), pp. 1210–1233.
[15] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms,
2nd ed., MIT Press, Cambridge, MA, 2001.
[16] A. R. Curtis, M. J. D. Powell, and J. K. Reid, On the estimation of sparse Jacobianmatrices, J. Inst. Math. Appl., 13 (1974), pp. 117–119.
[17] A. H. Gebremedhin, F. Manne, and A. Pothen, What color is your Jacobian? Graph
coloring for computing derivatives, SIAM Rev., 47 (2005), pp. 629–705.
[18] A. H. Gebremedhin, A. Pothen, A. Tarafdar, and A. Walther, Eﬃcient computation ofsparse Hessians: An experimental study using ADOL-C, submitted, 2006.

1072

A. H. GEBREMEDHIN, A. TARAFDAR, F. MANNE, AND A. POTHEN[19] A. Griewank, Evaluating Derivatives: Principles and Techniques of Algorithmic Diﬀerentiation, SIAM, Philadelphia, 2000.
[20] A. Griewank, D. Juedes, and J. Utke, ADOL-C: A package for the automatic diﬀerentiationof algorithms written in C/C++, ACM Trans. Math. Softw., 22 (1996), pp. 131–167.
[21] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math., 14 (1973), pp. 390–408.
[22] S. Hossain and T. Steihaug, Computing a sparse Jacobian matrix by rows and columns,
Optim. Methods Softw., 10 (1998), pp. 33–48.
[23] T. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience, New York, 1995.
[24] S. O. Krumke, M. V. Marathe, and S. S. Ravi, Models and approximation algorithms forchannel assignment in radio networks, Wireless Networks, 7 (2001), pp. 567 – 574.
[25] V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan, End-to-end packetscheduling in wireless ad-hoc networks, in Proceedings of the Fifteenth Annual ACM-SIAM
Symposium on Discrete Algorithms, SIAM, Philadelphia, 2004, pp. 1014–1023.
[26] Y.-L. Lin and S. S. Skiena, Algorithms for square roots of graphs, SIAM J. Discrete Math., 8(1995), pp. 99–118.
[27] S. T. McCormick, Optimal approximation of sparse Hessians and its equivalence to a graphcoloring problem, Math. Program., 26 (1983), pp. 153–171.
[28] M. J. D. Powell and P. L. Toint, On the estimation of sparse Hessian matrices, SIAM J.
Numer. Anal., 16 (1979), pp. 1060–1074.
[29] L. Stockmeyer and V. Vazirani, NP-completeness of some generalizations of the maximum
matching problem, Inform. Process. Lett., 15 (1982), pp. 14–19.
[30] M. M. Strout and P. D. Hovland, Metrics and models for reordering transformations, inProceedings of the 2004 Workshop on Memory System Performance, ACM, New York,
2004, pp. 23–34.