{"id":"cdf665af-e029-46b4-aaae-43e91337cd97","arxiv_id":"2607.18569","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The winner of the unbiased triangle game can be decided in O(n^7) time on general graphs, O(n^{ω+1}) on connected K4-containing graphs, and O(n^3) when the edge-triangle incidence graph is a cactus.","lead":"This paper gives faster algorithms for deciding who wins the unbiased Maker-Breaker triangle game, where Maker tries to claim all three edges of a triangle and Breaker tries to stop him. It improves the general worst-case time from O(n^16) to O(n^7), gives near-linear special cases, and links the problem's difficulty to triangle detection.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"General O(n^7) algorithm rests entirely on the unproved translation of Kutz's rank-3 characterization in Theorem 4.4; a mismatch there invalidates Corollary 4.14 and the K4/cactus special cases.","rationale":"I agree with the Reader's weakest_assumption: the decisive step is Theorem 4.4. I traced the dependency: Corollary 4.14 -> Theorem 4.12 -> Corollary 4.10 -> Theorem 4.8 -> Theorem 4.4 -> Kutz [20, Thm 38]. The paper gives full correctness proofs for the Ladder algorithm and for the decomposition logic once Theorem 4.4 is granted, but the theorem itself is quoted as a translation without proof. This is not a disagreement with the field's consensus; it is a correctness risk because the theorem is used as a black-box certificate for Breaker's win. I found no internal contradiction in the statement, so I would not recommend REJECT: the right response is to keep the CONDITIONAL verdict and demand the independent check. If the re-derivation succeeds, the main algorithms are plausible and the complexity improvement is a real contribution; if it fails, the central claim must be weakened or the missing hypotheses stated. The special-case algorithms would also be affected, though the lower-bound reduction in Theorem 4.23 is independent of the disputed characterization.","tokens_in":38868,"tokens_out":18295,"duration_ms":190845,"concrete_test":"Independently re-derive Theorem 4.4 from Kutz's [20, Theorem 38] without reusing the paper's incidence-graph formulation: translate the original hypergraph statement to I(H) and check that conditions (1)–(4) are logically equivalent under the stated hypotheses, especially the ladder predicate in condition (4) and the treatment of open docks with one vertex removed in G. If the derivation requires an extra assumption not listed in Theorem 4.4—for instance a bound on the number of closed docks per shore or a restriction on alpha/beta degrees—then Corollary 4.10 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 4.14's O(n+m^3+m^2 t) bound is obtained by applying Theorem 4.12 to H(G). Theorem 4.12 in turn delegates the rank-3 decision problem to Corollary 4.10, which splits I(H) into 2-connected components and invokes Theorem 4.4 to recognize Breaker's win. Theorem 4.4 is not proved in the paper: §4.1 states only that it is 'obtained by interpreting [20, Theorem 38]' through the incidence graph. The conditions (1)–(4) are intricate—dock shores, open/closed docks, three-path components, and ladders with optional paths—and the proof of Theorem 4.5 verifies only that the algorithm checks these conditions, not that the conditions are equivalent to Breaker's win. If Kutz's original theorem carries a hypothesis that is lost in the incidence-graph translation (for example, a condition on when an open dock may have both vertices present, or on the height of ladders when the optional path is absent), then Theorem 4.8's split can certify Breaker's win on a component where Maker actually wins. Every special-case algorithm in §4.2–§4.3 also calls this subroutine, so the central complexity improvement would collapse. This is a load-bearing external dependency, not a cosmetic gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the unbiased Maker-Breaker triangle game on the edge set of a general graph G. It proposes viewing the game through the edge-triangle incidence graph ET(G) and claims three algorithmic results: (i) a general algorithm deciding the winner in O(n + m^3 + m^2 t) = O(n^7), improving the previous O(n^16) bound; (ii) an O(n + min{n^{ω+1}, m^2}) algorithm when G contains K4 and ET(G) is connected; and (iii) an O(n + m^{1.5}) algorithm when ET(G) is a cactus graph. It also gives a linear-time reduction from triangle detection to deciding the triangle game, and two extremal results: roughly n^2/4 edges force Maker's win (tight), and every minimal Maker win has at least 2n−1 edges (tight). The technical core is a structural characterization of Breaker's win in linear almost-3-uniform hypergraphs, translated from Kutz's thesis, and its application to triangle hypergraphs.","tokens_in":39240,"tokens_out":22555,"duration_ms":222418,"significance":"If the results are correct, the paper makes a substantial contribution: it reduces the polynomial-time bound for a natural Maker-Breaker game from O(n^16) to O(n^7), introduces the edge-triangle incidence graph as a useful algorithmic lens, provides a fine-grained lower bound via triangle detection, and gives tight extremal edge bounds with explicit extremal graphs. The claimed running times are concrete and the paper includes several novel structural characterizations (monotonicity of optimal winning strategies, the K4-based characterization, and the cactus/tadpole-fork characterization). However, the correctness of the central algorithms currently rests on two load-bearing gaps: an unproved translation of an external theorem and an inconsistent deletion convention that makes a key lemma false as stated. These issues must be resolved before the paper can be accepted.","major_comments":[{"comment":"Under the stated definition of H+U in Section 2, H+U keeps hyperedges that survive as singletons. Corollary 4.7 is therefore false: deleting two degree-1 vertices from a 3-edge {v1,v2,v3} creates a 1-edge {v3}, which is an immediate Maker win. Concrete counterexample: the hypergraph H with edges {v1,v2,v3} and {v3,a} is Breaker-win, but H+{v1,v2} contains the 1-edge {v3} and is Maker-win. The proof's decomposition H = H1 ∪ H2 is invalid because H1 = H−{v1,v2} contains the shrunk edge {v3}, not the original hyperedge e. Since Corollary 4.7 is used in the proofs of Theorem 4.8 and Theorem 5.3, and indirectly in Corollary 4.10 and the main algorithms, this is load-bearing. The authors should either adopt the game-residual deletion (remove every hyperedge that intersects the deleted vertex set) and re-check all statements using H+U, or supply a correct argument under the stated convention.","section":"§2; Corollary 4.7"},{"comment":"Theorem 4.4, the central structural characterization, is not proved. The sentence 'The following theorem is obtained by interpreting Kutz' characterization of Breaker's win [20, Theorem 38] through the lens of the vertex-hyperedge incidence graph' is not a substitute for a proof. Theorem 4.5 verifies only that conditions (1)–(4) can be checked in linear time; it does not prove that those conditions are equivalent to Breaker's win. Corollary 4.10 applies this characterization to 2-connected components, and Theorem 4.12, Corollary 4.14, Theorem 4.19, and Theorem 4.22 all inherit the dependency. A missing or mistranslated hypothesis — for example on open docks or on ladder height when the optional path is absent — would invalidate the central O(n^7) claim. Please include a full proof of Theorem 4.4, or restate Kutz's original theorem exactly and prove the translation lemma by lemma.","section":"§4.1, Theorem 4.4"},{"comment":"The proof of Theorem 4.12 uses Lemma 4.11, quoted from [20, Lemma 24], to reduce the 3-uniform case to the almost-3-uniform case. Lemma 4.11 is not proved in the paper, and its hypotheses are not stated precisely enough to verify the enumeration over all pairs (v,w). Since this enumeration is the source of the |V|^2 factor in the claimed O(|V|^3 + |V|^2|E|) bound, the theorem is conditional as written. Please either prove Lemma 4.11 or give a complete statement, including all hypotheses, and a proof or exact reference.","section":"§4.1, Theorem 4.12"},{"comment":"The correctness proof of the cactus-graph algorithm is too terse. The text asserts that after pruning, a cycle attached to the rest of the graph by an edge-vertex 'also lies on a tadpole-fork', and that the reverse BFS order processes each cycle with at most one degree-3 vertex, but it does not rigorously prove that Step 9 detects a tadpole-fork exactly. Since Theorem 4.22 is one of the three main algorithmic results, please expand the correctness proof, ideally by stating and proving an explicit lemma that links the algorithm's local conditions to the existence of a tadpole-fork in ET(G).","section":"§4.3, Theorem 4.22"}],"minor_comments":[{"comment":"The abstract states the general running time as O(n + m^{3.5}), while the main text and Figure 1 give O(n + m^3 + m^2 t). Please make these consistent; the tighter bound is the one that should appear.","section":"Abstract"},{"comment":"Typo: 'contraindication' should be 'contradiction'.","section":"§3"},{"comment":"In the proof of Theorem 5.3, the equality n = |V(G')| = ℓ+2 depends on each newly added triangle sharing an edge with the previous union; please state this explicitly, since a triangle sharing only a vertex would not give the same count.","section":"§5.3"},{"comment":"In the proof, condition (4) is introduced as a separate condition and used before condition (3) is proved, but it is not part of the theorem statement. Please either fold it into the statement or clarify the logical structure.","section":"§4.2, Theorem 4.17"},{"comment":"There are minor notational inconsistencies, e.g., the spelling 'bijection' and the use of 'B' for both a strategy and a set. A careful copyedit would improve readability.","section":"Several places"}],"recommendation":"major_revision","confidential_remarks":"The two main issues — the unproved translation of Kutz's theorem and the false-as-stated Corollary 4.7 caused by the deletion convention — are serious but appear fixable within the manuscript's scope. If the authors can supply a full proof of Theorem 4.4 and correct the H+U convention (or consistently adopt the game-residual deletion), the paper would make a strong contribution. I therefore recommend major revision rather than rejection; however, the current version is not acceptable as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is genuinely useful. It gives an O(n^7) algorithm for the unbiased triangle game, a real improvement over the previous O(n^16), plus faster special cases for K4-containing graphs and cactus incidence graphs, and a linear reduction from triangle detection. The incidence-graph viewpoint and the monotonicity theorem are nice and seem to be new. The proofs are detailed and mostly self-contained.\n\nThe main vulnerability is Theorem 4.4, the characterization of Breaker's win on almost 3-uniform linear hypergraphs. Everything downstream—Corollary 4.14, the K4/cactus algorithms—hangs on it, but it is not proved in the paper. The authors say it is 'obtained by interpreting' a theorem from Kutz's PhD thesis, which is a legitimate citation in principle, but the translation is intricate and it is not even stated as a lemma with a correspondence to Kutz's conditions. A reader can't verify it without pulling the 2004 thesis. That is a load-bearing gap, and the stress-test is right to flag it.\n\nThe count in the proof of Theorem 5.3 initially looks off (n = ℓ+2 vs. a vertex-counting reading), but if triangles are treated as edge sets, the numbers work. A clarification would help. Also, the lower-bound discussion says the game can't be decided in o(n^ω) based on the triangle-detection reduction, but the reduction from a graph with n vertices produces a board with O(n^2) vertices, so the real lower bound is roughly n^{ω/2} in the board size. That's a weaker statement and should be phrased as such.\n\nOverall, the paper deserves a serious referee. The referee's main job will be to verify the Kutz translation, and the authors should be asked to include a proof or at least a precise correspondence. If that theorem is faithful, the paper is a strong, useful contribution. If not, the special cases and the reduction still stand. I'd send it to review and require the Kutz issue to be addressed before acceptance.","headline":"Strong algorithmic improvements for the Maker–Breaker triangle game, but the central theorem is an unproved translation from Kutz's thesis, so a referee needs to check that translation carefully.","tokens_in":39654,"tokens_out":6410,"would_cite":true,"duration_ms":71771,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C57","05C65","05C85","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The winner of the unbiased Maker-Breaker triangle game on any graph can be decided in O(n^7) time, down from O(n^16), by reading the game through its edge-triangle incidence graph.","keywords":["Maker-Breaker games","triangle game","positional games","edge-triangle incidence graph","linear hypergraphs","game complexity","K4-free graphs","cactus graphs"],"falsifier":"Exhaustively compare the paper's conditions against brute-force game search on all small linear almost-3-uniform hypergraphs (or small graphs whose edge-triangle incidence graph is a cactus): the first instance whose conditions declare Breaker the winner while Maker has a winning strategy falsifies the base theorem and every algorithm built on it.","tokens_in":38808,"feed_emoji":"🔺","tokens_out":8116,"duration_ms":80985,"temperature":0.7,"pith_summary":"The paper shows that the winner of the unbiased Maker-Breaker triangle game — in which Maker alternately claims edges of a graph and wins by completing a triangle, while Breaker blocks — can be determined substantially faster than previously known. Its central move is to replace the standard hypergraph model with the edge-triangle incidence graph, whose connected components encode all threats. The paper proves that in this model Maker wins exactly when he can force two of his claimed edges into the same connected component after Breaker's moves, and that fastest winning strategies can be assumed to play monotonically. From this it derives an O(n+m^3+m^2 t)=O(n^7) general algorithm, plus an O(n^{ω+1}) algorithm for graphs containing K4 (the complete graph on four vertices) with connected incidence graph, and an O(n^3) algorithm when the incidence graph is a cactus graph (all cycles edge-disjoint). It also gives a linear-time reduction from triangle detection, showing the game is at least as hard as finding a triangle.","feed_headline":"Unbiased triangle-game winner decidable in O(n^7) time","feed_subtitle":"A switch to the edge-triangle incidence graph cuts the previous O(n^16) bound and ties the game to triangle detection.","key_machinery":"The edge-triangle incidence graph ET(G): the bipartite graph with one vertex for each edge of G, one vertex for each triangle of G, and an edge between an edge-vertex and a triangle-vertex when that edge belongs to that triangle. It is the paper's central object: connected components of ET(G) after Breaker's moves are the arenas in which Maker's winning condition (WC) lives, and monotonicity of fastest winning strategies lets the algorithms examine only decreasing connected subgraphs. The other load-bearing piece is a structural characterization of Breaker's win on linear almost-3-uniform hypergraphs, translated into four graph conditions involving docks, shores, and ladders; the paper imple","core_discovery":"On the paper's own terms, the central discovery is that the unbiased triangle game is governed by the edge-triangle incidence graph ET(G) rather than by the triangle hypergraph. Maker's winning condition (WC) is this: at some point after Breaker has claimed a set of edges, Maker has claimed two edge-vertices lying in the same connected component of ET(G) minus the closed neighborhood of Breaker's claimed edges. The paper shows that fastest winning strategies can be assumed monotone and that, until winning, every Maker move lies on a cycle in the remaining incidence graph. Building on a characterization of Breaker's win on linear almost-3-uniform hypergraphs, it converts these structural fact","pith_inferences":["If the triangle-detection lower bound is tight, the general algorithm is still far from optimal; the K4 and cactus special cases suggest O(n^3) is a plausible target for all K4-free graphs.","The monotonicity theorem is stated for the triangle game, but the proof mainly uses linearity of the induced hypergraph, so the same incidence-graph technique may yield faster algorithms for other Maker-Breaker games on fixed subgraphs with at most three edges.","The linear-time reduction from triangle detection transfers fine-grained lower bounds: any subcubic algorithm for the game would imply a subcubic triangle-detection algorithm, making the game a natural candidate for fine-grained complexity classification.","The extremal threshold (1/4+ε)n^2 for Maker's win is stated for raw edge counts; the paper itself notes the bipartite extremal example is artificial, and the open problem it poses — a threshold in triangle-to-edge ratio after removing reducible edges — is a testable route to a sharper bound."],"forward_implications":["For any input graph, the winner can now be decided in O(n+m^3+m^2 t) ≤ O(n^7), a large improvement over the previous O(n^16) bound.","If G contains K4 and ET(G) is connected, the winner can be decided in O(n+min{n^{ω+1},m^2}) time, where ω < 2.372 is the exponent of matrix multiplication; if a K4 witness is given, the bound improves to O(n+m^{1.5}).","If ET(G) is a cactus graph, the winner is decided in O(n+m^{1.5}) = O(n^3), and Maker wins exactly when ET(G) contains a tadpole-fork.","Deciding the triangle game is at least as hard as triangle detection: any graph can be transformed in linear time into a board graph that is Maker's win exactly when the original graph contains a triangle.","Asymptotically, any graph with at least (1/4+ε)n^2 edges is Maker's win, and this is tight; minimal Maker-win graphs need at least 2n−1 edges, and this is tight for every n≥5."],"fun_headline_variants":["Edge-triangle incidence speeds triangle-game decision to O(n^7)","From O(n^16) to O(n^7): unbiased triangle game decided faster","Maker-Breaker triangle game solved via edge-triangle incidence","Triangle game winner found in O(n^7) with new graph model"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that the characterization of Breaker's win on linear almost-3-uniform hypergraphs borrowed from earlier work is correct and complete; the paper cites it without proof, and if it has hidden hypotheses the general O(n^7) algorithm and both special-case algorithms collapse.","fun_headline_variants_meta":{"raw":{"variants":["Edge-triangle incidence speeds triangle-game decision to O(n^7)","From O(n^16) to O(n^7): unbiased triangle game decided faster","Maker-Breaker triangle game solved via edge-triangle incidence","Triangle game winner found in O(n^7) with new graph model"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000346,"raw_usage":{"total_tokens":1809,"prompt_tokens":899,"completion_tokens":910,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":831}},"tokens_in":643,"tokens_out":910,"duration_ms":10038,"temperature":1.0,"reasoning_tokens":831,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T15:02:25.854793+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhaustively compare the paper's conditions against brute-force game search on all small linear almost-3-uniform hypergraphs (or small graphs whose edge-triangle incidence graph is a cactus): the first instance whose conditions declare Breaker the winner while Maker has a winning strategy falsifies the base theorem and every algorithm built on it.","supporting_citations":[],"review_version":1}