Odd and Even Harder Problems on Cycle-Factors
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918164741226496 |
|---|---|
| author | Hörsch, Florian Király, Csaba Mendoza-Cadena, Mirabel Pap, Gyula Szabó, Eszter Yamaguchi, Yutaro |
| author_facet | Hörsch, Florian Király, Csaba Mendoza-Cadena, Mirabel Pap, Gyula Szabó, Eszter Yamaguchi, Yutaro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18393 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Odd and Even Harder Problems on Cycle-Factors Hörsch, Florian Király, Csaba Mendoza-Cadena, Mirabel Pap, Gyula Szabó, Eszter Yamaguchi, Yutaro Data Structures and Algorithms Combinatorics 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. |
| title | Odd and Even Harder Problems on Cycle-Factors |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2510.18393 |