pith. sign in

arxiv: 1907.04132 · v1 · pith:DNTJ2NKOnew · submitted 2019-07-09 · 💻 cs.DS · cs.CC

Linear MIM-Width of Trees

Svein H{\o}gemo , Jan Arne Telle , Erlend Raa V{\aa}gset This is my paper

Pith reviewed 2026-05-25 00:00 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords linear MIM-widthtreesgraph width parametersinduced matchinglinear layoutalgorithmdynamic programming
0
0 comments X

The pith

An O(n log n) algorithm computes the linear maximum induced matching width of any tree and returns an optimal layout.

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

The paper presents an algorithm that calculates the linear MIM-width of a tree in O(n log n) time. Linear MIM-width quantifies the smallest width achievable in a linear ordering of vertices, where width is determined by the size of a maximum induced matching in certain cut sets. The algorithm works because trees have a recursive structure that permits efficient dynamic updates of possible matchings during layout construction. A reader would care if they need to solve problems that become tractable once this width parameter is known and small. The method also produces the layout itself, so the output is immediately usable for downstream algorithms.

Core claim

We provide an O(n log n) algorithm computing the linear maximum induced matching width of a tree and an optimal layout.

What carries the argument

A tree-specific algorithm that computes the minimum width over all linear layouts by tracking maximum induced matchings across subtree cuts.

If this is right

  • Linear MIM-width becomes polynomial-time computable on all trees.
  • An explicit optimal linear layout can be constructed for any tree in O(n log n) time.
  • Problems parameterized by linear MIM-width admit efficient solutions when restricted to tree inputs.
  • The same algorithmic technique may apply to related width measures defined via induced matchings on trees.

Where Pith is reading between the lines

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

  • Similar divide-and-conquer strategies could be tested on outerplanar graphs or series-parallel graphs to see if the same time bound holds.
  • If the algorithm's internal width tables can be maintained under edge contractions, it might yield a practical heuristic for general graphs.
  • The O(n log n) bound suggests that exact linear MIM-width could serve as a preprocessing step in tree-based optimization pipelines without dominating total runtime.

Load-bearing premise

The input is a tree and the standard definition of linear MIM-width applies without modification.

What would settle it

A single tree on which the algorithm returns a width value larger than the minimum width over all linear vertex orderings would falsify the claim.

Figures

Figures reproduced from arXiv: 1907.04132 by Erlend Raa V{\aa}gset, Jan Arne Telle, Svein H{\o}gemo.

