Height-one poset interval dimension at most three → Non-crossing theta-host recognition Complexity open
Unsolved
Why this question matters
This tests recognition on a small host where branching and non-crossing constraints interact.
The question fixes a particular small host and the non-crossing condition. General intersection-graph recognition does not establish this restriction.
The reduction to construct
The source is an explicitly encoded height-one poset. Its outputs are at most three interval orders whose intersection is that poset, or NO-SOLUTION.
The fixed host has one a–b edge, three parallel b–c edges, and one c–d edge. Represent the target graph by connected subgraphs of a subdivision of this host, with intersection exactly adjacency and each pairwise set difference connected or empty.
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.
Interval-dimension encodings must survive subdivision freedom and alternative host representations.
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.