在$d$-Clique Packing问题中，给定一个图$G$和一个整数$t$，我们需要判断$G$中是否存在$t$个大小为$d$的成对顶点不相交的Clique集合。这一问题是Triangle Packing的推广，并且对于所有$d \geq 3$都是NP完全的。我们展示了如何在$n^{O(k^{d-1})}$时间内解决该问题，其中$k$是图的Clique宽度（输入中给出$G$的$k$-表达式）。
我们进一步证明，假设指数时间假设（ETH）成立，则不存在任何算法可以在$n^{o(k^{d-1})}$时间内解决该问题，对于任何固定的$d \geq 3$，即使是在寻找大小为$d$的Clique分区的特殊情况下。我们的证明还涉及到$d$-Clique Packing（和$d$-Clique Partition）在Clique宽度参数化下的W[1]-困难性，这对于每个$d \geq 3$都是成立的。
我们的工作延续了Fomin等人（SICOMP 2010+2014）开始的一系列关于ETH紧界限的基本图问题的研究，他们获得了Max-Cut和Edge Dominating Set的紧界限。
博主点评： 本文在Clique打包问题的复杂性分析上取得了重要进展，特别是在Clique宽度的参数化方面。通过引入ETH假设，作者不仅给出了算法的时间复杂度界限，还揭示了问题的固有困难性，为相关领域的研究提供了有力的理论支持。