Planar 3-SAT → Two-subcoloring of height-one unit disk graphs Complexity open
Unsolved
Why this question matters
Moderate: hardness would close the geometric boundary left after bounded-height hardness and affect exact two-channel grouping in narrow wireless deployments. A polynomial algorithm would instead imply the paper's proposed 2-approximation route, but is not the requested positive reduction.
Marin and Watrigant prove 2-Subcoloring hard for triangle-free unit disk graphs and for some constant strip height, then explicitly leave height at most one open. Their result does not specify hardness at this narrower height.
The reduction to construct
An explicit planar Boolean 3-CNF formula with a planar variable-clause incidence embedding is given. Output YES if satisfiable and NO otherwise.
The input is the adjacency list of a simple graph promised to have a representation by diameter-one closed disks whose centers lie in a horizontal strip of height at most one. Output YES exactly when its vertices can be partitioned into two classes, each inducing a disjoint union of cliques, equivalently containing no induced three-vertex path; otherwise NO. The reduction must produce a rational-coordinate representation to establish the promise, although the target input is the graph.
Construct deterministic polynomial-time F and G from Planar 3-SAT to this exact height-one 2-Subcoloring problem, with equivalent YES/NO outputs and polynomial coordinate bit lengths. A positive result would prove NP-hardness of the open strip-height case.
High: the published bounded-height construction exceeds the height-one threshold, and the familiar proper-coloring algorithm for bounded-height unit disk graphs does not apply to subcoloring. A plausible route compacts its variable and clause disk corridors to height one while retaining required adjacencies; the exact separation inequalities are the missing step.
What a complete answer must include
Specify disk centers, derive the adjacency graph exactly, prove every center lies in a width-one strip and prove equivalence of subcolorings and satisfying assignments. Give polynomial bit and runtime bounds, and later compare small cases with an independent graph oracle.
References
Literature checked 2026-09-26. Checked the MFCS 2025 primary paper, geometric Definitions in Section 2 and Theorem 7 with the following open statement; searched 2026-09-26 for '2-Subcoloring unit disk height 1', 'strip height one subcoloring NP-hard' and later versions. No later matching theorem surfaced. Gates 1-4 pass; Gate 5 holds on height-one coordinate gadgets; Gate 6 was not assessed.