arxiv: 2605.14428 · v1 · submitted 2026-05-14 · 💻 cs.DS · math.CO

Recognition: 3 theorem links

· Lean Theorem

Branch-width of represented matroids in matrix multiplication time

Mujin Choi , Tuukka Korhonen , Sang-il Oum

Authors on Pith no claims yet

Pith reviewed 2026-05-15 02:10 UTC · model grok-4.3

classification 💻 cs.DS math.CO

keywords branch-widthmatroidbranch-decompositionmatrix representationfinite fieldalgorithmmatrix multiplication

0 comments

The pith

A matroid given by an n by n matrix over a finite field has a branch-decomposition of width at most k found in O(n²) time plus one matrix multiplication, or the algorithm reports that branch-width exceeds k.

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

The paper gives an algorithm that accepts an n-element matroid represented by an n by n matrix over a finite field F together with an integer k. It either returns a branch-decomposition of width at most k or correctly states that the branch-width is larger than k. The running time is O_{k,F}(n²) plus the time to multiply two n by n matrices. All earlier algorithms required at least cubic time in n. When the input matrix is already in standard form the matrix-multiplication step disappears and only the quadratic term remains.

Core claim

For an n-element matroid M given by an n × n matrix representation over a finite field F and an integer k, there is an (O_{k,F}(n²) + O(n^ω))-time algorithm that either finds a branch-decomposition of M of width at most k or confirms that the branch-width of M is more than k, where ω < 2.3714 is the matrix-multiplication exponent.

What carries the argument

Branch-decomposition of width k, located by reducing the search to a quadratic number of rank queries and matrix operations over the finite field, with matrix multiplication used only to convert the input to standard form.

If this is right

Rank-width of directed graphs can be computed in the same improved time bound.
Path-width of matroids represented over a fixed finite field can be decided faster than before.
An approximation algorithm for branch-width exists for matrices over infinite fields that are already in standard form and use only a bounded number of distinct entry values.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Any future improvement in the matrix-multiplication exponent immediately yields a faster matroid algorithm without further changes.
The reduction showing that deciding branch-width zero is equivalent to matrix singularity suggests that other linear-algebraic width parameters may inherit similar lower bounds.
The quadratic term may be improvable if a different representation or data structure replaces the current dynamic-programming approach.

Load-bearing premise

The matroid is supplied as an explicit matrix over a known finite field F, and the hidden factors depending on k and F remain computable.

What would settle it

A concrete n by n matrix over some finite field F together with a k for which the algorithm either returns an incorrect decomposition or exceeds the stated time bound would show the claim is false.

Figures

Figures reproduced from arXiv: 2605.14428 by Mujin Choi, Sang-il Oum, Tuukka Korhonen.

**Figure 1.** Figure 1: An example of a general representation and a standard representation representing the same matroid. most 𝑘, if the input matroid is represented over a fixed finite field and is given with its branch-decomposition of width at most 𝑘. 1 We remark that when the matroid is not represented over a finite field, the part (B) above fails [10, Section 8.3]. For the part (A), if we have an oracle for the rank-functi… view at source ↗

read the original abstract

For an $n$-element matroid $M$ given by an $n \times n$ matrix representation over a finite field $\mathbb F$ and an integer $k$, we present an $(O_{k,\mathbb F}(n^2)+O(n^\omega))$-time algorithm that either finds a branch-decomposition of $M$ of width at most $k$, or confirms that the branch-width of $M$ is more than $k$, where $\omega < 2.3714$ is the matrix multiplication exponent, and the $O_{k,\mathbb F}(\cdot)$-notation hides factors that depend on $k$ and $\mathbb F$ in a computable manner. All previous algorithms including Hlin\v{e}n\'y and Oum [SIAM J. Comput. (2008)] and Jeong, Kim, and Oum [SIAM J. Discrete Math. (2021)] run in at least $\Omega(n^3)$ time. Moreover, if the input matrix representation is given by a standard form, our algorithm runs in $O_{k,\mathbb F}(n^2)$-time, since $O(n^\omega)$-time is only needed for finding a standard form of the input matrix. When $M$ is given by an $m \times n$ matrix, the overhead for finding a standard form is $O(mn \min(m,n)^{\omega-2})$. As corollaries, we obtain faster algorithms for rank-width of directed graphs and path-width of matroids represented over a fixed finite field. Furthermore, we also present an approximation algorithm for finding branch-width that works on infinite fields provided that the input matrix is of a standard form and contains a bounded number of distinct values of entries. To suggest that our algorithm is optimal, we observe that for every field $\mathbb F$, deciding whether the branch-width of a matroid represented over $\mathbb F$ is $0$ is as hard as deciding whether a square matrix over $\mathbb F$ is singular. Under the assumption that singularity testing requires $\Omega(n^\omega)$-time, this implies that the overhead of $O(n^{\omega})$ is unavoidable. We also show strengthenings of this observation to rule out some approximations under this assumption.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean O(n² + n^ω) algorithm for exact branch-width on matrix-represented matroids over finite fields, with a matching lower bound from singularity testing.

