Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets
Prachi Goyal, Neeldhara Misra, Fahad Panolan, Meirav Zehavi · SIAM Journal on Discrete Mathematics · 2015
In this work, we study the well-known $r$-Dimensional $k$-Matching ($(r,k)$-DM), and $r$-Set $k$-Packing ($(r,k)$-SP) problems. Given a universe $U := U_1 \uplus \cdots \uplus U_r$ and an $r$-uniform family $\mathcal{F} \subseteq U_1 \times \cdots \times U_r$, the $(r,k)$-DM problem asks if $\mathcal{F}$ admits a collection of $k$ mutually disjoint sets. Given a universe $U$ and an $r$-uniform family $\mathcal{F}\subseteq 2^U$, the $(r,k)$-SP problem asks if $\mathcal{F}$ admits a collection of $k$ mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time $\mathcal{O} (2.851^{(r-1)k}\cdot|\mathcal{F}|\cdot n\log^2 n\cdot \log W)$ for the weighted version of $(r,k)$-DM, where $W$ is the maximum weight in the input, and a deterministic algorithm with running time $\mathcal{O}(2.851^{(r-0.5501)k}\cdot|\mathcal{F}|\cdot n\log^2 n\cdot \log W)$ for the weighted version of $(r,k)$-SP. Thus, we significantly improve the previous best known deterministic running times for $(r,k)$-DM and $(r,k)$-SP and the previous best known running times for their weighted versions. We rely on structural properties of $(r,k)$-DM and $(r,k)$-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for $(3,k)$-DM, running in time $\mathcal{O}(2.004^{3k}\cdot|\mathcal{F}| \cdot n\log^2 n)$. We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size $\mathcal{O}(e^rr(k-1)^r\log W)$ for the weighted versions of $(r,k)$-DM and $(r,k)$-SP, improving the previous best known kernels of size $\mathcal{O}(r!r(k-1)^r\log W)$ for these problems.