Positive NAE-3-SAT → Bipartite diameter-five Perfect Matching Cut Complexity open
Unsolved
Why this question matters
The diameter restriction targets a missing boundary in the structural complexity of perfect matching cuts.
The cited classification leaves the bipartite diameter-five case between established tractable and hard cases.
The reduction to construct
A source instance is a conjunction of clauses of three distinct unnegated variables. A valid assignment gives both truth values to every clause; an infeasible instance returns NO-SOLUTION.
The target is a connected bipartite graph of diameter at most five. A witness is a nontrivial vertex bipartition in which every vertex has exactly one neighbor across the cut; otherwise the output is NO-SOLUTION.
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.
Shortening distances must preserve the exact one-crossing-neighbor constraint at every vertex.
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-15. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.