Mamadou Moustapha Kanté
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Mamadou Moustapha Kanté has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- O-Joung Kwon
Department of Mathematics, Hanyang University, Seoul, South Korea
9 shared publications - Benjamin Bergougnoux
University of Warsaw
6 shared publications - Sang-Il Oum
Discrete Mathematics Group Institute for Basic Science (IBS) Daejeon South Korea
6 shared publications - Daniël Paulusma
Durham University, Durham, UK
4 shared publications - Jisu Jeong
Clova AI Research NAVER Corp Seongnam Korea
4 shared publications - Konrad Kazimierz Dabrowski
School of Computing, Newcastle University, Newcastle upon Tyne, UK
3 shared publications
Latest Publications
- 20 May 2026
- Published by Springer Nature in Algorithmica
- Vol. 88 (3) , 47
Computing Pivot-Minors
- 26 March 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Graph structurings : some algorithmic applications
Structurations des graphes : quelques applications algorithmiques: Tous les problèmes définissables en logique du second ordre monadique peuvent être résolus en temps polynomial dans les classes de graphes qui ont une largeur de clique bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La largeur de rang, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de vertex-minor pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure comme vertex-minor. Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété P dans un graphe G, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si G satisfait P en n'utilisant que les étiquettes des sommets. Nous montrons que si P est une propriété définissable en logique du premier ordre alors, certaines classes de graphes de largeur de clique localement bornée admettent un système d'étiquetage pour P avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire. Si x et y sont deux sommets, X un ensemble de sommets et F un ensemble d'arêtes, nous notons Conn(x,y,X,F) la propriété qui vérifie dans un graphe donné si x et y sont connectés par un chemin, qui ne passe par aucun sommet de X si aucune arête de F. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que Conn(x,y,X,0) admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des combinaisons de graphes qui ont une petite largeur de clique et telles que le graphe d'intersection de ces derniers est planaire et est de degré borné.
- 26 March 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Graph structurings : some algorithmic applications
Structurations des graphes : quelques applications algorithmiques: Tous les problèmes définissables en logique du second ordre monadique peuvent être résolus en temps polynomial dans les classes de graphes qui ont une largeur de clique bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La largeur de rang, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de vertex-minor pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure comme vertex-minor. Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété P dans un graphe G, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si G satisfait P en n'utilisant que les étiquettes des sommets. Nous montrons que si P est une propriété définissable en logique du premier ordre alors, certaines classes de graphes de largeur de clique localement bornée admettent un système d'étiquetage pour P avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire. Si x et y sont deux sommets, X un ensemble de sommets et F un ensemble d'arêtes, nous notons Conn(x,y,X,F) la propriété qui vérifie dans un graphe donné si x et y sont connectés par un chemin, qui ne passe par aucun sommet de X si aucune arête de F. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que Conn(x,y,X,0) admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des combinaisons de graphes qui ont une petite largeur de clique et telles que le graphe d'intersection de ces derniers est planaire et est de degré borné.
- Open Access
Transducing Linear Decompositions of Tournaments
Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We show that in the case of tournaments, a first-order transduction suffices. This implies that the logics CMSO and existential MSO are equivalent over bounded linear clique-width tournaments.
Open AccessTransducing Linear Decompositions of Tournaments
Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-decompositions of bounded width can be produced by a CMSO transduction. We show that in the case of tournaments, a first-order transduction suffices. This implies that the logics CMSO and existential MSO are equivalent over bounded linear clique-width tournaments.
- Open Access
- 18 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms that achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n -vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, • Independent Set and Dominating Set can be solved in time \(2^{\mathcal {O}(dk)}\cdot n^{\mathcal {O}(1)} \) using \(\mathcal {O}(dk\log n) \) space; • Max Cut can be solved in time \(n^{\mathcal {O}(dk)} \) using \(\mathcal {O}(dk\log n) \) space. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence , which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial..- 18 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
Open AccessSpace-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms that achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n -vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, • Independent Set and Dominating Set can be solved in time \(2^{\mathcal {O}(dk)}\cdot n^{\mathcal {O}(1)} \) using \(\mathcal {O}(dk\log n) \) space; • Max Cut can be solved in time \(n^{\mathcal {O}(dk)} \) using \(\mathcal {O}(dk\log n) \) space. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence , which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.. - 27 May 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1007
Generalisations of matrix partitions: Complexity and obstructions
- 27 May 2024
- Published by Elsevier in Theoretical Computer Science
- Vol. 1007
Generalisations of matrix partitions: Complexity and obstructions
- Open Access
Computing pivot-minors
A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. Pivot-minors have mainly been studied from a structural perspective. In this paper we perform the first systematic computational complexity study of pivot-minors. We first prove that the Pivot-Minor problem, which asks if a given graph $G$ contains a pivot-minor isomorphic to a given graph $H$, is NP-complete. If $H$ is not part of the input, we denote the problem by $H$-Pivot-Minor. We give a certifying polynomial-time algorithm for $H$-Pivot-Minor when (1) $H$ is an induced subgraph of $P_3+tP_1$ for some integer $t\geq 0$, (2) $H=K_{1,t}$ for some integer $t\geq 1$, or (3) $|V(H)|\leq 4$ except when $H \in \{K_4,C_3+ P_1\}$. Let ${\cal F}_H$ be the set of induced-subgraph-minimal graphs that contain a pivot-minor isomorphic to $H$. To prove the above statement, we either show that there is an integer $c_H$ such that all graphs in ${\cal F}_H$ have at most $c_H$ vertices, or we determine ${\cal F}_H$ precisely, for each of the above cases.Open AccessComputing pivot-minors
A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. Pivot-minors have mainly been studied from a structural perspective. In this paper we perform the first systematic computational complexity study of pivot-minors. We first prove that the Pivot-Minor problem, which asks if a given graph $G$ contains a pivot-minor isomorphic to a given graph $H$, is NP-complete. If $H$ is not part of the input, we denote the problem by $H$-Pivot-Minor. We give a certifying polynomial-time algorithm for $H$-Pivot-Minor when (1) $H$ is an induced subgraph of $P_3+tP_1$ for some integer $t\geq 0$, (2) $H=K_{1,t}$ for some integer $t\geq 1$, or (3) $|V(H)|\leq 4$ except when $H \in \{K_4,C_3+ P_1\}$. Let ${\cal F}_H$ be the set of induced-subgraph-minimal graphs that contain a pivot-minor isomorphic to $H$. To prove the above statement, we either show that there is an integer $c_H$ such that all graphs in ${\cal F}_H$ have at most $c_H$ vertices, or we determine ${\cal F}_H$ precisely, for each of the above cases. - Open Access
More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ where $k$ is respectively the clique-width, $\mathbf{Q}$-rank-width, rank-width and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013] and the rank-based approach introduced in [Bodlaender, Cygan, Kratsch and Nederlof, ICALP 2013]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for $W[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$ and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $\mathbf{Q}$-rank-width and the rank-width of the input graph.Open AccessMore applications of the d-neighbor equivalence: acyclicity and connectivity constraints
In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ where $k$ is respectively the clique-width, $\mathbf{Q}$-rank-width, rank-width and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013] and the rank-based approach introduced in [Bodlaender, Cygan, Kratsch and Nederlof, ICALP 2013]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for $W[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$ and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $\mathbf{Q}$-rank-width and the rank-width of the input graph. - Open Access
Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. However, for each fixed finite field $\mathbb F$, the list needs to contain only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these $\mathbb F$-representable excluded minors in general. We consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field $\mathbb F$, every $\mathbb F$-representable excluded minor for the class of matroids of path-width at most $k$ has at most $2^{|\mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute, for any integer $k$ and a fixed finite field $\mathbb F$, the set of $\mathbb F$-representable excluded minors for the class of matroids of path-width $k$, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an $\mathbb F$-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.Open AccessObstructions for matroids of path-width at most k and graphs of linear rank-width at most k
Every minor-closed class of matroids of bounded branch-width can be characterized by a list of excluded minors, but unlike graphs, this list may need to be infinite in general. However, for each fixed finite field $\mathbb F$, the list needs to contain only finitely many $\mathbb F$-representable matroids, due to the well-quasi-ordering of $\mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these $\mathbb F$-representable excluded minors in general. We consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field $\mathbb F$, every $\mathbb F$-representable excluded minor for the class of matroids of path-width at most $k$ has at most $2^{|\mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute, for any integer $k$ and a fixed finite field $\mathbb F$, the set of $\mathbb F$-representable excluded minors for the class of matroids of path-width $k$, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an $\mathbb F$-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs. - Open Access
A linear fixed parameter tractable algorithm for connected pathwidth
The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called {\em connected pathwidth}. We prove that connected pathwidth is fixed parameter tractable, in particular we design a $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connected pathwidth of $G$ is at most $k.$ This resolves an open question by [Dereniowski, Osula, and Rz{\k{a}}{\.{z}}ewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85-100, 2019]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996] for the design of linear parameterized algorithms for treewidth and pathwidth. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well.Open AccessA linear fixed parameter tractable algorithm for connected pathwidth
The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called {\em connected pathwidth}. We prove that connected pathwidth is fixed parameter tractable, in particular we design a $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connected pathwidth of $G$ is at most $k.$ This resolves an open question by [Dereniowski, Osula, and Rz{\k{a}}{\.{z}}ewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85-100, 2019]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996] for the design of linear parameterized algorithms for treewidth and pathwidth. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well. - Open Access
Tree pivot-minors and linear rank-width
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role from tree-width and path-width. As such, it is natural to examine if for every tree~$T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving: (1) for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; (2) for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.Open AccessTree pivot-minors and linear rank-width
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role from tree-width and path-width. As such, it is natural to examine if for every tree~$T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving: (1) for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; (2) for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.