Pith. sign in

REVIEW 4 major objections 5 minor 26 references

Faster Algorithms for Deciding the Unbiased Maker-Breaker Triangle Game on General Graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2607.18569 v1 pith:YCQGSN7K submitted 2026-07-20 cs.CC

Julian Christoph Brinkmann , Anand Srivastav This is my paper · ORCID
classification cs.CC MSC 05C5705C6505C8568Q25
keywords Maker-Breakergamestrianglegamepositionaledge-triangleincidencegraphlinearhypergraphscomplexityK4-freegraphscactus
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [§2; Corollary 4.7] 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.
  2. [§4.1, Theorem 4.4] 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.
  3. [§4.1, Theorem 4.12] 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.
  4. [§4.3, Theorem 4.22] 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).
minor comments (5)
  1. [Abstract] 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.
  2. [§3] Typo: 'contraindication' should be 'contradiction'.
  3. [§5.3] 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.
  4. [§4.2, Theorem 4.17] 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.
  5. [Several places] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithms are deductive consequences of explicit lemmas, and the Kutz rank-3 characterization is used as an external black box, not a self-citation.

full rationale

The derivation chain is self-contained apart from explicitly cited external results. Lemma 3.1 proves an iff characterization of Breaker's win in terms of connected components of the edge-triangle incidence graph; Theorems 3.4, 3.7 and 3.8 give original proofs of monotonicity and cycle properties. Section 4 then applies Kutz's characterization: Theorem 4.4 is explicitly stated as 'obtained by interpreting Kutz' characterization of Breaker's win [20, Theorem 38]', with Kutz's thesis being an external source, not the authors' own work. Theorem 4.8 is proved in the paper by induction, and Corollary 4.10 and Theorem 4.12 are direct algorithmic consequences. The general O(n+m^3+m^2 t) bound is obtained by composing these results with Lemma 4.13, which gives an O(n+m^1.5) construction of the game hypergraph. The K4 and cactus special cases rest on Theorems 4.17 and 4.21, both of which are proved from Lemma 3.1 and other stated lemmas, not assumed. No parameter is fitted to data, and no 'prediction' is a renamed input. The only self-citation is [14] (Glazik–Srivastav), which appears in a survey sentence about the biased triangle game and is not used in any proof or as a load-bearing premise. The paper's reliance on the unproved faithful translation of Kutz's theorem is a correctness risk, but not circularity: the cited result is independent external work with stated assumptions, and the present paper does not derive the target result from itself.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted; the paper is a purely mathematical/algorithms contribution. The main unverified input is Kutz's theorem and a few standard algorithmic building blocks.

assumptions (4)
  • domain assumption Kutz's characterization of Breaker's win on linear almost 3-uniform hypergraphs (Theorem 4.4) is correct and faithfully translated
    Used as the core subroutine in Corollary 4.10 and Theorem 4.12 for general graphs; no proof is given in the paper.
  • domain assumption Acyclic rank-3 hypergraphs are Breaker's win [13, Theorem 3.21]
    Used in Theorem 4.8 and Corollary 4.10 to classify hypergraphs without 2-connected components.
  • standard math Standard algorithmic results: ω<2.372, K4 detection in O(n^{ω+1}) [7], clique enumeration in O(m^2) [10], linear-time 2-connected components [17], triangle listing in O(m^{1.5}) [10]
    Used to obtain the running-time bounds; these are prior algorithmic results.
  • standard math Erdős–Stone theorem
    Used in Theorem 5.2 to turn the 3-colorable Maker-win gadget into an edge-threshold for all large graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Faster Algorithms for Deciding the Unbiased Maker-Breaker Triangle Game on General Graphs." pith.science (2026). https://pith.science/paper/YCQGSN7K

@misc{pith2026260718569,
  author       = {Pith},
  title        = {Pith review of: Faster Algorithms for Deciding the Unbiased Maker-Breaker Triangle Game on General Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YCQGSN7K}},
  note         = {Machine review of arXiv:2607.18569}
}
abstract

