Positive 1-in-3-SAT → P13-free Perfect Matching Cut Complexity open

Unsolved

Clone https://github.com/reduction-zoo/p13-free-perfect-matching-cut to investigate Positive 1-in-3-SAT → P13-free Perfect Matching Cut. Read the fixed question and state. Use preparation notes, the test corpus, and verifier if present; otherwise complete Prepare before a reduction attempt. Follow the repository instructions and your AutoResearch pipeline.

Submit a solution

Why this question matters

The question addresses a forbidden-path boundary for perfect matching cuts.

The cited structural classification leaves the P13-free perfect matching cut question separate from hardness on larger induced-path classes.

The reduction to construct

The source is Positive 1-in-3-SAT with explicit clauses of three unnegated variables. Its valid output is the correct YES/NO answer.

The target is a graph with no induced path on thirteen vertices and asks for a nontrivial cut having exactly one opposite neighbor at every vertex. The archived fixed theorem requests decision outputs; it does not establish witness extraction. Its valid output for this fixed theorem is the correct YES/NO answer.

Construct a polynomial-time instance map preserving the correct decision answer. Recovery maps the target YES/NO answer to the source answer. The archived theorem is decision-only; no witness recovery theorem is claimed. The requested complexity conclusion is NP-hardness for the stated target problem.

Variable and clause gadgets must compose without creating long induced paths. A decision reduction should not be presented as an established search reduction.

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.