1-queue recognition → 2-queue recognition Complexity open
Solution submitted Research history & proof on GitHub ↗
Why this question matters
This asks whether recognizing the next queue level inherits the difficulty of one-queue recognition.
A reduction between adjacent queue levels must work with unrestricted vertex orders; an embedding with a supplied order would be a different theorem.
The reduction to construct
The source gives a simple graph. Its outputs are vertex orders with no nested pair of independent edges, or NO-SOLUTION.
A queue layout consists of a vertex order and a partition of edges into queues, with no two independent edges nested within a queue. The source permits one queue and the target permits two; outputs include the order and queue assignment.
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 two-queue layout of the constructed graph must expose a recoverable one-queue layout of the source.
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-15. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.