Directed two-linkage → Cycle factor containing an even cycle Complexity open
Unsolved
Why this question matters
This addresses the complexity difference between parity conditions imposed on some cycles and on all cycles of a factor.
Requiring at least one even cycle is different from requiring every cycle to have a specified parity; those classifications cannot be substituted for this predicate.
The reduction to construct
The source gives a digraph and two designated terminal pairs. Its outputs are two vertex-disjoint directed paths joining the respective pairs, or NO-SOLUTION.
The source asks for two vertex-disjoint directed paths between prescribed terminal pairs. The target is a loopless digraph and asks for a spanning directed cycle factor containing at least one even cycle; directed two-cycles are allowed.
Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.
A parity modification must prevent unintended even cycles without destroying the linkage correspondence.
What a complete answer must include
Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.
References
Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.