Figure 1
Figure 1. Figure 1: A tree with a path P = (x1, x2, x3, x4), with nodes in N[N[P]] and dangling trees featured, and below it the order given by the Path Layout Lemma Firstly, from the algorithm it should be clear that each node of T is added exactly once to σT , that it runs in linear time, and that there is no cut containing two crossing edges from two separate dangling trees. Now we must show that σT does not contain cuts w… view at source ↗
Figure 2
Figure 2. Figure 2: The smallest tree with LMIM-width 2, having a node v with three 1-neighbors u1, u2, u3 having dangling trees S1, S2, S3, respectively, so that D(v, 1) = 3 By Theorem 1, every tree with LMIM-width k ≥ 2 must be at least 3 times bigger than the smallest tree with LMIM-width k−1, which implies the following. Remark 1. The LMIM-width of an n-node tree is O(log n). 3 Rooted trees, k-critical nodes and labels Ou… view at source ↗
Figure 3
Figure 3. Figure 3: A decision tree corresponding to the case analysis of Proposition 1 Proof. We show that exactly one case applies to every rooted tree and in each case we assign the label according to Definition 4. First the base case: either x is a leaf or all its children are leaves and we are in Case 0 and the label is assigned according to Def. 4. Otherwise, observe the decision tree in [PITH_FULL_IMAGE:figures/full_f… view at source ↗
Figure 4
Figure 4. Figure 4: A rooted tree of LMIM-width 4 with labels of subtrees. We explain the labels (3, t.2),(3, t.3),(3, 2, t.2) assigned to subtrees rooted at the nodes we call a, b, c, with parent(a) = b and parent(b) = c. The sub-tree rooted at a, with label (3, t.2) has precisely two children that have a child-tree each of LMIM-width 3, hence a is 3- critical and it is a type 2 tree (Case 2 of Prop. 1). The sub-tree rooted … view at source ↗
Figure 5
Figure 5. Figure 5: The same decision tree as shown in Prop. 1, but adapted to MakeLabel Lemma 2. Given labels at descendants of node x in Tr, MakeLabel(Tr, x) computes label(Tr[x]) as the value of cur label. Proof. Assume that x has the children v1, . . . , vd, and denote their set of la￾bels as L = {l1, . . . , ld}. MakeLabel keeps a variable cur label that is updated maximally k times in a for loop, where k is the biggest … view at source ↗
Figure 6
Figure 6. Figure 6: The path P in green for the proof of Theorem 3. 5 Conclusion We have given an O(n log n) algorithm computing the LMIM-width and an opti￾mal layout of an n-node tree. This is the first graph class of LMIM-width larger than 1 having a polynomial-time algorithm computing LMIM-width and thus constitutes an important step towards a better understanding of LMIM-width. Indeed, for the development of FPT algorithm… view at source ↗
read the original abstract

We provide an $O(n \log n)$ algorithm computing the linear maximum induced matching width of a tree and an optimal layout.

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.

Referee Report

0 major / 1 minor

Summary. The manuscript claims to provide an O(n log n) algorithm that computes the linear maximum induced matching width of a tree together with an optimal layout.

Significance. If correct, the result supplies a near-linear time algorithm for a graph layout parameter on trees. This is a concrete algorithmic contribution in the area of width parameters and could support further work on MIM-width and related problems.

minor comments (1)
  1. The provided text consists only of the abstract; without the algorithm description, proof, or pseudocode it is not possible to verify the claimed runtime or correctness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for reviewing our manuscript. The recommendation is 'uncertain' but the report lists no major comments or specific concerns about the claimed O(n log n) algorithm or its correctness. We are prepared to provide further details on the dynamic programming approach or the layout construction if requested.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper claims an O(n log n) algorithm for linear MIM-width on trees together with an optimal layout. The definition of linear MIM-width is imported unchanged from prior literature and applied directly to trees; no modification, fitting, or self-referential redefinition occurs. The result is a computational procedure whose correctness is established by standard algorithmic analysis rather than by any equation or parameter that reduces to the input data by construction. No self-citation chains, ansatzes, or renamings of known results are load-bearing for the central claim.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are mentioned in the abstract.

pith-pipeline@v0.9.0 · 5537 in / 797 out tokens · 17120 ms · 2026-05-25T00:00:29.241825+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

  1. [1]

    Linear rank-width and linear clique-width of trees

    Isolde Adler and Mamadou Moustapha Kant´ e. Linear rank-width and linear clique-width of trees. Theor. Comput. Sci. , 589:87–98, 2015

    work page 2015

  2. [2]

    Graph classes with structured neigh- borhoods and algorithmic applications

    R´ emy Belmonte and Martin Vatshelle. Graph classes with structured neigh- borhoods and algorithmic applications. Theor. Comput. Sci. , 511:54 – 65, 2013. 18 S. Høgemo et al

    work page 2013

  3. [3]

    Rank based ap- proach on graphs with structured neighborhood

    Benjamin Bergougnoux and Mamadou Moustapha Kant´ e. Rank based ap- proach on graphs with structured neighborhood. CoRR, abs/1805.11275, 2018

    work page arXiv 2018

  4. [4]

    Bodlaender

    Hans L. Bodlaender. A linear-time algorithm for finding tree- decompositions of small treewidth. SIAM J. Comput. , 25(6):1305–1317, 1996

    work page 1996

  5. [5]

    Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems

    Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. , 511:66 – 76, 2013

    work page 2013

  6. [6]

    Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics

    Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012

    work page 2012

  7. [7]

    Ellis, Ivan Hal Sudborough, and Jonathan S

    John A. Ellis, Ivan Hal Sudborough, and Jonathan S. Turner. The vertex separation and search number of a graph. Inf. Comput., 113(1):50–79, 1994

    work page 1994

  8. [8]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the tractability of optimization problems on H-graphs. In Proc. ESA 2018 , pages 30:1 – 30:14, 2018

    work page 2018

  9. [9]

    Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width

    Esther Galby, Andrea Munaro, and Bernard Ries. Semitotal domina- tion: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width. CoRR, abs/1810.06872, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  10. [10]

    Golovach, Pinar Heggernes, Mamadou Moustapha Kant´ e, Dieter Kratsch, Sigve Hortemo Sæther, and Yngve Villanger

    Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kant´ e, Dieter Kratsch, Sigve Hortemo Sæther, and Yngve Villanger. Output-polynomial enumeration on graphs of bounded (local) linear mim-width. Algorithmica, 80(2):714–741, 2018

    work page 2018

  11. [11]

    On the clique-width of some perfect graph classes

    Martin Charles Golumbic and Udi Rotics. On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. , 11(3):423–443, 2000

    work page 2000

  12. [12]

    Width param- eters beyond tree-width and their applications

    Petr Hlinen´ y, Sang-il Oum, Detlef Seese, and Georg Gottlob. Width param- eters beyond tree-width and their applications. Comput. J., 51(3):326–362, 2008

    work page 2008

  13. [13]

    Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Generalized distance domination problems and their complexity on graphs of bounded mim-width. In 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, pages 6:1–6:14, 2018

    work page 2018

  14. [14]

    Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width

    Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, pages 21:1–21:13, 2017

    work page 2017

  15. [15]

    A unified polynomial- time algorithm for feedback vertex set on graphs of bounded mim-width

    Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A unified polynomial- time algorithm for feedback vertex set on graphs of bounded mim-width. In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France , pages 42:1–42:14, 2018

    work page 2018

  16. [16]

    Lower bounds on the mim-width of some graph classes

    Stefan Mengel. Lower bounds on the mim-width of some graph classes. Discrete Applied Mathematics, 248:28–32, 2018

    work page 2018

  17. [17]

    Graph problems related to gate matrix layout and pla folding

    Rolf H M¨ ohring. Graph problems related to gate matrix layout and pla folding. In Computational graph theory, pages 17–51. Springer, 1990. Linear MIM-Width of Trees 19

    work page 1990

  18. [18]

    Rank-width: Algorithmic and structural results

    Sang-il Oum. Rank-width: Algorithmic and structural results. Discrete Applied Mathematics, 231:15–24, 2017

    work page 2017

  19. [19]

    Hardness of computing width parameters based on branch decompositions over the vertex set

    Sigve Hortemo Sæther and Martin Vatshelle. Hardness of computing width parameters based on branch decompositions over the vertex set. Theor. Comput. Sci., 615:120–125, 2016

    work page 2016

  20. [20]

    New width parameters of graphs

    Martin Vatshelle. New width parameters of graphs . PhD thesis, University of Bergen, Norway, 2012

    work page 2012

  21. [21]

    Inapproximability of rank, clique, boolean, and maximum induced matching-widths under small set expansion hypothesis

    Koichi Yamazaki. Inapproximability of rank, clique, boolean, and maximum induced matching-widths under small set expansion hypothesis. Algorithms, 11(11):173, 2018

    work page 2018