{"id":"4f8493cf-1c3a-4bee-8efe-16639d9f16a6","arxiv_id":"1908.02019","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Fixed-time and fixed-destination optimal control of Boolean control networks reduce to shortest path problems in time-expanded state transition graphs, solvable by dynamic programming or Dijkstra's algorithm.","lead":"This paper converts finite-horizon optimal control of Boolean control networks into shortest path problems on specially built graphs, with algorithms that handle time-varying costs and constraints. It offers a unified and faster way to plan optimal interventions in Boolean models of gene regulatory networks.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 2's time-monotonicity is load-bearing: without it, the TED-STG horizon bound fails and Problem 2 with time-variant costs is less general than the abstract suggests.","rationale":"The reader correctly identifies Assumption 2 as the weakest load-bearing point. The graph-theoretic reductions in Theorems 1, 3, and 4 are coherent and the complexity analyses are sound under the stated hypotheses. The main mathematical claim is conditional on Assumption 2 for Problem 2: the time-expanded TED-STG is truncated at Z layers precisely because Proposition 2 guarantees an optimal path of length xd with cost max(10-t,0), terminal cost 0, Ω={xd}, so Z=|R(x0)|=2. If the algorithm outputs 10 while a horizon-11 policy attains cost 0, the assumption-free version of the Problem 2 claim is falsified, confirming that the horizon bound K<|R(x0)| depends on Assumption 2(iii).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section VI.A imposes Assumption 2: h bounded below, g nonnegative, and both nondecreasing in t. This is not a minor technicality. Proposition 2's cycle-elimination proof (Eq. 21) relies on monotonicity to compare costs after removing a cycle and shifting remaining transitions to earlier times; without it, removing a cycle can increase cost, so an optimal control sequence may require arbitrarily many steps. Hence the bound K < |R(x0)| that defines the number of layers in the TED-STG (Definition 7) and underpins Theorem 4 is invalid outside Assumption 2. A two-state example makes this concrete: let R(x0)={x0,xd}, place a zero-cost self-loop on x0, and set the edge x0->xd to cost max(10-t,0) at time t, with terminal cost 0 and Ω={xd}. All optimal sequences have K>=11 and cost 0, but Algorithm S1 explores only paths of length <2 and returns cost 10. Thus the central claim that Problem 2 can be solved with time-variant costs is only true under monotone costs; this is a genuine scope restriction, although the paper does state the assumption explicitly.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a unified graph-theoretic framework for finite-horizon optimal control (FHOC) of Boolean control networks. Two general problems are formulated: Problem 1 with a fixed horizon T and Problem 2 with an unspecified finite horizon to a destination set, both allowing time-variant costs and state/control constraints. The authors construct weighted state transition graphs and time-expanded variants (TET-STG, STG+, TED-STG), prove in Theorems 1-4 that the two FHOC problems are equivalent to shortest-path problems in these graphs, and develop Algorithm 2 (DP over the TET-STG), Algorithm 3 (modified Dijkstra over STG+), and Algorithm S1 (modified Dijkstra over TED-STG). Worst-case complexities O(TMN), O(MN + N log N), and O(N^2(M + 2 log N)) are claimed. The paper reports an application to the Ara operon network of E. coli and claims substantial running-time improvements over existing algebraic methods.","tokens_in":26612,"tokens_out":9143,"duration_ms":148683,"significance":"If the results hold, the paper gives a clean and useful unification: rather than developing separate algebraic algorithms for each FHOC variant, all considered problems are reduced to shortest-path computations on explicitly constructed graphs. The reduction proofs for Theorems 1-4 are carefully structured, the complexity analyses of the three algorithms check out, and the worked examples are simple enough to verify by inspection. A particular strength is that the approach genuinely handles time-variant stage and terminal costs for Problem 1, and time-nondecreasing time-variant costs for Problem 2, which goes beyond most prior work. The benchmark on the Ara operon network is potentially valuable, although the reported timing data are missing from the manuscript. The central theoretical contribution is sound under the stated assumptions, but the scope of the time-variant claim for Problem 2 needs to be qualified.","major_comments":[{"comment":"The monotonicity condition (iii) in Assumption 2 is load-bearing for the fixed-destination results, and the unqualified claim of solving Problem 2 with time-variant costs is too strong without it. Proposition 2's cycle-elimination argument in Eq. (21) uses h(xd,k) >= h(xd,k-r) and g(x(t),u(t),t) >= g(x(t),u(t),t-r); if g can decrease over time, removing a cycle can increase cost, so the bound |u*| < |R(x0)| that fixes the number of layers in Definition 7 is invalid. A concrete two-state example: let R(x0)={x0,xd}, place a zero-cost self-loop on x0, set the edge x0->xd to cost max(10-t,0), and set h=0, Omega={xd}. Every optimal sequence waits at least 10 steps and then moves, with cost 0 and K>=11, but the TED-STG with Z=2 contains only the t=0 transition and Dijkstra's algorithm on it returns cost 10. Thus Algorithm S1 and Theorem 4 solve Problem 2 with time-variant costs only under time-nondecreasing costs; the abstract, the contribution list, and the Table I row for Algorithm S1 should state this restriction explicitly.","section":"Section VI.A, Assumption 2 and Definition 7/Theorem 4"},{"comment":"The benchmark timing measurements are not actually reported. The text refers to 'Table ??' twice, once in Task 1 and once in Task 2, but no such table appears in the manuscript. Since the abstract claims that the approach 'can dramatically reduce the running time' and Remark 13 repeats this claim, the missing table is load-bearing for the empirical part of the paper. The authors should supply the timing table with the measured running times of the compared methods, or explicitly qualify the empirical claims as unsupported pending additional experiments.","section":"Section VIII.A/B, 'Table ??'"},{"comment":"The proof of Lemma 5 is omitted with the statement that it can be proved 'in almost the same way as Lemma 3'. Because Theorem 4 relies on Lemma 5 to relate feasible control sequences to paths in the TED-STG, the proof should be included or, at minimum, the t-shift argument that handles the time-dependent terminal cost h(x(K),K) should be spelled out. This is a short argument, but an omitted load-bearing lemma is a gap in the published proof chain as written.","section":"Section VI.C, Lemma 5"}],"minor_comments":[{"comment":"The pseudo-state is labeled delta_0_N,N in the implementation, while Definition 7 gives the pseudo-state no time index; please clarify this implementation label to avoid confusion between N (number of BCN states) and Z (reachable-set size).","section":"Algorithm S1"},{"comment":"The phrase 'Combing Theorem 1 and 2' should read 'Combining Theorem 1 and 2'.","section":"Section V.C"},{"comment":"The sentence 'enumerating all paths from delta_1_4,0 to delta_0_4,5' appears to have state subscripts 4 instead of 8; the TET-STG in Fig. 2 is built from states of the form delta_i_8.","section":"Example 3"},{"comment":"There are minor typos: 'bread-first search' should be 'breadth-first search', and 'intial state' should be 'initial state'.","section":"Section IV"},{"comment":"In the bullet list of Task 1 results, 'the complete state state has 512 states' has a duplicated word; it should read 'the complete state space has 512 states'.","section":"Section VIII.A"},{"comment":"The notation 'uij (15)' refers to a formula defined for the time-variant TET-STG; in the time-invariant setting of Definition 6 the control uij has no time superscript, so the reference should be adjusted for consistency.","section":"Algorithm 3, line 18"}],"recommendation":"major_revision","confidential_remarks":"The main graph-theoretic reductions are sound under the stated assumptions, and I do not see circularity or post hoc tuning in the examples. The decision rests on two fixable issues: the unqualified 'time-variant costs' claim for Problem 2 must be qualified to time-nondecreasing costs, and the missing benchmark timing table must be supplied before the empirical claims can be evaluated. Once those are addressed, the paper would be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read arXiv:1908.02019. The core contribution holds up: Problem 1 (fixed horizon) and Problem 2 (fixed destination) for Boolean control networks are reduced to shortest path problems in STG-based graphs, including time-variant costs and constraints. That is genuinely new compared with [14] and [23], which only handle time-invariant special cases. The TET-STG plus DP algorithm is standard but clean; the TED-STG construction for time-variant fixed-destination costs is the most original piece. The worst-case bounds O(TMN), O(MN + N log N), and O(N^2(M + 2 log N)) check out, and the paper ships Python code, which I respect.\n\nThe mathematical architecture is sound. Theorems 1 through 4 are straightforward proofs of the reductions, and Proposition 2's cycle-elimination argument is valid under Assumption 2. I do not see fitted parameters, circular reasoning, or overclaimed credit: the authors explicitly acknowledge the earlier graph-based work of [14] and [23].\n\nThe big caveat is Assumption 2, and it is load-bearing. For fixed-destination problems, the paper requires h bounded below and g nonnegative, with both nondecreasing in time. The stress-test example is correct: with a zero-cost self-loop and a time-decreasing edge cost to the destination, the optimal sequence can wait many steps before taking the cheap edge, so the bound K < |R(x0)| and hence the finite TED-STG construction fail. The paper states Assumption 2 explicitly, which is to its credit, but the abstract and contribution list say \"time-variant costs\" without the monotonicity qualifier. That overstates the scope. The fix is easy in presentation: keep the assumption and say plainly in the abstract that time-varying costs must be nondecreasing, or extend the theory, which is not obvious.\n\nMinor issues: Lemma 5's proof is omitted, though it is nearly identical to Lemma 3, so this is minor. The benchmark timing table is missing from the supplied text (Table ??), and the running times have no error bars or iteration counts. The Ara operon results are illustrative, not load-bearing, and the missing table should be restored before publication.\n\nWho is this for? Anyone working on BCN optimal control who wants to replace STP matrix algebra with graph algorithms. It deserves a serious referee and, after a revision that fixes the scope wording and supplies the missing benchmark details, it should be accepted. I would cite it and would bring it to a reading group on control of Boolean networks.","headline":"A real unification of BCN optimal control into shortest path problems, with an honest but load-bearing monotonicity assumption and a few missing details worth fixing.","tokens_in":27147,"tokens_out":2009,"would_cite":true,"duration_ms":21781,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93C55","05C85","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that two general finite-horizon optimal control problems for Boolean control networks—fixed horizon and fixed destination, both allowing time-variant costs—are exactly shortest-path problems in tailored state-transition…","keywords":["Boolean control networks","finite-horizon optimal control","shortest path problem","state transition graph","time-expanded graph","dynamic programming","Dijkstra's algorithm","time-variant costs"],"falsifier":"For a small Boolean control network with $|R(x_0)|=3$, choose time-variant costs that satisfy Assumption 2—for example $g(t)=1$ for $t<3$ and $g(t)=2$ afterwards, with zero terminal cost—and compare Algorithm S1's returned plan to exhaustive enumeration of all control sequences of lengths 1 through 5 under the same state and control constraints. If any enumerated sequence yields strictly smaller total cost, Theorem 4's reduction to a shortest path in the TED-STG is false; otherwise the claim survives this check.","tokens_in":26158,"feed_emoji":"🧮","tokens_out":11170,"duration_ms":108110,"temperature":0.7,"pith_summary":"Boolean control networks are deterministic networks of on/off variables, typically gene states, whose evolution is driven by binary inputs; choosing an input sequence to minimize a cost over a finite planning window is a core task for designing interventions. The paper claims that two very general forms of this task, one with a fixed number of steps (Problem 1) and one with an unknown but finite number of steps ending in a target set (Problem 2), can be reformulated exactly as shortest-path problems on specially constructed graphs, even when costs vary with time and when states and inputs are constrained. This unification means that previously scattered special cases—minimum-energy control, minimum-time control, Mayer-type problems, time-discounted costs, and others—are all captured by one graph-theoretic machinery, and the paper derives worst-case running times of $O(TMN)$, $O(MN+N\\log N)$, and $O(N^2(M+2\\log N))$, where $N$ is the number of states and $M$ is the number of control inputs. A sympathetic reader would care because the paper also claims the first solution to fixed-destination optimal control with time-variant costs, and on the Ara-operon benchmark the graph methods are several orders of magnitude faster than algebraic matrix-based methods.","feed_headline":"Finite-horizon Boolean-network control reduces to shortest-path search","feed_subtitle":"Fixed-time and fixed-destination planning, even with time-varying costs, become Dijkstra-style searches on state graphs.","key_machinery":"The load-bearing object is the state transition graph (STG) of the Boolean control network: vertices are the states reachable from a given initial state, and a directed edge exists for each one-step transition; edge weights are set to the minimum stage cost among the controls that realize the transition. Around this object the paper builds three variants: the TET-STG (layered by time, for fixed horizons), the STG+ (a static graph with a pseudo-state for terminal costs, for time-invariant fixed-destination problems), and the TED-STG (time-expanded layers up to $|R(x_0)|-1$, with pseudo-state edges from every destination occurrence, for time-variant fixed-destination problems). The pseudo-state $\\delta^0_N$ is the device that converts a terminal cost into an edge weight. The reduction is carried by the fact that any feasible control sequence maps to a path whose weight is at most the control cost, with equality when each transition uses the cheapest admissible control; combined with finiteness of the candidate set, this turns planning into an unconstrained shortest-path computation.","core_discovery":"The paper's central claim is a reduction. The fixed-time problem (Problem 1) is equivalent to a shortest-path problem in the time-expanded fixed-time state transition graph (TET-STG), which places one copy of each reachable state at each time step and adds a pseudo-state to absorb the terminal cost; the optimal cost is the weight of a shortest path from the initial state at time 0 to that pseudo-state, and the optimal control sequence is read off from the minimizing controls along the path. For the fixed-destination problem with time-invariant costs, the extended state transition graph (STG+) adds a terminal pseudo-state to the ordinary state graph, and the problem becomes a standard single-pair shortest-path problem solved by Dijkstra's algorithm (Algorithm 3). For time-variant costs in the fixed-destination problem, the time-expanded fixed-destination state transition graph (TED-STG) stacks the reachable states over all times up to $|R(x_0)|-1$ and connects every occurrence of a destination state to the pseudo-state, so the problem again becomes a single-pair shortest-path problem (Algorithm S1). Equality between the optimal control cost and the shortest-path weight is shown by pairing each control sequence with a path whose weight never exceeds the control cost, and by noting that the optimal one-step control on each transition attains equality.","pith_inferences":["The paper does not treat stochastic networks, but the same time-expanded construction would apply to probabilistic Boolean networks if edge weights were replaced by expected stage costs, although the shortest-path equivalence would then need a careful treatment of probabilities.","A natural stress test of the framework is to run Algorithm S1 on networks where $|R(x_0)|$ is close to $N$; the complexity advantage over algebraic methods comes mostly from sparse reachability, so dense networks would erase much of the reported speed-up.","The monotonicity assumption in Assumption 2 is what makes the finite bound $|u^*|<|R(x_0)|$ hold; the paper's fixed-destination results are best read as showing that time-variant costs are tractable precisely when waiting never makes travel cheaper."],"forward_implications":["The same graph pipeline solves every special case listed in the literature—minimum-energy, minimum-time, Mayer-type, Lagrange-type, and time-discounted problems—without needing a new method for each case.","Fixed-destination optimal control with time-variant costs, previously unsolved, is solvable in $O(N^2(M+2\\log N))$ worst-case time, compared with the $O(MN^3)$ cost of checking every horizon length with a fixed-time solver.","Because the graphs are built only from the reachable set $R(x_0)$, the algorithms exploit networks whose reachable part is small; on the Ara-operon example the reachable set has 108 states out of 512.","For fixed-horizon problems, the equivalence holds even with negative edge weights, since the horizon is fixed and cycles cannot be exploited; only bounded-below costs are required."],"supporting_citations":[{"why":"Supplies the multilinear semi-tensor-product representation of Boolean functions and the algebraic state-space form used to derive one-step reachability.","marker":"[6]"},{"why":"Introduces the input-state incidence framework that motivates building graphs directly from the network transition matrix.","marker":"[7]"},{"why":"Defines minimum-energy control as a special case of Problem 2; the paper re-derives it as a shortest-path instance and compares complexity.","marker":"[14]"},{"why":"Defines minimum-time control, which Problem 2 specializes to, and provides a complexity baseline.","marker":"[15]"},{"why":"Proposes a general finite-horizon optimal-control formulation with stage and terminal costs; the paper's Problem 1 extends it to time-variant costs.","marker":"[16]"},{"why":"The closest graph-theoretical predecessor, solving a k-edge shortest-path version; the paper generalizes it to time-variant costs and terminal constraints.","marker":"[23]"},{"why":"Standard reference for breadth-first search, Dijkstra's algorithm, dynamic programming, and the Fibonacci-heap complexity used in the analysis.","marker":"[33]"},{"why":"Space-time network construction whose time-expanded idea underlies the TET-STG and TED-STG.","marker":"[34]"}],"fun_headline_variants":["Boolean network control: every finite-horizon case is a shortest path","Unified graph approach makes BCN optimal control pathfinding","New reduction: BCN finite-horizon control as Dijkstra search","First unified solution for BCN control with time-varying costs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's fixed-destination results require that per-step costs never be negative and that both per-step and terminal costs never decrease as time goes on; if later steps could become cheaper, looping around a cycle could make total cost arbitrarily small and no finite optimal plan would exist.","fun_headline_variants_meta":{"raw":{"variants":["Boolean network control: every finite-horizon case is a shortest path","Unified graph approach makes BCN optimal control pathfinding","New reduction: BCN finite-horizon control as Dijkstra search","First unified solution for BCN control with time-varying costs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000599,"raw_usage":{"total_tokens":2882,"prompt_tokens":1110,"completion_tokens":1772,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":726,"completion_tokens_details":{"reasoning_tokens":1699}},"tokens_in":726,"tokens_out":1772,"duration_ms":13145,"temperature":1.0,"reasoning_tokens":1699,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:57:12.347395+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small Boolean control network with $|R(x_0)|=3$, choose time-variant costs that satisfy Assumption 2—for example $g(t)=1$ for $t<3$ and $g(t)=2$ afterwards, with zero terminal cost—and compare Algorithm S1's returned plan to exhaustive enumeration of all control sequences of lengths 1 through 5 under the same state and control constraints. If any enumerated sequence yields strictly smaller total cost, Theorem 4's reduction to a shortest path in the TED-STG is false; otherwise the claim survives this check.","supporting_citations":[{"cited_title":"A linear representation of dynamics of boolean networks,","cited_arxiv_id":null,"evidence_quote":"Supplies the multilinear semi-tensor-product representation of Boolean functions and the algebraic state-space form used to derive one-step reachability."},{"cited_title":"Input-state incidence matrix of boolean control networks and its applications,","cited_arxiv_id":null,"evidence_quote":"Introduces the input-state incidence framework that motivates building graphs directly from the network transition matrix."},{"cited_title":"Minimum energy control and optimal-satisfactory control of boolean control network,","cited_arxiv_id":null,"evidence_quote":"Defines minimum-energy control as a special case of Problem 2; the paper re-derives it as a shortest-path instance and compares complexity."},{"cited_title":"Minimum-time control of boolean networks,","cited_arxiv_id":null,"evidence_quote":"Defines minimum-time control, which Problem 2 specializes to, and provides a complexity baseline."},{"cited_title":"Optimal control of boolean control networks,","cited_arxiv_id":null,"evidence_quote":"Proposes a general finite-horizon optimal-control formulation with stage and terminal costs; the paper's Problem 1 extends it to time-variant costs."},{"cited_title":"Optimal control problem of boolean control networks: A graph-theoretical approach,","cited_arxiv_id":null,"evidence_quote":"The closest graph-theoretical predecessor, solving a k-edge shortest-path version; the paper generalizes it to time-variant costs and terminal constraints."},{"cited_title":"Shortest path algorithms in trans- portation models: classical and innovative aspects,","cited_arxiv_id":null,"evidence_quote":"Space-time network construction whose time-expanded idea underlies the TET-STG and TED-STG."}],"review_version":1}