Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring

Abstract

This paper presents a new polynomial-time algorithm, approximate star bicoloring (ASBC), for star bicoloring and acyclic bicoloring. These NP-complete combinatorial problems arise from problems associated with computing large sparse Jacobian matrices. The main results of this paper lie in approximation analysis related to these problems. In particular, it is shown that (i) both star and acyclic bicoloring can be approximated in polynomial time to the ratio O(n ^2/3) and (ii) both star and acyclic bicoloring cannot be approximated to the ratio O(n ^1/3−ε) in polynomial time under reasonable complexity theoretic hypotheses. The ASBC algorithm is also analysed experimentally on a collection of realistic test cases from the Harwell–Boeing sparse matrix collection. The experimental results indicate that ASBC performs quite well in practice; the performance of the new algorithm always fell within the range of 1.53 and 6 times optimal on the given test sets.

Keywords:

• star bicoloring
• acyclic bicoloring
• automatic differentiation
• approximation algorithms

AMS Subject Classification :

• 68W25
• 68Q17

Acknowledgements

This paper is dedicated to Andreas Griewank. The first author expresses his deep gratitude to Andreas Griewank for introducing AD and combinatorial scientific computing 17 to him nearly 20 years ago. The first author also wishes to express his gratitude to Liming Cai for many discussions on a much earlier version of this paper 4. Liming Cai declined to be a co-author of this paper.

Notes

The precise definitions of these graph colouring problems are provided in Section 2.

In their paper, Coleman and Verma referred to these problems as bipartite path colouring and bipartite cyclic colouring.

Obtained from http://math.nist.gov/MatrixMarket/.

The matrix cannes 268 was omitted because the results given in 7 reported a number of non-zeros that did not match the values from Matrix Market.

In most cases, this number exactly matches the number given in the Matrix Market. However, in a few cases, some of the values in the matrices (given in sparse matrix format) are zero. For those few matrices (arc130, fs 541 1, fs 541 2), the number of non-zeros reported here are larger than the number of non-zeros reported by Matrix Market.

The numbers reported are somewhat different than the numbers reported in 18. Notice that the number of non-zeros reported in the table in that paper does not match the values given by the Matrix Market.