Faster deterministic algorithms for r-dimensional matching using representative sets

family $F \subseteq U_1 \times \cdots \times U_r$, the
\textsc{$r$-dimensional matching} problem asks if $F$ admits a collection
of $k$ mutually disjoint sets. The special case when $r=3$ is the classic
{\sc $3$D Matching} problem. Recently, several improvements have been
suggested for these (and closely related) problems in the setting of
randomized parameterized algorithms. Also, many approaches have evolved
for deterministic parameterized algorithms. For instance, for the {\sc
$3$D Matching} problem, a combination of color coding and iterative
expansion yields a running time of $O^*(2.80^{(3k)})$, and for the
\textsc{$r$-dimensional matching} problem, a recently developed
derandomization for known algebraic techniques leads to a running time of
$O^*(5.44^{(r-1)k})$.

In this work, we employ techniques based on dynamic programming and
representative families, leading to a deterministic algorithm with running
time $O^*(2.85^{(r-1)k})$ for the {\sc $r$-Dimensional Matching} problem.
Further, we incorporate the principles of iterative expansion used in the
literature [TALG 2012] to obtain a better algorithm for {\sc
$3$D-matching}, with a running time of $O^*(2.003^{(3k)})$. Apart from the
significantly improved running times, we believe that these algorithms
demonstrate an interesting application of representative families in
conjunction with more traditional techniques.