BFS tree support → Horn satisfiability Complexity open
Unsolved
Why this question matters
A polynomial reduction would give both recognition and tree construction for the remaining traversal-support case.
Published traversal-support classifications leave the BFS case open; the polynomial algorithms for DFS and general search do not imply FIFO consistency.
The reduction to construct
The source gives an explicit nonempty list of permutations of the same n vertices, n≥1. Its output is a tree realizing all orders as FIFO breadth-first traversals, with arbitrary neighbor tie orders, or NO-SOLUTION.
An explicitly listed nonempty profile of permutations must be realized by FIFO breadth-first search on one tree, with arbitrary neighbor tie orders. The target is an explicit Horn formula; its outputs are satisfying assignments or NO-SOLUTION.
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 exact parent compatibility representation is available, but neither propagation completeness nor extraction is proved. Greedy and contraction routes have counterexamples.
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.