In this paper, we present new polynomial-time algorithms for determining the winner of the unbiased triangle game played on the edge set of general graphs. To that end, we propose to view the game through the edge-triangle incidence graph instead of the standard hypergraph model. We identify a necessary and sufficient winning condition for Maker in terms of the edge-triangle incidence graph and show that winning strategies achieving this condition as fast as possible play monotonically in the sense that they only consider monotonically decreasing connected subgraphs of the edge-triangle incidence graph. We give three different algorithms for different classes of graphs. For general graphs $G$, the outcome of the unbiased triangle game can be decided in time $\mathcal{O}(n+m^{3.5})=\mathcal{O}(n^7)$. This significantly improves on the $\mathcal{O}(n^{16})$ algorithm implied by the work of Galliot, Gravier and Sivignon (arXiv 2022). For graphs $G$ which contain $K_4$, the complete graph on four vertices, as a subgraph and whose edge-triangle incidence graph is connected, the winner can be decided in time $\mathcal{O}(n+\min\{n^{\omega+1},m^2\})=\mathcal{O}(n^{\omega+1})$, where $\omega<2.372$ is the exponent of matrix multiplication (Alman et. al., SODA 2025). For graphs $G$ whose edge-triangle incidence graph is a cactus graph, i.e. all its cycles are edge-disjoint, the winner can be decided in time $\mathcal{O}(n+m^{1.5})=\mathcal{O}(n^3)$. Such $G$ are $K_4$-free. The algorithms for the special cases are based on novel structural characterizations of Maker's win for each graph class. We also give a linear time reduction from triangle detection to deciding the unbiased triangle game.

Figures

Figures reproduced from arXiv: 2607.18569 by the authors.

