论文标题
加权边缘分区问题的固定参数障碍性问题
Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem
论文作者
论文摘要
我们为加权边缘分区（WECP）问题开发了FPT算法和Bi-Kernel，其中具有$ n $顶点和整数边缘权重的图与整数$ k $一起提供，目的是找到$ K $ cliques，以便每个边缘在其权重等等中都出现在许多clique中。该问题以前仅在未加权版本中研究了Edge Clique Partition（ECP），其中边缘需要将其分配为$ k $ cliques。结果表明，ECP在〜$ k^2 $顶点[Mujuni和Rosamond，2008年]中接受了一个内核，但是该核并未扩展到WECP。以前最快的算法以ECP闻名的算法的运行时为$ 2^{\ Mathcal {o}（k^2）} n^{o（1）} $ [ISSAC，2019年]。对于WECP，我们开发了一个带有$ 4^k $顶点的双核，以及带有运行时$ 2^{\ Mathcal {o}（k^{3/2} w^{1/2} \ log（k/w）} \ log（k/w））} n^{o（k^{1/2}）} n^{o（1）} $的算法。尤其是后者将ECP的运行时间提高到〜$ 2^{\ Mathcal {o}（k^{3/2} \ log k）} n^{o（1）} $。
We develop an FPT algorithm and a bi-kernel for the Weighted Edge Clique Partition (WECP) problem, where a graph with $n$ vertices and integer edge weights is given together with an integer $k$, and the aim is to find $k$ cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into $k$ cliques. It was shown that ECP admits a kernel with~$k^2$ vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of $2^{\mathcal{O}(k^2)}n^{O(1)}$ [Issac, 2019]. For WECP we develop a bi-kernel with $4^k$ vertices, and an algorithm with runtime $2^{\mathcal{O}(k^{3/2}w^{1/2}\log(k/w))}n^{O(1)}$, where $w$ is the maximum edge weight. The latter in particular improves the runtime for ECP to~$2^{\mathcal{O}(k^{3/2}\log k)}n^{O(1)}$.
