3-SAT → Mixed-layout recognition of 2-trees Complexity open
Unsolved
Why this question matters
The question asks whether choosing a mixed layout is hard even on a narrowly structured graph class.
The cited work retains recognition of one-stack, one-queue layouts on 2-trees. Counterexamples to universal existence do not establish recognition hardness.
The reduction to construct
A source instance is an explicitly encoded Boolean formula with at most three literals per clause. Its outputs are satisfying Boolean assignments, or NO-SOLUTION when the formula is unsatisfiable.
The target must be a 2-tree and asks for a vertex order with one stack and one queue. Independent stack edges may not alternate and independent queue edges may not nest. A 2-tree starts from an edge and repeatedly adds a vertex adjacent to both endpoints of an existing edge.
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.
Fixed-order page assignment is tractable. The unresolved work is forcing orders while maintaining the 2-tree structure.
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.