Figure 1
Figure 1. Overview of algorithms for the unbiased triangle game on different graph classes. The author of [20] does not provide a concrete running time, arguing only that is polynomial. Membership in this family of maximal winning graphs can be checked in linear time given the board graph 𝐺 resulting in a linear time algorithm for the 𝑃4-game. They also show that the 𝐾1,ℓ-game is fixed-parameter tractable when parameterized b… view at source ↗
Figure 2
Figure 2. The graph 𝐾4 (left) and its edge-triangle incidence graph (right). In the edge-triangle incidence graph, circular vertices correspond to edges of 𝐾4 and triangular vertices correspond to triangles in 𝐾4. The vertex label indicates the vertices involved in the edge or triangle. Our definition of the unbiased triangle game is slightly different from the standard definition in the literature: Usually, Maker and Breaker… view at source ↗
Figure 3
Figure 3. A path of length 7 on which Maker has claimed two edge-vertices (dashed) and the resulting edge-vertices that Maker and Breaker claim in the proof of Lemma 3.1. Edge-vertices claimed by Breaker are colored red. Cyan edge-vertices are claimed by Maker. Black edge-vertices are unclaimed. We define the winning condition (WC) as follows: there exist two edges claimed by Maker in the same connected component of ET(𝐺) − 𝑁… view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: An exemplary illustration of 𝜅(𝑒𝑖 , 𝐸𝑖 𝑏 ) in the second case of the proof of Lemma 3.7. This figure does not aim to cover all possibilities, e.g. 𝑎𝑖 could also be the unlabeled edge incident to the same triangle instead. Now assume 𝑖 + 1 < ℓ. Without loss of generalit…
Figure 5
Figure 5. Figure 5: A concrete example of the situation in the proof of Lemma 3.8. Except for 𝑎 ′ 1 , edge-vertices with degree 1 are not drawn. We define the strategy 𝑀′ which satisfies the desired property. The strategy 𝑀′ first picks 𝑒 ∗ 1 . Let 𝑎 ∗ 1 be Breaker’s response. If 𝑎 ∗ 1 ∉ …
Figure 6
Figure 6. Figure 6: The graphs 𝐻1 and 𝐻2 as well as their edge-triangle incidence graphs. The graph 𝐻1 satisfies condition (1) of Theorem 4.17. The three vertices in the same connected component of ET(𝐻1) − 𝑇({1, 2, 3, 4}) are colored red. The graph 𝐻2 satisfies condition (3) of Theorem 4…
Figure 7
Figure 7. Figure 7: The edge-triangle incidence graph ET(𝐾4) during the unbiased triangle game. The edge-vertices are named as in [PITH_FULL_IMAGE:figures/full_fig_p024_7.png]
Figure 8
Figure 8. Figure 8: A tadpole-fork. Edge-vertices with degree 1 are not drawn. Definition 4.20. Let 𝐺 be a graph. A tadpole (𝐶, 𝑃, 𝑒) in ET(𝐺) consists of a cycle 𝐶, a path 𝑃, possibly consisting only of a single vertex, and an edge-vertex 𝑒 ∈ 𝐸(𝐺) such that 𝑁[𝑇(𝐶)] ∩ 𝑁[𝑇(𝑃)] ⊆ {𝑒} and 𝑉(…
Figure 9
Figure 9. Figure 9: The graphs 𝐺1 and 𝐺2, their respective image 𝐻1 and 𝐻2 under the reduction from Theorem 4.23 as well as ET(𝐻1) and ET(𝐻2). The edge-triangle incidence graph ET(𝐻1) is only partially drawn. The dashed vertex represents the remainder of the copy of ET(𝐾4) that uses the e…
Figure 10
Figure 10. Figure 10: A 3-colorable graph that is Maker’s win. If 𝐺 contains a triangle 𝑡, then 𝑡 connects two disjoint copies of ET(𝐾4) in ET(𝐻). Thus, 𝐻 is winning for Maker by condition (2) of Theorem 4.17. If 𝐺 does not contain a triangle, then ET(𝐻) consists of disjoint copies of ET(𝐾…
Figure 11
Figure 11. Figure 11: The graphs 𝐻𝑛 for 5 ≤ 𝑛 ≤ 9. They are minimal Maker wins satisfying 𝑚 = 2𝑛 − 1. For 𝑛 ≥ 7, the graph 𝐻𝑛+1 is obtained from 𝐻𝑛 in the same way 𝐻8 is obtained from 𝐻7 [PITH_FULL_IMAGE:figures/full_fig_p029_11.png]
Figure 12
Figure 12. Figure 12: A minimal Maker win with 7 vertices and 15 edges. Proof. Our proof of the first statement is based on the ideas of the proof of [22, Theorem 1.3]. However, as we are not in a probabilistic setting, we cannot dismiss cases that will not happen asymptotically almost sur…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 7 canonical work pages

  1. [1]

    More Asymmetry Yields Faster Matrix Multiplication

    Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More Asymmetry Yields Faster Matrix Multiplication. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2005–2039. SIAM, 2025.doi:10.1137/1.9781611978322.63

    doi:10.1137/1.9781611978322.63 2025

  2. [2]

    OntheChvátal-ErdösTriangleGame.Electron.J.Comb.,18(1),2011

    JózsefBaloghandWojciechSamotij. OntheChvátal-ErdösTriangleGame.Electron.J.Comb.,18(1),2011. doi:10.37236/559

    work page doi:10.37236/559 2011

  3. [3]

    O(n2.7799) Complexity for n*n Approximate Matrix Multiplication.Inf

    Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti. O(n2.7799) Complexity for n*n Approximate Matrix Multiplication.Inf. Process. Lett., 8(5):234–235, 1979.doi:10.1016/0020-0190(79)90113-3

    doi:10.1016/0020-0190(79)90113-3 1979

  4. [4]

    Seymour, and Robin Thomas

    Maria Chudnovsky, Neil Robertson, Paul D. Seymour, and Robin Thomas. K4-free graphs with no odd holes.J. Comb. Theory B, 100(3):313–331, 2010.doi:10.1016/J.JCTB.2009.10.001. [5]Vašek Chvátal and Paul Erdös. Biased positional games. InAnn. Discrete Math., volume 2, pages 221–229. Elsevier, 1978

    work page doi:10.1016/j.jctb.2009.10.001 2010

  5. [6]

    On the Asymptotic Complexity of Matrix multiplication (Extended Summary)

    Don Coppersmith and Shmuel Winograd. On the Asymptotic Complexity of Matrix multiplication (Extended Summary). In22nd Annual Symposium on Foundations of Computer Science, pages 82–90. IEEE Computer Society, 1981.doi:10.1109/ SFCS.1981.27

    1981

  6. [7]

    TowardsOptimalOutput-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques

    MinaDalirrooyfard,SuryaMathialagan,VirginiaVassilevskaWilliams,andYinzhanXu. TowardsOptimalOutput-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 923–934. ACM, 2024.doi:10.1145/3618260.3649663. [8]Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduat...

    arXiv 2024

  7. [9]

    Complexity of Maker-Breaker games on edge sets of graphs.Discret

    Éric Duchêne, Valentin Gledel, Fionn Mc Inerney, Nicolas Nisse, Nacim Oijid, Aline Parreau, and Milos Stojakovic. Complexity of Maker-Breaker games on edge sets of graphs.Discret. Appl. Math., 361:502–522, 2025.doi:10.1016/J.DAM. 2024.11.012

    doi:10.1016/j.dam 2025

  8. [10]

    On the complexity of fixed parameter clique and dominating set.Theoretical Computer Science, 326(1):57–67, 2004.doi:10.1016/j.tcs.2004.05.009

    Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set.Theoretical Computer Science, 326(1):57–67, 2004.doi:10.1016/j.tcs.2004.05.009

    work page doi:10.1016/j.tcs.2004.05.009 2004

Show all 26 references
  1. [11]

    Selfridge

    Paul Erdös and John L. Selfridge. On a Combinatorial Game.J. Comb. Theory A, 14(3):298–301, 1973.doi:10.1016/ 0097-3165(73)90005-8

    1973

  2. [12]

    4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete.CoRR, abs/2509.13819, 2025

    Florian Galliot. 4-uniform Maker-Breaker and Maker-Maker games are PSPACE-complete.CoRR, abs/2509.13819, 2025. doi:10.48550/ARXIV.2509.13819

    2025 doi arXiv

  3. [13]

    Maker-Breaker is solved in polynomial time on hypergraphs of rank 3.CoRR, abs/2209.12819, 2025.arXiv:2209.12819

    Florian Galliot, Sylvain Gravier, and Isabelle Sivignon. Maker-Breaker is solved in polynomial time on hypergraphs of rank 3.CoRR, abs/2209.12819, 2025.arXiv:2209.12819

    2025 arXiv

  4. [14]

    A new bound for the Maker-Breaker triangle game.Eur

    Christian Glazik and Anand Srivastav. A new bound for the Maker-Breaker triangle game.Eur. J. Comb., 104:103536, 2022. doi:10.1016/J.EJC.2022.103536

    2022

  5. [15]

    On the number of triangles in𝑘4-free graphs.CoRR, abs/2509.12100, 2025

    Jialin He, Jie Ma, Yan Wang, and Chunlei Zu. On the number of triangles in𝑘4-free graphs.CoRR, abs/2509.12100, 2025. arXiv:2509.12100

    2025

  6. [16]

    Birkhäuser Basel, 2014.doi:10.1007/978-3-0348-0825-5

    Dan Hefetz, Michael Krivelevich, Miloš Stojaković, and Tibor Szabó.Positional Games, volume 44 ofOberwolfach Seminars. Birkhäuser Basel, 2014.doi:10.1007/978-3-0348-0825-5

    2014 doi

  7. [17]

    Hopcroft and Robert Endre Tarjan

    John E. Hopcroft and Robert Endre Tarjan. Efficient Algorithms for Graph Manipulation [H] (algorithm 447).Commun. ACM, 16(6):372–378, 1973.doi:10.1145/362248.362272

    1973

  8. [18]

    Finding a Minimum Circuit in a Graph.SIAM J

    Alon Itai and Michael Rodeh. Finding a Minimum Circuit in a Graph.SIAM J. Comput., 7(4):413–423, 1978. doi: 10.1137/0207033

    1978 doi

  9. [19]

    Solving Maker-Breaker Games on 5-uniform hypergraphs is PSPACE-complete.CoRR, abs/2502.20271, 2025.arXiv:2502.20271

    Finn Orson Koepke. Solving Maker-Breaker Games on 5-uniform hypergraphs is PSPACE-complete.CoRR, abs/2502.20271, 2025.arXiv:2502.20271

    2025 arXiv

  10. [20]

    Phd thesis, Freie Universität Berlin, 2004

    Martin Kutz.The Angel Problem, Positional Games, and Digraph Roots. Phd thesis, Freie Universität Berlin, 2004. URL: https://refubium.fu-berlin.de/handle/fub188/9918

    2004

  11. [21]

    Dimitrios Michail, Joris Kinable, Barak Naveh, and John V. Sichi. JGraphT - A Java Library for Graph Data Structures and Algorithms.ACM Trans. Math. Softw., 46(2):16:1–16:29, 2020.doi:10.1145/3381449

    2020 doi

  12. [22]

    AthresholdfortheMaker-Breakercliquegame.RandomStruct.Algorithms,45(2):318–341, 2014.doi:10.1002/RSA.20489

    TobiasMüllerandMilošStojaković. AthresholdfortheMaker-Breakercliquegame.RandomStruct.Algorithms,45(2):318–341, 2014.doi:10.1002/RSA.20489

    2014 doi

  13. [23]

    Victor Y. Pan. Strassen’s Algorithm Is not Optimal: Trililnear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations. In19th Annual Symposium on Foundations of Computer Science, pages 166–176. IEEE Computer Society, 1978.doi:10....

    1978 doi

  14. [24]

    6-UniformMaker-BreakerGameisPSPACE-Complete.Combinatorica,43(3):595–612, 2023.doi:10.1007/S00493-023-00026-7

    MdLutfarRahmanandThomasWatson. 6-UniformMaker-BreakerGameisPSPACE-Complete.Combinatorica,43(3):595–612, 2023.doi:10.1007/S00493-023-00026-7

    2023 doi

  15. [25]

    Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication.SIAM J

    Francesco Romani. Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication.SIAM J. Comput., 11(2):263–267, 1982.doi:10.1137/0211020

    1982 doi

  16. [26]

    Schaefer

    Thomas J. Schaefer. On the Complexity of Some Two-Person Perfect-Information Games.J. Comput. Syst. Sci., 16(2):185–225, 1978.doi:10.1016/0022-0000(78)90045-4

    1978 doi

  17. [27]

    Partial and Total Matrix Multiplication.SIAM J

    Arnold Schönhage. Partial and Total Matrix Multiplication.SIAM J. Comput., 10(3):434–455, 1981.doi:10.1137/0210032. J. C. Brinkmann, A. Srivastav 31 [28]Volker Strassen. Gaussian Elimination is not Optimal.Numer. math, 13:354–356, 1969.doi:10.1007/BF02165411

    1981 doi

  18. [29]

    Multiplying Matrices Faster Than Coppersmith-Winograd

    Virginia Vassilevska Williams. Multiplying Matrices Faster Than Coppersmith-Winograd. InProceedings of the 44th Symposium on Theory of Computing Conference, pages 887–898. ACM, 2012.doi:10.1145/2213977.2214056

    2012

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.