{"id":"065c79b7-7068-44c7-8be9-b2e1e5152ff8","arxiv_id":"2507.07894","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new bicriteria transit network design problem is shown to be NP-complete and inapproximable in general, with polynomial-time approximation schemes in restricted fixed-flow cases.","lead":"This paper introduces a bicriteria directed multimodal transit network design problem and proves it is NP-complete even in highly simplified settings, and that no polynomial-time approximation can guarantee any computable approximation ratio unless P=NP. It also identifies restricted cases, such as a fixed passenger flow, where approximation schemes exist and where part of the Pareto frontier can be characterized.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's PTAS/FPTAS construction enumerates an exponential number of items in binary-encoded flows and capacities, so the claimed approximation schemes are not established as stated.","rationale":"The reader's weakest_assumption correctly identifies the exponential item enumeration in Theorem 4.2. This is the most load-bearing concern because, unlike the typos in Theorem 3.2 (the swapped (a,b) and the unstated c1/B), it is not a presentational slip: the proposed construction genuinely fails to run in polynomial time on binary-encoded inputs. The hardness theorems remain plausible and likely repairable, but the positive approximability claim is unsupported as written. A conditional verdict is appropriate: the authors should either provide a compact multiplicity encoding (e.g., powers-of-two) or restrict the theorem to unary-encoded flows and capacities. I therefore keep the reader's CONDITIONAL verdict unchanged.","tokens_in":18884,"tokens_out":22398,"duration_ms":248264,"concrete_test":"Take a fixed-flow MSP instance with a single edge e, F(e) = 2^N, m = 1, k_1 = 2, eta_0 = 2, eta_1 = 1, c_1 = 1, B = 1, and a = infinity. Compute the size of the KPS instance built by Theorem 4.2(b): it adds floor(F(e)/k_1) = 2^(N-1) copies of the full-vehicle item plus partial-fill items. The input length is O(N), so the construction is exponential in the input size. Then attempt to replace the 2^(N-1) copies by O(N) items via binary splitting (powers of two) and verify whether the resulting instance still yields a (1+epsilon)-approximation to the original; if no such polynomial-size reduction is provided, the theorem remains unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Theorem 4.2, the proofs of parts (a) and (b) reduce fixed-flow MSP to MKPS/KPS by adding, for each edge j and mode i, one item for every full vehicle copy floor(F(e_j)/k_i) and one item for each partial fill f in [ceil(eta_i/eta_0), min(k_i, F(e_j))]. Since F(e_j) and k_i are given as binary integers, both the number of copies and the size of the partial-fill range can be exponential in the input length; for instance, F(e) = 2^N and k_i = 2 yields 2^(N-1) full-vehicle items. The proof then invokes a PTAS/FPTAS whose runtime is polynomial in the number of items, so an exponential item count makes the construction non-polynomial. No compact encoding of multiplicities is provided, so Theorem 4.2 does not establish the stated approximability results for fixed-flow MSP. This is the same gap identified by the reader, and it directly undermines the paper's advertised positive approximability claims.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Modal Split Problem (MSP), a bicriteria directed network design model for public transport planning, and analyzes its complexity. The main hardness results are: MSP is NP-complete even with unit edge weights, a single mode, unit demands, and unit mode parameters (Theorem 3.2); the optimization version is not approximable within any polynomial-time computable function alpha(|V|) unless P=NP (Theorem 3.4); and MSP remains NP-complete when the passenger flow is fixed or when the graph is a single edge (Theorem 4.1). The paper also claims a PTAS for fixed-flow MSP and an FPTAS for the single-mode fixed-flow case (Theorem 4.2), together with a geometric characterization of a Pareto-frontier segment for a continuous relaxation (Theorems 4.3 and 4.4) and a sampling algorithm. An appendix proves NP-completeness and inapproximability for the directed network design problem DiNDP.","tokens_in":19139,"tokens_out":29154,"duration_ms":344852,"significance":"The hardness results, if correct, are significant: they show that even extremely stripped-down versions of a practically motivated bicriteria transit design problem are intractable, and that no general approximation guarantee exists. The paper also contains useful transfer arguments from undirected to directed network design, and the Pareto-frontier relaxation result is an appealing geometric idea that could be valuable for practitioners. The reductions are from standard NP-complete problems (X3C, SSUM, UKPS, DiSTP) and are checkable in principle. However, as written the positive approximability claims in Theorem 4.2 are not established, and several load-bearing steps in Theorems 3.2 and 4.1(a) contain inconsistencies. The manuscript therefore needs substantial revision before its claims can be accepted.","major_comments":[{"comment":"The constructed MKPS/KPS instance is not polynomial in the input size. Since F(e_j) and k_i are binary integers, the number of full-vehicle copies floor(F(e_j)/k_i) and the number of partial-fill values f in [ceil(eta_i/eta_0), min(k_i,F(e_j))] can both be exponential; for example, F(e_j)=2^N with k_i=2 gives 2^{N-1} full-vehicle items. The PTAS/FPTAS runtimes are polynomial in the item count, so the scheme is not a polynomial-time algorithm. The proof needs a compact encoding: binary splitting of multiplicities, and an argument that only one partial-fill item per edge and mode is needed. Additionally, the proof invokes a PTAS for MKPS with r=|E|+1 constraints, but the cited reference [20] concerns multiobjective knapsack, and multidimensional knapsack with unbounded dimension is not known to admit a PTAS (it generalizes maximum set packing). The claimed approximation schemes are therefore not established as stated.","section":"Section 4, Theorem 4.2 proof, items i)-ii)"},{"comment":"The reduction as written is internally inconsistent. The MSP decision problem defined in Section 2 requires T(F,L,M) <= a and H(F,L,M) <= b, but the proof states (a,b) := (beta,gamma) and then uses H <= a = beta and T <= b = gamma, so the roles of a and b are swapped relative to the definition. In addition, the cost c1 of the single public transport mode is never specified; for the DiNDP budget beta to map to the MSP budget constraint, one must set c1 = 1. These are fixable, but the reduction is currently ill-defined.","section":"Section 3, Theorem 3.2"},{"comment":"The assertion that T(F',L',M') and gamma are integral and hence T(F',L',M') < gamma + 1 implies T(F',L',M') <= gamma is not justified. The rerouted flow F' can be fractional: the original feasible solution is allowed to have fractional flows and fractional modal splits, and no integrality argument is given. Since this integrality is used to close the reduction, the proof needs an explicit argument that an integral feasible solution exists, e.g., by path decomposition with integral demands and non-binding capacities.","section":"Section 3, Theorem 3.2 proof, integrality step"},{"comment":"The SSUM reduction contains several sign and endpoint errors. The demand should be D(v1, v_{n+1}) = 2 on the last vertex, not D(v1, v_{n-1}); the modal split convention after fixing L is reversed (M(e)=(0,1) means mode 1, so it should be assigned when L(e)_1 = 1, not when L(e)_1 = 0); and the sentence claiming that an edge with L(e)=0 reduces energy should refer to L(e)=1. The intended accounting is recoverable, but as written the reduction does not correctly establish the claimed NP-completeness of fixed-flow MSP.","section":"Section 4, Theorem 4.1(a)"},{"comment":"The lower bound H^ := eta * sum_e w(e) F(e) with eta = min_{i=1..m} eta_i is not a valid lower bound when eta_0 < eta, because the all-mode-0 solution has energy H = eta_0 * sum_e w(e) F(e), which could be smaller than H^. The assumption that eta != eta_0 does not address this, since eta_i is energy per vehicle while eta_0 is energy per passenger, so comparing min_{i>=1} eta_i with eta_0 mixes incompatible units. The approximation-factor transformation needs a correct lower bound, for example using min_{i=0..m} eta_i/k_i appropriately or another per-passenger quantity.","section":"Section 4, Theorem 4.2 proof, lower bound"}],"minor_comments":[{"comment":"In the patch vector expression, the second coordinate of the base point is written as tau_0 * sum_e w(e) F(e), but by Eq. (2) it should be eta_0 * sum_e w(e) F(e).","section":"Section 4, paragraph before Eq. (3)"},{"comment":"The vector v_i is defined as (tau_i - tau_0, eta_i/k_i - tau_0); the second entry should be eta_i/k_i - eta_0. Also the preimage of Psi_0 is described by M = 0, but a modal split must satisfy sum_i M_i = 1; this should be the all-mode-0 split.","section":"Section 4, Theorem 4.3 proof"},{"comment":"The proof uses the notation 2vmaxW and 2smaxW in the energy computation; these mix v_max/s_max and W/A'. They should be cleaned up for consistency.","section":"Section 4, Theorem 4.1(b) proof"},{"comment":"In the lower-bound argument for R_{V,U}(G'), the quantity m is undefined; it should be h, the number of U-nodes, matching the previous inequality.","section":"Section 3, Lemma 3.1 proof"}],"recommendation":"major_revision","confidential_remarks":"The hard-complexity core of the paper is plausible once Theorem 3.2's notation is repaired, and Theorem 3.4's counting argument in fact works. The main risk is the positive approximability section: the item-count problem in Theorem 4.2 is not cosmetic, and the citation [20] appears to be for multiobjective knapsack rather than multidimensional knapsack, so the PTAS claim for growing constraint dimension is doubtful. If the authors cannot provide a correct polynomial-time approximation scheme for fixed-flow MSP, the paper should probably be revised to focus on the hardness results. I would not recommend acceptance in the present form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2507.07894. The paper defines a new bicriteria multimodal network design problem (MSP) and maps out its complexity: NP-complete in very stripped-down cases, no α(|V|)-approximation unless P=NP, and a claimed PTAS/FPTAS when the passenger flow is fixed. The hardness results look essentially right. The reductions from X3C and DiSTP are standard but adapted to a directed setting that genuinely seems to have been missing; Lemma 3.5 (the 2-approximation via shortest-path arborescences) is a clean observation. The model itself is reasonable and the paper is honest about what it does and doesn't cover.\n\nThe soft spots are real, though mostly repairable. In Theorem 3.2 the instance parameter assignment is reversed: it sets (a,b)=(β,γ) but then uses H≤a and T≤γ, which only works if a=γ and b=β. The integrality step is fine after that swap. In Theorem 4.1(a) the algebra has errors: the base energy should be 2Σ (with demand 2 on each edge) so b should be 2Σ−A, not Σ−A, and the inequality direction in the subset-sum conclusion is backwards. The intended reduction still works, but as written it doesn't parse.\n\nThe bigger problem is Theorem 4.2. The PTAS/FPTAS proofs construct MKPS/KPS instances by adding one item per vehicle copy and one item per partial-fill value. Flows and capacities are given in binary, so the number of copies floor(F(e)/k_i) and the range of f can be exponential in the input length. No compact encoding of multiplicities is provided, so the reduction is not polynomial and the approximation schemes are not established. The stress-test note is right on this; it's a load-bearing gap in the claimed positive results. It may be fixable via binary splitting or a different DP, but it is not a typo.\n\nOverall: I'd send this to a serious referee rather than desk-reject. The core complexity claims are likely correct and valuable for the transportation network design community. The authors need a major revision: fix the parameter swap, the algebra, and either repair the PTAS proof or qualify the claim. The paper deserves a round of review; it just shouldn't be accepted as is.","headline":"A new bicriteria multimodal network design problem with plausible NP-hardness results, but the fixed-flow PTAS/FPTAS proof has a real complexity gap and several smaller errors need repair.","tokens_in":19623,"tokens_out":8785,"would_cite":false,"duration_ms":85508,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","90B10","90C27","90C29"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves the bicriteria public-transport network design problem is NP-complete even when all weights, demands, and mode parameters are 1, and that no polynomial-factor approximation exists for the general optimisation version…","keywords":["bicriteria optimization","network design","NP-completeness","inapproximability","public transportation planning","knapsack problem","Pareto frontier","directed graphs"],"falsifier":"Run the Theorem 3.4 construction on a Directed Steiner Tree instance whose optimal arborescence costs more than the budget $B$: the reduction predicts that every feasible MSP solution must place at least one passenger on private transport, forcing energy at least $\\lceil\\alpha(n)(|E|+1)\\rceil$, so any claimed $\\alpha$-approximation that returns energy at most $\\alpha(n)|E|$ would simultaneously decide DiSTP and refute the inapproximability claim, unless the reduction itself is wrong.","tokens_in":18688,"feed_emoji":"🚌","tokens_out":12010,"duration_ms":133532,"temperature":0.7,"pith_summary":"This paper analyses the Modal Split Problem (MSP), a model for choosing which links of a public-transport network to build, how many vehicles to run, and how passengers should be routed, while balancing passenger travel time against total energy use under a construction budget. The authors prove that even the most stripped-down version of this problem is NP-complete: with unit edge weights, a single public mode, unit demand between every pair of nodes, and unit energy and time coefficients, deciding whether a feasible plan meets given travel-time and energy bounds is already hard. They further prove that the optimisation version, minimising energy subject to a travel-time limit, cannot be approximated within any polynomial-time-computable factor $\\alpha(|V|)$ unless P=NP, even when the travel-time bound is removed. On the positive side, they show that when passenger flows are fixed the remaining difficulty is a knapsack-type procurement problem, which admits a PTAS and, for a single mode, an FPTAS; they also identify a line segment of the relaxed problem's Pareto frontier that yields genuinely Pareto-optimal layouts under an ordering condition on mode parameters.","feed_headline":"Even the simplest transit design problem is NP-complete","feed_subtitle":"With unit demands and one mode, transit planning stays intractable, and no general approximation is guaranteed.","key_machinery":"The argument runs through three constructions. Lemma 3.1 shows the directed Network Design Problem DiNDP is NP-complete even with unit weights and distances by rebuilding a symmetric subgraph from an Exact-3-Cover instance, then Theorem 3.2 reduces DiNDP to MSP by setting the public-mode energy coefficient to $\\eta_1=1$, private-transport energy so high that any feasible solution must be connected, and identifying construction cost with energy and routing cost with travel time. Inapproximability is carried by the directed Steiner tree problem: Theorem 3.4 plants demand $\\lceil\\alpha(n)(|E|+1)\\rceil$ on each Steiner commodity so that an $\\alpha$-approximation of energy would decide whether a bounded-cost arborescence exists. The fixed-flow results translate MSP into a Multidimensional Knapsack or Unbounded Knapsack instance whose variables are vehicle counts per edge and whose items record energy savings, construction cost, and passenger load; the known PTAS/FPTAS for knapsack then transfer back. Finally, the Pareto-frontier statement uses the geometric ordering of mode direction vectors $(\\tau_i-\\tau_0,\\eta_i/k_i-\\eta_0)$: for the steepest mode, a line segment between the all-private solution and the scaled single-mode solution is undominated in the relaxation.","core_discovery":"The paper's central discovery is that the Modal Split Problem is intractable in a very robust sense and that its tractable parts are exactly the ones reducible to knapsack. Theorem 3.2 proves NP-completeness of MSP even with $w(e)=1$, $m=1$, $D(u,v)=1$ for all $u\\neq v$, and $\\eta_1=\\tau_1=1$, by reducing the directed network design problem DiNDP to MSP; this is the strongest possible parameter collapse short of making the problem empty. Theorem 3.4 proves that for any polynomial-time computable function $\\alpha(|V|)$, the optimisation version with $a=\\infty$ is not $\\alpha(|V|)$-approximable unless P=NP, via a reduction from Directed Steiner Tree in which a large demand $\\lceil\\alpha(n)(|E|+1)\\rceil$ forces any approximation to separate feasible from infeasible Steiner instances. Section 4 shows NP-completeness persists when the passenger flow is fixed, when the graph is tree-like, and even when the graph is a single edge, and derives a PTAS/FPTAS for fixed-flow MSP from known approximation schemes for multidimensional and ordinary knapsack. The paper also proves that for instances whose mode parameters satisfy a slope-ordering condition, a specific line segment in the objective space lies on the Pareto frontier of a continuous relaxation, and every integral layout on it is Pareto-optimal for the original problem.","pith_inferences":["The positive fixed-flow theorem as written needs a compact encoding: the construction in Theorem 4.2 lists $\\lfloor F(e)/k_i\\rfloor$ copies and every partial-fill level $f$, which can be exponential in the bit length of the demand; a polynomial-time scheme therefore requires aggregation or a different encoding.","Reading the one-edge and tree-like hardness cases together suggests that the intrinsic difficulty of transit frequency setting lies in vehicle-type choice and fill constraints, not in route choice; knapsack-style approximation is the right tool for the procurement stage.","The relaxation's Pareto segment can serve as an outer bound in exact algorithms: any candidate solution whose objective point lies strictly below the segment cannot be Pareto-optimal for the integer problem, so the segment could prune a branch-and-bound search.","A concrete stress test: take a single-edge instance with $F(e)=2^p$ and $k_1=3$ and measure whether the claimed FPTAS run time stays polynomial in $p$; if it does not, the theorem needs a compact item representation."],"forward_implications":["Even with unit weights, one mode, and unit demands, MSP has no polynomial-time exact algorithm unless P=NP, so exact optimisation for such problems is inherently exponential in the worst case.","For the general energy-minimisation version, no polynomial-time algorithm can guarantee any factor $\\alpha(|V|)$ in the number of nodes, so approximation guarantees for MSP must come from additional structure rather than from a universal bound.","When the passenger flow is fixed, the leftover problem is a vehicle procurement problem with knapsack structure: a PTAS exists, and with one mode an FPTAS exists, giving practical near-optimal energy layouts.","For instances satisfying the slope-ordering condition, the relaxed problem has a known undominated line segment in objective space, and integral points on it are genuinely Pareto-optimal solutions to the original problem.","The directed versions of the underlying network design problems are likewise hard: DiNDP is NP-complete and cannot be approximated within $|V|^{1-\\varepsilon}$ unless P=NP."],"supporting_citations":[{"why":"Supplies the undirected network design hardness result whose structure the directed Lemma 3.1 proof reconstructs.","marker":"[13]"},{"why":"Establishes that Exact-3-Cover is NP-complete, the source problem used in Lemma 3.1.","marker":"[14]"},{"why":"Provides the undirected inapproximability and the 2-approximation for unweighted network design that the paper adapts to directed DiNDP and MSP.","marker":"[4]"},{"why":"Gives NP-completeness of Steiner tree, the basis for the Directed Steiner Tree problem used in Theorem 3.4.","marker":"[15]"},{"why":"Supplies polynomial-time shortest-path arborescence computation used in the 2-approximation construction of Lemma 3.5.","marker":"[17]"},{"why":"Provides the FPTAS for 0-1 knapsack that underlies the fixed-flow FPTAS in Theorem 4.2 b).","marker":"[19]"},{"why":"Provides the PTAS for multidimensional knapsack used in Theorem 4.2 a).","marker":"[20]"}],"fun_headline_variants":["Transit design stays NP-hard even with one mode and unit demands","No approximation for transit design even in simplest case","Even single-mode transit planning has no guaranteed approximation","Transit design intractable even with unit demands and one mode","Knapsack cases are the only easy transit design instances"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's fixed-flow approximation theorem assumes that writing out one knapsack item for each vehicle copy and each partial-fill level remains polynomial; with binary-encoded demands the list can be exponentially long, so the PTAS/FPTAS claim depends on an encoding argument that is not supplied.","fun_headline_variants_meta":{"raw":{"variants":["Transit design stays NP-hard even with one mode and unit demands","No approximation for transit design even in simplest case","Even single-mode transit planning has no guaranteed approximation","Transit design intractable even with unit demands and one mode","Knapsack cases are the only easy transit design instances"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000971,"raw_usage":{"total_tokens":4124,"prompt_tokens":939,"completion_tokens":3185,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":555,"completion_tokens_details":{"reasoning_tokens":3105}},"tokens_in":555,"tokens_out":3185,"duration_ms":22364,"temperature":1.0,"reasoning_tokens":3105,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:33:28.925317+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Theorem 3.4 construction on a Directed Steiner Tree instance whose optimal arborescence costs more than the budget $B$: the reduction predicts that every feasible MSP solution must place at least one passenger on private transport, forcing energy at least $\\lceil\\alpha(n)(|E|+1)\\rceil$, so any claimed $\\alpha$-approximation that returns energy at most $\\alpha(n)|E|$ would simultaneously decide DiSTP and refute the inapproximability claim, unless the reduction itself is wrong.","supporting_citations":[{"cited_title":"The c om- plexity of the network design problem","cited_arxiv_id":null,"evidence_quote":"Supplies the undirected network design hardness result whose structure the directed Lemma 3.1 proof reconstructs."},{"cited_title":"Worst-Case Analysis of Network Design Problem Heu ris- tics","cited_arxiv_id":null,"evidence_quote":"Provides the undirected inapproximability and the 2-approximation for unweighted network design that the paper adapts to directed DiNDP and MSP."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives NP-completeness of Steiner tree, the basis for the Directed Steiner Tree problem used in Theorem 3.4."},{"cited_title":"Efficient route planning on public transportation n et- works: A labelling approach","cited_arxiv_id":null,"evidence_quote":"Supplies polynomial-time shortest-path arborescence computation used in the 2-approximation construction of Lemma 3.5."},{"cited_title":"A fully polynomial approximation al- gorithm for the 0–1 knapsack problem","cited_arxiv_id":null,"evidence_quote":"Provides the FPTAS for 0-1 knapsack that underlies the fixed-flow FPTAS in Theorem 4.2 b)."},{"cited_title":"Approximating Mult iobjec- tive Knapsack Problems","cited_arxiv_id":null,"evidence_quote":"Provides the PTAS for multidimensional knapsack used in Theorem 4.2 a)."}],"review_version":1}