Diameter-four Perfect Matching Cut → Diameter-three Perfect Matching Cut Complexity open
Unsolved
Why this question matters
The question seeks the missing diameter boundary for Perfect Matching Cut.
The cited diameter classification leaves the diameter-three case distinct from the known diameter-four hardness result.
The reduction to construct
The source is a connected graph of diameter at most four. Its outputs are nontrivial cuts having exactly one opposite neighbor at every vertex, or NO-SOLUTION.
Both problems ask for a nontrivial bipartition with exactly one opposite neighbor per vertex, or NO-SOLUTION. The connected source graph has diameter at most four; the connected target graph has diameter at most three.
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.
Distance shortcuts can introduce new perfect matching cuts or destroy old ones.
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
- Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius ↗
- arXiv record ↗
- Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter ↗
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.