Bipartite radius-four Disconnected Perfect Matching → Bipartite radius-three Disconnected Perfect Matching Complexity open
Solution submitted Research history & proof on GitHub ↗
Why this question matters
This addresses a small-radius boundary for a matching that also acts as an edge separator.
The published radius classification distinguishes radius-two tractability from radius-four hardness and leaves radius three as a separate question.
The reduction to construct
The source is a connected bipartite graph of radius at most four. Its outputs are perfect matchings whose deletion disconnects the graph, or NO-SOLUTION.
Both problems ask for a perfect matching whose deletion disconnects a connected bipartite graph, or NO-SOLUTION. The source radius is at most four and the target radius 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.
A cut alone is insufficient: every decoded structure must extend to the required perfect matching.
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.