New Acyclic and Star Coloring Algorithms
with Applications to Hessian Computation

Abstract.

Acyclic and star coloring problems are specialized vertex coloring problems that arise in the efficient computation of Hessians using automatic differentiation or finite differencing, when  both sparsity and symmetry are exploited. We present an algorithmic paradigm for finding 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 time complexity of our star coloring algorithm is $O(n\overline{d}_2)$ where $\overline{d}_k$, a generalization of vertex degree, denotes the average number of distinct paths of length at most $k$ edges starting at a vertex in $G$; and the time complexity of our acyclic coloring algorithm is $O(n\overline{d}_2 \cdot \alpha(m,m'))$ where $\alpha$ is the inverse of Ackermann's function and $m' = n\overline{d}_2$. (The factor $\alpha(m,m')$ in the latter expression is nearly a constant.) The space complexity of both algorithms is $O(m)$. To the best of our knowledge, our acyclic coloring algorithm  is the first practical algorithm for the problem. For the star coloring problem, our algorithm improves on the time complexity of and the number of colors used by a previously known $O(n\overline{d}_3)$-time heuristic algorithm. Computational results from experiments on various large-size test graphs demonstrate that the algorithms are fast and produce highly effective solutions. The use of these algorithms in Hessian computation is expected to reduce overall runtime significantly.

Key words.  acyclic coloring, star coloring, computation of Hessians, automatic differentiation, finite differences