  Mining groups of genes that consistently co-express is an important problem
in biomedical research, where it is critical for applications such as
drug-repositioning and designing new disease treatments. Recently, Cooley et
al. modeled this problem as Exact Weighted Clique Decomposition (EWCD) in
which, given an edge-weighted graph $G$ and a positive integer $k$, the goal is
to decompose $G$ into at most $k$ (overlapping) weighted cliques so that an
edge's weight is exactly equal to the sum of weights for cliques it
participates in. They show EWCD is fixed-parameter-tractable, giving a
$4^k$-kernel alongside a backtracking algorithm (together called cricca) to
iteratively build a decomposition. Unfortunately, because of inherent
exponential growth in the space of potential solutions, cricca is typically
able to decompose graphs only when $k \leq 11$.
  In this work, we establish reduction rules that exponentially decrease the
size of the kernel (from $4^k$ to $k2^k$) for EWCD. In addition, we use
insights about the structure of potential solutions to give new search rules
that speed up the decomposition algorithm. At the core of our techniques is a
result from combinatorial design theory called Fisher's inequality
characterizing set systems with restricted intersections. We deploy our
kernelization and decomposition algorithms (together called DeCAF) on a corpus
of biologically-inspired data and obtain over two orders of magnitude speed-up
over cricca. As a result, DeCAF scales to instances with $k \geq 17$.
