标题： 奇数和偶数更难的环因子问题 显示英文标题

标题： Odd and Even Harder Problems on Cycle-Factors

摘要： 对于一个图（无向图、有向图或混合图），一个环因子是覆盖整个顶点集的顶点不相交环的集合。 受奇偶性约束的环因子自然出现在结构图论和算法复杂性的研究中。 在本工作中，我们研究了在奇偶性约束下寻找环因子问题的四种变体：(1) 所有环都是奇数长度，(2) 所有环都是偶数长度，(3) 至少有一个环是奇数长度，和 (4) 至少有一个环是偶数长度。 这些变体在无向图、有向图和混合图的情况下被考虑。 我们证明了除了第四个问题外，其他所有问题在所有情况下都是NP难的，而第四个问题在有向图和无向图情况下的复杂性仍然是开放的。 我们还证明，在混合图中，甚至判断是否存在任何环因子也是NP难的。 显示英文摘要

摘要： For a graph (undirected, directed, or mixed), a cycle-factor is a collection of vertex-disjoint cycles covering the entire vertex set. Cycle-factors subject to parity constraints arise naturally in the study of structural graph theory and algorithmic complexity. In this work, we study four variants of the problem of finding a cycle-factor subject to parity constraints: (1) all cycles are odd, (2) all cycles are even, (3) at least one cycle is odd, and (4) at least one cycle is even. These variants are considered in the undirected, directed, and mixed settings. We show that all but the fourth problem are NP-complete in all settings, while the complexity of the fourth one remains open for the directed and undirected cases. We also show that in mixed graphs, even deciding the existence of any cycle factor is NP-complete.