  The edge clique cover (ECC) problem -- where the goal is to find a minimum
cardinality set of cliques that cover all the edges of a graph -- is a classic
NP-hard problem that has received much attention from both the theoretical and
experimental algorithms communities. While small sparse graphs can be solved
exactly via the branch-and-reduce algorithm of Gramm et al. [JEA 2009], larger
instances can currently only be solved inexactly using heuristics with unknown
overall solution quality. We revisit computing minimum ECCs exactly in practice
by combining data reduction for both the ECC \emph{and} vertex clique cover
(VCC) problems. We do so by modifying the polynomial-time reduction of Kou et
al. [Commun. ACM 1978] to transform a reduced ECC instance to a VCC instance;
alternatively, we show it is possible to ``lift'' some VCC reductions to the
ECC problem. Our experiments show that combining data reduction for both
problems (which we call \emph{synergistic data reduction}) enables finding
exact minimum ECCs orders of magnitude faster than the technique of Gramm et
al., and allows solving large sparse graphs on up to millions of vertices and
edges that have never before been solved. With these new exact solutions, we
evaluate the quality of recent heuristic algorithms on large instances for the
first time. The most recent of these, \textsf{EO-ECC} by Abdullah et al. [ICCS
2022], solves 8 of the 27 instances for which we have exact solutions. It is
our hope that our strategy rallies researchers to seek improved algorithms for
the ECC problem.
