2-Orientability → Two-Contention-Point Serializable Transaction Scheduling Complexity open
Unsolved
Why this question matters
Moderate: this would move the known database scheduling hardness boundary from unrestricted contention to two objects, completing one side of the gap next to the one-contention-point polynomial algorithm.
Baccaert et al. (ICDT 2026, Section 5 and Open Problems) solve one contention point and explicitly identify the gap to their many-point hardness. Their Section 6.2 gives only a worst-case makespan bound for two contention points, not an instance-optimal algorithm. The exact two-point complexity is an inferred slice of that stated gap.
The reduction to construct
Input is an explicitly listed undirected graph G. Output YES exactly if some total order of V(G) orients each edge forward so that every directed path in the resulting orientation has at most two edges; otherwise NO. This is the 2-Orientability problem in ICDT 2026, Proposition 11, equivalent to 3-colorability via Gallai–Roy–Vitaver. It is not the unrelated indegree-bounded orientation problem.
Input is a finite collection of read/write operation sequences on named objects and binary span bound K. Each operation has unit duration; per-transaction order is strict; conflicting operations on the same object cannot be simultaneous; the conflict-precedence graph must be acyclic. At most two objects are contention points. A schedule may be shifted so its first operation occurs at time zero, and its span is last occupied time plus one. Output YES if such a schedule has span at most K, otherwise NO.
Give polynomial-time F from this precise NP-hard 2-Orientability problem to two-contention-point schedulability and truth-preserving G. A positive rule proves NP-hardness for this exact two-point target.
High: the published hardness uses many contention points, while serialization adds global precedence cycles absent from ordinary job-shop schedules. A two-object gadget must preserve both time and acyclicity.
What a complete answer must include
Provide deterministic polynomial-time F and G with bit-size bounds. Prove correctness for every legal input and every valid target output, including NO-SOLUTION where defined; independently check recovered answers on representative instances. A generic SAT or ILP encoding alone does not meet the novelty goal.
References
Literature checked 2026-09-26. Web searches 2026-09-26: "two contention points schedulability", "Bounding the Makespan of Transaction Schedules open problems", and board aliases. Read ICDT 2026 Definitions, Propositions 11–12, Lemma 13, Sections 5, 6.2 and 8. Proposition 12 uses three shared objects per input edge; Section 6.2 only bounds worst-case span. Gate 5 route: represent oriented-edge interactions through two global contention objects with private operations carrying spacing; the missing lemma must prevent cross-edge interference from creating false long paths. Untested; Gate 6 not assessed.