{"id":"d9e90d67-e32a-4839-a531-1a8bd3d5062f","arxiv_id":"2411.17596","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"low","formal_verification":"none","parameter_count":7,"one_line_summary":"Arcee is a PACE 2024 OCM solver combining penalty-graph SCC splitting, Dujmovic-style reduction rules, sifting/force-swapping heuristics, and exact FAS-based ILP and branch-and-bound, achieving 4th, 8th, and 4th place in the three tracks.","lead":"This paper describes Arcee, a solver for the NP-hard One-Sided Crossing Minimization problem, built for the 2024 PACE Challenge, where it placed 4th in the heuristic track, 8th in the exact track, and 4th in the parameterized track. It combines graph splitting, data-reduction rules, sifting and force-swapping local search, and exact ILP and branch-and-bound methods, making it a useful reference for crossing-minimization practitioners.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Tuning on a hand-picked subset of public instances is a real generalization risk, but the paper's core claim (competitive PACE results) is not disproven by it.","rationale":"The reader's weakest_assumption points to public-instance tuning as the main risk, and I agree: it is the single most load-bearing assumption in the paper's empirical argument. The algorithmic ingredients (modified RRlarge with a lower bound, SCC splitting, lazy cycle generation, sifting and force swapping) are internally consistent; the modified RRlarge correctness argument in Section 3.2 is a valid exchange argument, and the SCC/partition splitting observations are standard and correct. Therefore the load-bearing concern is not about algorithm soundness but about whether the reported performance numbers generalize. The key specific evidence for the concern is Section 8.2 item 4, which explicitly says SMAC3 was run for 24 hours on 10 public instances selected because Arcee was suboptimal on them, i.e., the tuning set was chosen using the public leaderboard. The evaluation in Table 1 then reports aggregate points for all 200 instances including those 100 public ones, so the reported 6e-5 gain is at least partially a training-set improvement. The paper also reports no variance for randomized heuristics, so a 5e-5-point gap between 'no smac' and 'submission' in Table 1 has no error bars; the gap is smaller than a single instance's rounding to the nearest 1e-5 of a point and could plausibly be noise. The official PACE placements are externally audited and thus support the broad competitiveness claim, but the paper's own attribution of the final placement to the SMAC-tuned force swapping is the vulnerable part. My recommendation is to keep the reader's CONDITIONAL verdict: the concern is real but it is a measurement concern, conditional on code and data release, not a mathematical error. If a private-instance-only rerun still shows the tuned variant winning, the concern is resolved; if not, the paper would need to downgrade the strength of its ablation claims. No independent support currently outweighs the missing variance/held-out evaluation: there is no released code or data, no formal verification, and the only external check is the official ranking, which did not require the ablation to generalize. Thus CONDITIONAL remains the right verdict.","tokens_in":12068,"tokens_out":1983,"duration_ms":16243,"concrete_test":"Recompute Table 1's 'submission' and 'no smac' rows on the 100 private PACE instances only, excluding all 100 public instances, with 5 repeated randomized runs per configuration (same time limit, same hardware). If the SMAC-tuned configuration does not beat the 'no smac' configuration on private instances by at least the same relative margin (or at all), the reported ablation gain of 6e-5 points is public-set overfitting. Also report mean/standard deviation over the 5 runs per instance so the 5e-5 total-score gap can be compared to run-to-run variance.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central performance claim in Section 9 rests on empirical competitive results (4th heuristic, 8th exact, 4th parameterized). The weakest load-bearing point is not algorithmic correctness; it is that the heuristic's force-swapping parameters, and especially the claimed 6e-5 point gain from SMAC3 tuning, were selected on only 10 public instances where Arcee was suboptimal, and the same public instances are included in Table 1 and the final score. Section 8.2 item 4 describes selecting instances 'from the public dataset for which suboptimal solutions were not previously found', using the public leaderboard to identify other solvers' better results, then optimizing parameters for 24 hours. There is no separate test set and no variance reporting for randomized heuristics (random sifting order, random initial orders, randomized force swap). The final score of 199.9998 vs. 199.9993 for 'no smac' is a 5e-5/200 = 0.000025% total-score gain over a tuned-and-tested-on-the-same-instances baseline; the public leaderboard was used in the loop, so the gain could be partially overfit to what other teams' solvers happened to find on those 10 public instances rather than to intrinsic instance difficulty. This is a measurement/dataset circularity, not a logical inconsistency, and it does not invalidate the official rankings, but it does weaken the paper's ablation-based claim that the SMAC-tuned parameters are the reason for the competitive placement.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper describes Arcee, the authors' solver for the One-Sided Crossing Minimization (OCM) problem submitted to the 2024 PACE Challenge. The solver combines graph splitting based on the penalty graph's strongly connected components, reduction rules RR1, RR2, RRLO1, and a modified RRlarge rule that incorporates a trivial lower bound; a heuristic track using median/barycenter initial orders, sifting, force swapping, and large-graph truncation; and an exact/parameterized track that translates OCM to Feedback Arc Set and solves it with two ILP formulations with row generation, plus a branch-and-bound solver with cycle-packing lower bounds and a local-search upper bound. The paper reports official PACE results: 4th place in the heuristic track (1st student), 8th in the exact track (2nd student), and 4th in the parameterized track (1st student), and presents ablations over the heuristic components.","tokens_in":12368,"tokens_out":5459,"duration_ms":55069,"significance":"If the results are taken at face value, the paper is a useful practical contribution: it documents a competitive, well-engineered OCM solver and provides a correct integration of a lower-bound-aware reduction rule into the existing RRlarge framework. The strongest evidence is independent: the official PACE rankings on private instances, the cactus plots of re-evaluated top solvers, and the clarity of the modified RRlarge correctness argument. The paper is honest about several limitations, including the lack of any use of the cutwidth parameter in the parameterized track. Its main weaknesses are experimental: the ablation table reports single runs of a randomized heuristic, and the SMAC tuning was performed on a subset of the public instances that are also included in the reported aggregate score. These issues affect the strength of the attribution of the final score to specific components, but they do not undermine the official placement claims.","major_comments":[{"comment":"The ablation that attributes the final heuristic score to force swapping and SMAC-tuned parameters does not use a clean train/test split. Footnote 2 states that the force-swapping parameters were optimized by SMAC3 on 10 public instances selected because the public leaderboard showed suboptimal solutions, and Table 1 reports points for the public and private instances together. The reported additional gain of 6e-5 points from the SMAC parameters is therefore measured, at least in part, on the very instances used for tuning. The authors should separate public and private scores, evaluate the final configurations on a held-out set, or otherwise substantiate that the SMAC gain is not an artifact of tuning on those 10 instances.","section":"§8.2, Table 1, footnote 2"},{"comment":"The heuristic is randomized (random sifting order, random initial orders, randomized force swapping), yet Table 1 reports a single run per configuration and gives no variance or repeated-run statistics. With a total-score difference of only 6e-5 points between the 'no smac' and 'submission' rows, single runs cannot establish that this difference is not run-to-run noise. The authors should report at least a few seeds for the key configurations, or state that the official PACE score is one particular seed and justify why the differences are meaningful.","section":"§8.2, §4.1"},{"comment":"The exact solver's central modification to the approach of Baharev et al. is to keep the initial heuristic and add only cycles contradicting it, rather than recomputing an FAS heuristic on each updated graph G'. The paper justifies this with the unquantified statement that the modification 'has superior performance in our tests'. No experiment compares the two cycle-generation strategies. Since this modification is presented as a main algorithmic idea and underlies the reported exact and parameterized results, the comparison should be reported or the claim should be downgraded to an informal observation.","section":"§5.2, Algorithm 1"}],"minor_comments":[{"comment":"The sentence 'Its running time running time is O(n log n)' contains a duplicated phrase.","section":"§1.1"},{"comment":"The sentence 'cab > cba contradicts lower bound ≤ upper bound' is not by itself clear: cab > cba does not contradict LB ≤ UB. The contradiction follows from the inequality cba + LB - cab > UB together with LB ≤ UB, and the proof should say this explicitly.","section":"§3.2"},{"comment":"The x-marks in Table 1 do not align unambiguously with the column headers, especially for the 'no rr' and 'no smac' rows, making it hard to tell which components are active in each configuration. Clearer row labels or explicit active/inactive markers are needed.","section":"Table 1"},{"comment":"The conjecture that small cutwidth may bound the size of strongly connected components in the penalty graph is stated without evidence; it should be marked explicitly as speculation, since the parameterized instances alone cannot establish it.","section":"§8.4"},{"comment":"The statement that ILP solvers produced incorrect solutions due to numerical issues should specify which solver and settings were used and whether the issue was observed with both Gurobi and SCIP.","section":"§5.2"},{"comment":"The sentence 'The complete ranking can be found on the official PACE website' should include a URL or a formal citation so that the reader can access the full ranking.","section":"§8.5"}],"recommendation":"major_revision","confidential_remarks":"The official PACE placements are credible, independent evidence that the solver is competitive, and the central algorithmic derivation is sound. The main gap is methodological: the journal version's own ablation claims about the SMAC-tuned parameters and the force-swapping component need a proper hold-out evaluation and variance reporting. I would also ask for an artifact/code availability statement, since the paper describes a concrete system but currently provides no link to the solver or benchmark scripts. There is no novelty-disclosure concern; the related work is adequately covered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — this is a truthful, well-scoped PACE 2024 solver report. The genuinely new pieces are small: the lower-bound-aware RRlarge rule (Section 3.2) and the fixed-heuristic lazy cycle generation in Algorithm 1 (Section 5.2). The RRlarge proof checks out. The rest is a sensible assembly of known techniques: penalty graph/FAS equivalence, SCC splitting, interval partitioning, sifting, ILP row generation, branch and bound. That is not a criticism; for a competition solver paper, clear engineering plus a clean evaluation is the right contribution.\n\nWhat should count in the paper's favor: the official rankings are independent (4th heuristic, 8th exact, 4th parameterized; 1st student in all three), the authors re-evaluate the top five heuristic solvers on all 200 instances on their own hardware, and the parameterized track result (all instances, 28.54s) is strong. Figures 6 and 7 give useful data on how often reductions help. The discussion of the overly cautious time limits is honest.\n\nThe soft spots are real but narrow. The SMAC3 tuning in Section 8.2 was done on 10 public instances selected using the public leaderboard, and the same public instances are inside the aggregate score in Table 1. There is no held-out test set and no variance reporting for the randomized heuristic. So the specific claim that the tuned parameters are worth 6e-5 points should be read as evidence of tuning gain on those instances, not a demonstrated generalization result. That said, the official PACE score itself is on private instances, and the ranking does not depend on the ablation. The stress-test worry is valid but does not overturn the paper's central claim.\n\nThe citation pattern is fine, and the paper does not oversell; Section 8.4 even admits uncertainty about the cutwidth connection. Missing code and data is a practical limitation, not a correctness issue.\n\nWho is this for? Anyone implementing OCM/FAS solvers, and readers interested in what makes PACE submissions competitive. It deserves a serious referee — an experimental algorithms or graph drawing venue would be appropriate — with the request that the authors release code and data and clarify the tuning/test boundary. I would not desk reject it.","headline":"Solid PACE solver report: sound small algorithmic novelties and independent official results; the only real risk is tuning on public instances, which peer review can fix by asking for code and a cleaner test split.","tokens_in":12954,"tokens_out":2126,"would_cite":false,"duration_ms":19696,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that One-Sided Crossing Minimization is practically solvable by combining graph splitting and reduction rules with a weighted Feedback Arc Set exact core, a claim backed by near-perfect heuristic and all-instance…","keywords":["One-Sided Crossing Minimization","OCM","weighted Feedback Arc Set","penalty graph","data reduction rules","local search","integer linear programming","parameterized algorithms competition"],"falsifier":"Tune the two force-swapping parameters on only half of the public instances and evaluate on the held-out half; if the tuned parameters do not beat the initially guessed parameters on the held-out half, the reported $6\\times10^{-5}$-point gain is tuning-specific rather than a general improvement.","tokens_in":11844,"feed_emoji":"📐","tokens_out":10001,"duration_ms":86777,"temperature":0.7,"pith_summary":"The paper presents Arcee, a solver for One-Sided Crossing Minimization (OCM): given a bipartite graph with one side's order fixed, reorder the other side so that straight-line edges cross as little as possible. It argues that a practical solver can be built by combining splitting and reduction rules with two complementary engines—local search with escape moves for the heuristic track, and a weighted Feedback Arc Set formulation solved by integer linear programming with lazy cycle generation or by branch and bound for the exact and parameterized tracks. The claimed payoff is concrete: in the 2024 competition, the solver placed fourth in the heuristic track (first among student entries) with 199.9998 of 200 possible points, eighth in the exact track solving 152 of 200 instances, and fourth in the parameterized track solving all instances in 28.54 seconds total. A sympathetic reader would care because the same solver architecture, with no track-specific tricks beyond one switch, remains competitive across all three regimes.","feed_headline":"Solver scores 199.9998 of 200 in crossing-minimization challenge","feed_subtitle":"Reduction rules and a feedback-arc-set exact core make OCM tractable in all three competition tracks.","key_machinery":"The load-bearing objects are the crossing matrix $M$ with entries $c_{uv}$ and the weighted penalty graph $G_p$ that orients each pair toward the cheaper order with weight $c_{vu} - c_{uv}$. Because an optimal order is a topological sort after an optimal Feedback Arc Set is removed, exact solvers reduce OCM to weighted Feedback Arc Set. Around this core, reduction rules RR1, RR2, the modified RRlarge, and RRLO1 build a partial order and delete vertices whose position is forced; sifting repositions one vertex at a time; force swapping perturbs local minima; and the exact engine alternates a partial ILP (or branching) with lazy addition of shortest cycles contradicting the heuristic order. The key identity is the penalty-graph equivalence: crossing minimization equals weighted feedback arc set in the graph of pair-wise cheaper orientations, which is what makes exact solving feasible on competition instances.","core_discovery":"The paper's central claim is that OCM can be solved competitively in practice by treating it as a weighted Feedback Arc Set problem on a penalty graph and surrounding that core with data reductions. Each pair of free vertices gets a crossing number $c_{uv}$, the penalty graph orients the cheaper direction and weights it by the savings, and an optimal OCM order is a topological order of this graph after an optimal feedback arc set is removed. The solver's reductions (RR1, RR2, a lower-bound-augmented RRlarge, and RRLO1) fix many vertices before search, and its heuristic combines the median and barycenter starts with sifting plus a distance-increasing force swap to escape local minima. The exact solver lazily generates only the cycles needed to verify the heuristic solution, which the paper reports as faster and more stable than a transitive-constraint linear-ordering ILP. The paper's evidence is the competition record: near-perfect heuristic score, 152 exact instances solved, and all parameterized instances solved quickly.","pith_inferences":["Because the same public instances used for hyperparameter tuning also appear in the reported evaluation, the final $6\\times10^{-5}$-point gain is the result most exposed to overfitting; a clean test would tune on one half of the public set and score on the other half.","The parameterized track's easy splitting may partly reflect low cutwidth, and the paper leaves open whether cutwidth bounds the strongly connected component size of the penalty graph; if so, a cutwidth-aware preprocessing could tighten the large-graph threshold beyond the current 10,000 free vertices.","The exact solver's idea of verifying a heuristic solution through lazily generated shortest cycles could transfer directly to minimum feedback arc set benchmarks outside OCM, since it treats the heuristic only as a certificate to check."],"forward_implications":["Graph splitting on strongly connected components of the penalty graph plus interval partitioning reduces most parameterized instances to components with fewer than ten vertices, making all 200 solvable.","On 27 of the 100 public heuristic instances, data reduction alone fixes the entire order; applying reduction rules before local search is worth roughly $69\\times10^{-5}$ points under the competition scoring.","Force swapping with distance-increasing swaps adds measurable improvement over repeated random sifting: removing it costs $29\\times10^{-5}$ points, guessed parameters recover $23\\times10^{-5}$, and tuned parameters add the final $6\\times10^{-5}$.","The cycle-based ILP with lazy generation solves seven more instances than the linear-ordering ILP and avoids numerical instability seen on sub-100-node graphs.","Substituting an open-source ILP solver for a commercial one costs only six solved instances, so the exact approach does not depend on a commercial solver."],"supporting_citations":[{"why":"Supplies the reduction rules RR1, RR2, RRlarge, and RRLO1 that the solver runs before any search method.","marker":"[9]"},{"why":"Establishes the penalty-graph view that equates OCM with weighted Feedback Arc Set, the foundation of the exact solver.","marker":"[25]"},{"why":"Defines the median heuristic and the NP-hardness background; the median gives the initial heuristic order.","marker":"[10]"},{"why":"Introduces sifting, the one-vertex-at-a-time local search move the heuristic solver iterates.","marker":"[22]"},{"why":"Provides the lazy cycle-generation method that Algorithm 1 adapts to verify a heuristic Feedback Arc Set solution.","marker":"[1]"},{"why":"Supplies the linear-ordering ILP formulation used as one exact-solver baseline.","marker":"[11]"},{"why":"Supplies the cycle-cover ILP formulation underlying the cycle-based exact solver.","marker":"[21]"},{"why":"Supplies the hyperparameter optimizer used to tune the force-swapping parameters reported in the experiments.","marker":"[17]"},{"why":"Supplies the segment-tree crossing-count algorithm used for large instances in the heuristic solver.","marker":"[27]"}],"fun_headline_variants":["Solver hits 199.9998 in PACE crossing-minimization","OCM solver: near-perfect heuristic, exact FAS core","Reduction rules and FAS make OCM near-perfect in PACE","Exact OCM via feedback arc set, heuristic near-perfect"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reported scores assume the 100 public instances used during development represent the 100 withheld private instances well enough that the force-swapping parameters tuned on a subset of the public set improve held-out results rather than just the tuning cases.","fun_headline_variants_meta":{"raw":{"variants":["Solver hits 199.9998 in PACE crossing-minimization","OCM solver: near-perfect heuristic, exact FAS core","Reduction rules and FAS make OCM near-perfect in PACE","Exact OCM via feedback arc set, heuristic near-perfect"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000972,"raw_usage":{"total_tokens":4075,"prompt_tokens":829,"completion_tokens":3246,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":445,"completion_tokens_details":{"reasoning_tokens":3169}},"tokens_in":445,"tokens_out":3246,"duration_ms":32532,"temperature":1.0,"reasoning_tokens":3169,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:57:04.804954+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Tune the two force-swapping parameters on only half of the public instances and evaluate on the held-out half; if the tuned parameters do not beat the initially guessed parameters on the held-out half, the reported $6\\times10^{-5}$-point gain is tuning-specific rather than a general improvement.","supporting_citations":[{"cited_title":"Edge crossings in dr aw- ings of bipartite graphs","cited_arxiv_id":null,"evidence_quote":"Defines the median heuristic and the NP-hardness background; the median gives the initial heuristic order."},{"cited_title":"Topics in computer-aided design: P art i","cited_arxiv_id":null,"evidence_quote":"Supplies the cycle-cover ILP formulation underlying the cycle-based exact solver."},{"cited_title":"Smac3: A versatile bayesian optimization package for hyperparameter optimiz a- tion","cited_arxiv_id":null,"evidence_quote":"Supplies the hyperparameter optimizer used to tune the force-swapping parameters reported in the experiments."},{"cited_title":"W addle and Ashok Malhotra","cited_arxiv_id":null,"evidence_quote":"Supplies the segment-tree crossing-count algorithm used for large instances in the heuristic solver."}],"review_version":1}