3P2-free 2-Cut → P6-free 2-Cut Complexity open

Unsolved

Clone https://github.com/reduction-zoo/p6-free-two-cut to investigate 3P2-free 2-Cut → P6-free 2-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

Together with P5-free tractability, hardness here would identify an exact forbidden-path boundary.

The cited work gives P5-free tractability and asks about the next forbidden-path case. Probe-graph results concern a larger class and do not settle ordinary P6-free graphs.

The reduction to construct

The source is a connected graph containing no induced disjoint union of three edges. Its outputs are nontrivial cuts with crossing degree at most two, or NO-SOLUTION.

Both endpoints are connected simple graphs and seek a nontrivial bipartition with at most two opposite neighbors per vertex. The source excludes three disjoint induced edges; the target excludes an induced six-vertex path.

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.

Adding vertices cannot remove an existing induced P6; densification consumes crossing budgets and can destroy valid cuts.

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.