read the letter

The main result is an algorithm that, for an n-element matroid given by an n×n matrix over a fixed finite field F, decides if branch-width is at most k and outputs a decomposition if so. The runtime is O_{k,F}(n²) plus one matrix-multiplication step, which improves on the cubic-time algorithms from Hliněný-Oum and Jeong-Kim-Oum. When the input is already in standard form the matrix-mult step drops out entirely, leaving pure quadratic time in n for fixed k and F. They also show that deciding branch-width zero is equivalent to testing singularity of the matrix, so the n^ω term is tight under standard assumptions. That lower-bound argument is direct and useful.

Referee Report

0 major / 2 minor

Summary. The paper claims an algorithm for an n-element matroid M given by an n×n matrix representation over a finite field F and integer k that either outputs a branch-decomposition of width ≤k or certifies branch-width >k, running in O_{k,F}(n²) + O(n^ω) time (with ω<2.3714 the matrix-multiplication exponent). When the input is already in standard form the matrix-multiplication term disappears. The work improves on prior Ω(n³) algorithms, derives corollaries for rank-width of directed graphs and path-width of represented matroids, gives an approximation result for infinite fields on standard-form inputs with bounded distinct entries, and proves a matching lower bound by direct reduction from matrix singularity testing over F.

Significance. If correct, the result substantially advances algorithmic matroid theory by separating the quadratic overhead from the unavoidable matrix-multiplication cost and by supplying an explicit, computable dependence on the fixed parameters k and F. The reduction to standard form (O(n^ω) for square matrices, O(mn min(m,n)^{ω-2}) in general) and the direct lower-bound reduction from singularity testing are concrete strengths that establish both an improved upper bound and evidence of tightness under standard assumptions. The corollaries and the approximation extension further increase the scope.

minor comments (2)

[§1] §1 (Introduction): the sentence claiming the O_{k,F}(n²) term hides only computable factors should be accompanied by a brief pointer to the section where the state space of the dynamic program (or search procedure) is bounded in terms of k and |F|.
[Lower-bound section] The lower-bound section: while the reduction from singularity testing to branch-width-0 is described as direct, a short paragraph confirming that the constructed matroid is represented by the input matrix and that width exactly 0 corresponds to linear dependence would eliminate any residual ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and recommendation for minor revision. The referee's summary accurately captures the main results, including the O_{k,F}(n^2) + O(n^ω) runtime, the reduction to standard form, the corollaries for rank-width and path-width, the approximation result for infinite fields, and the matching lower bound from matrix singularity testing. Since no major comments are listed in the report, we have no specific points requiring rebuttal or revision.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives an FPT algorithm for branch-width of matrix-represented matroids by reducing the input to standard form (via matrix multiplication in O(n^ω) time) followed by an explicit quadratic-time dynamic-programming procedure whose k- and F-dependent factors are computable and independent of n. The claimed optimality rests on a direct reduction showing that branch-width-0 decision is equivalent to matrix singularity testing, which is a standard external hardness assumption rather than a self-referential fit or definition. Prior self-citations (Hliněný-Oum 2008, Jeong-Kim-Oum 2021) supply only slower baseline algorithms and are not invoked to justify uniqueness or to close any derivation loop; the new runtime bound is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard theory of linear representations of matroids over finite fields and the known complexity of matrix multiplication; no free parameters or new entities are introduced.

axioms (2)

domain assumption Matroids given by matrices over finite fields admit branch-decompositions whose width can be decided via algebraic techniques
Core modeling assumption that makes the input representation and the algorithm applicable.
standard math Matrix multiplication over finite fields can be performed in O(n^ω) time for ω < 2.3714
Used directly in the stated time bound.

pith-pipeline@v0.9.0 · 5730 in / 1491 out tokens · 74361 ms · 2026-05-15T02:10:41.184580+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

2005–2039

Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou, More asymmetry yields faster matrix multiplication , Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2025, pp. 2005–2039. MR 4863478

work page 2025
[2]

Bodlaender and Ton Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J

Hans L. Bodlaender and Ton Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms 21 (1996), no. 2, 358–402. MR 98g:68122 27

work page 1996
[3]

Bunch and John E

James R. Bunch and John E. Hopcroft, Triangular factorization and inversion by fast matrix multiplication, Math. Comp. 28 (1974), 231–236. MR 331751

