3P3-free Minimum Matching Cut → P9-free Minimum Matching Cut Complexity open
Unsolved
Why this question matters
The question refines the structural boundary for finding small matching separators.
This question concerns a bound on the size of a matching cut, rather than existence alone. Results for other cut predicates do not resolve it.
The reduction to construct
The source gives a connected graph with no induced disjoint union of three three-vertex paths, and a bound k. Its outputs are nonempty matching cuts of size at most k, or NO-SOLUTION.
Given a connected graph and integer k, ask for a nonempty matching cut of at most k edges, or NO-SOLUTION. The source excludes three disjoint induced three-vertex paths and the target excludes an induced nine-vertex path. This is a threshold problem, not an exact-optimum output contract.
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 gadget must control cut size as well as matching-cut feasibility and induced paths.
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-14. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.