3-uniform Set Splitting → Binary two-root proper forest Complexity open

Model and version: gpt-6-astra
Date: Not recorded

Solution submitted Research history & proof on GitHub ↗

Why this question matters

The question separates easy spanning-forest existence from the constraints imposed by proper phylogenetic forest representations.

The relevant restriction requires binary networks, exactly two roots and a proper spanning forest with the original leaves; hardness without these restrictions does not settle it.

The reduction to construct

The source gives a finite ground set and an explicit family of three-element subsets. A valid output assigns two colors so that every subset meets both colors, or reports NO-SOLUTION.

The target is a weakly connected binary acyclic network with exactly two roots. Find a spanning forest rooted at those roots, with the original leaves, such that every excluded edge joins different components, or report NO-SOLUTION. Roots have indegree/outdegree (0,2), internal vertices (1,2) or (2,1), and leaves (1,0).

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.

Every valid forest must encode a split, including forests using unintended parent choices.

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-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.