3-SAT → Minimum-cost time-feasible reconciliation with host switches of distance at most three Complexity open
Unsolved
Why this question matters
Moderate: hardness at distance three would locate the first possible boundary for biologically constrained reconciliation and help explain when exact host-switch reconstruction requires exponential search. It would not classify all fixed distances.
The 2026 paper states that cost-optimal time-feasible reconciliation with fixed host-switch distance is polynomial for distance two and open for every fixed distance at least three. Its short-cycle theorem concerns strong acyclicity and does not solve cost optimization under ordinary acyclicity.
The reduction to construct
An explicitly encoded Boolean 3-CNF formula is given. The valid output is YES if it has a satisfying assignment and NO otherwise.
The input contains two explicitly encoded rooted full binary host and parasite trees, a map from parasite leaves to host leaves, nonnegative binary-encoded event costs, and a binary-encoded cost bound K. The answer is YES exactly when a reconciliation mapping parasite vertices to host vertices respects the given leaves and the cospeciation, duplication and switch event rules of Antony, Martino and Sinaimeri, every host switch spans at most three host-tree edges, the temporal constraint digraph is acyclic, and total event cost is at most K; otherwise NO.
Give deterministic polynomial-time F and G from 3-SAT to this exact distance-three, time-feasible decision problem, preserving both YES and NO. A positive result would establish NP-hardness at the first distance not covered by the distance-two polynomial algorithm.
High: unrestricted switching hardness does not keep switches within three host edges or ensure time feasibility. The 2026 finite short-cycle certificate offers a way to audit constructed reconciliations, but forbidding those cycles while transmitting Boolean choices is the missing step.
What a complete answer must include
Specify tree, leaf map, cost vector and threshold gadgets, prove legal-event and acyclicity conditions in both directions, and bound all binary encodings and runtime. Later independent checks should validate event costs and the temporal graph on small positive and negative cases.
References
Literature checked 2026-09-26. Checked arXiv full text, Introduction, Definitions 1-5, Theorem 1 and Section 6; searched 2026-09-26 for 'distance-bounded reconciliation d=3 NP-hard', 'time-feasible reconciliation distance 3 algorithm' and later versions. No later matching classification was found. The paper's Definition 3 omits an explicit time-feasibility constraint; this card fixes the time-feasible variant singled out in its Introduction and uses Definition 5 for acyclicity. Gates 1-4 pass for that fixed variant; Gate 5 holds on a distance-three gadget; Gate 6 was not assessed.