work page 1974
[4]

and Comput

Bruno Courcelle, The monadic second-order logic of graphs I: Recognizable sets of ﬁnite graphs , Inform. and Comput. 85 (1990), no. 1, 12–75. MR 91g:05107

work page 1990
[5]

138, Cambridge University Press, Cam- bridge, 2012

Bruno Courcelle and Joost Engelfriet, Graph structure and monadic second-order logic , Ency- clopedia of Mathematics and its Applications, vol. 138, Cambridge University Press, Cam- bridge, 2012. MR 2962260

work page 2012
[6]

Dharmatilake, Binary matroids of branch-width 3, Ph.D

Jack S. Dharmatilake, Binary matroids of branch-width 3, Ph.D. thesis, Ohio State University, 1994

work page 1994
[7]

Fomin and Tuukka Korhonen, F ast FPT-Approximation of Branchwidth, SIAM J

Fedor V. Fomin and Tuukka Korhonen, F ast FPT-Approximation of Branchwidth, SIAM J. Comput. 53 (2024), no. 4, 1085–1131. MR 4783063

work page 2024
[8]

Hicks and Nolan B

Illya V. Hicks and Nolan B. McMurray Jr., The branchwidth of graphs and their cycle matroids , J. Combin. Theory Ser. B 97 (2007), no. 5, 681–692

work page 2007
[9]

Petr Hliněný, A parametrized algorithm for matroid branch-width, SIAM J. Comput. 35 (2005), no. 2, 259–277, loose erratum (electronic). MR 2191443

work page 2005
[10]

, Branch-width, parse trees, and monadic second-order logic for matroids , J. Combin. The- ory Ser. B 96 (2006), no. 3, 325–351. MR 2220663 (2007a:68050)

work page 2006
[11]

Petr Hliněný and Sang-il Oum, Finding branch-decompositions and rank-decompositions, SIAM J. Comput. 38 (2008), no. 3, 1012–1032. MR 2421076

work page 2008
[12]

Petr Hliněný and Geoﬀ Whittle, Matroid tree-width, European J. Combin. 27 (2006), no. 7, 1117–1128

work page 2006
[13]

Ibarra, Shlomo Moran, and Roger Hui, A generalization of the fast LUP matrix decomposition algorithm and applications , J

Oscar H. Ibarra, Shlomo Moran, and Roger Hui, A generalization of the fast LUP matrix decomposition algorithm and applications , J. Algorithms 3 (1982), no. 1, 45–56. MR 646891

work page 1982
[14]

thesis, KAIST, 2018

Jisu Jeong, Parameterized algorithms for width parameters, Ph.D. thesis, KAIST, 2018

work page 2018
[15]

art of trellis decoding

Jisu Jeong, Eun Jung Kim, and Sang-il Oum, The “art of trellis decoding” is ﬁxed-parameter tractable, IEEE Trans. Inform. Theory 63 (2017), no. 11, 7178–7205. MR 3724422

work page 2017
[16]

Discrete Math

, Finding branch-decompositions of matroids, hypergraphs, and more , SIAM J. Discrete Math. 35 (2021), no. 4, 2544–2617

work page 2021
[17]

Mamadou Moustapha Kanté and Michael Rao, The rank-width of edge-coloured graphs, Theory Comput. Syst. 52 (2013), no. 4, 599–644. MR 3038515

work page 2013
[18]

Discrete Math

Navin Kashyap, Matroid pathwidth and code trellis complexity , SIAM J. Discrete Math. 22 (2008), no. 1, 256–272

work page 2008
[19]

Tuukka Korhonen and Sang-il Oum, Branch-width of connectivity functions is ﬁxed-parameter tractable, arXiv:2601.04756, 2026

work page arXiv 2026
[20]

1538–1549

Tuukka Korhonen and Marek Sokołowski, Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth , STOC’24—Proceedings of the 56th Annual ACM Sym- posium on Theory of Computing, ACM, New Y ork, 2024, pp. 1538–1549. MR 4764929

work page 2024
[21]

436 (2012), no

Sang-il Oum, Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices , Linear Algebra Appl. 436 (2012), no. 7, 2008–2036. 28

work page 2012
[22]

Sang-il Oum and Paul Seymour, Approximating clique-width and branch-width , J. Combin. Theory Ser. B 96 (2006), no. 4, 514–528. MR 2232389

work page 2006
[23]

James Oxley, Matroid theory, Oxford University Press, 2011

work page 2011
[24]

Neil Robertson and Paul Seymour,Graph minors. X. Obstructions to tree-decomposition, J. Com- bin. Theory Ser. B 52 (1991), no. 2, 153–190. MR 92g:05158 29

work page 1991