Deciding whether a graph can be edge-decomposed into a matching and a $k$-bounded linear forest was recently shown by Campbell, H{\"o}rsch and Moore to be NP-complete for every $k \ge 9$, and solvable in polynomial time for $k=1,2$. In the first part of this paper, we close this gap by showing that this problem is in NP-complete for every $k \ge 3$. In the second part of the paper, we show that deciding whether a graph can be edge-decomposed into a matching and a $k$-bounded star forest is polynomially solvable for any $k \in \mathbb{N} \cup \{ \infty \}$, answering another question by Campbell, H{\"o}rsch and Moore from the same paper.
翻译：将图分解成匹配和有边界线性森林的复杂性
翻译后的摘要：
决定一个图是否能够被边分解成一个匹配和一个$k$-有边界线性森林，最近被Campbell、H{\"o}rsch和Moore证明，当$k \ge 9$时是NP完全问题，当$k=1,2$时可以在多项式时间内解决。在本文的第一部分中，我们通过展示在所有$k \ge 3$时都是NP完全问题来弥合这一差距。在本文的第二部分中，我们展示决定一个图是否能够被边分解成一个匹配和一个$k$-有边界星森林对于任何$k \in \mathbb{N} \cup \{ \infty \}$是多项式可解的，回答来自同一篇论文中的另一个问题。
相关内容
微信扫码咨询专知VIP会员