  The task of min-plus matrix multiplication often arises in the context of
distances in graphs and is known to be fine-grained equivalent to the All-Pairs
Shortest Path problem. The non-crossing property of shortest paths in planar
graphs gives rise to Monge matrices; the min-plus product of $n\times n$ Monge
matrices can be computed in $O(n^2)$ time. Grid graphs arising in sequence
alignment problems, such as longest common subsequence or longest increasing
subsequence, are even more structured. Tiskin [SODA'10] modeled their behavior
using simple unit-Monge matrices and showed that the min-plus product of such
matrices can be computed in $O(n\log n)$ time. Russo [SPIRE'11] showed that the
min-plus product of arbitrary Monge matrices can be computed in time
$O((n+\delta)\log^3 n)$ parameterized by the core size $\delta$, which is
$O(n)$ for unit-Monge matrices.
  In this work, we provide a linear bound on the core size of the product
matrix in terms of the core sizes of the input matrices and show how to solve
the core-sparse Monge matrix multiplication problem in $O((n+\delta)\log n)$
time, matching the result of Tiskin for simple unit-Monge matrices. Our
algorithm also allows $O(\log \delta)$-time witness recovery for any given
entry of the output matrix. As an application of this functionality, we show
that an array of size $n$ can be preprocessed in $O(n\log^3 n)$ time so that
the longest increasing subsequence of any sub-array can be reconstructed in
$O(l)$ time, where $l$ is the length of the reported subsequence; in
comparison, Karthik C. S. and Rahul [arXiv'24] recently achieved
$O(l+n^{1/2}\log^3 n)$-time reporting after $O(n^{3/2}\log^3 n)$-time
preprocessing. Our faster core-sparse Monge matrix multiplication also enabled
reducing two logarithmic factors in the running times of the recent algorithms
for edit distance with integer weights [Gorbachev & Kociumaka, arXiv'24].
