Parameterized Algorithms for Covering by Arithmetic Progressions
CoRR(2023)
摘要
An arithmetic progression is a sequence of integers in which the difference
between any two consecutive elements is the same. We investigate the
parameterized complexity of two problems related to arithmetic progressions,
called Cover by Arithmetic Progressions (CAP) and Exact Cover by Arithmetic
Progressions (XCAP). In both problems, we are given a set $X$ consisting of $n$
integers along with an integer $k$, and our goal is to find $k$ arithmetic
progressions whose union is $X$. In XCAP we additionally require the arithmetic
progressions to be disjoint. Both problems were shown to be NP-complete by
Heath [IPL'90].
We present a $2^{O(k^2)} poly(n)$ time algorithm for CAP and a $2^{O(k^3)}
poly(n)$ time algorithm for XCAP. We also give a fixed parameter tractable
algorithm for CAP parameterized below some guaranteed solution size. We
complement these findings by proving that CAP is Strongly NP-complete in the
field $\mathbb{Z}_p$, if $p$ is a prime number part of the input.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要