2026-08-07T12:10:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15850 2024-03-06T10:56:21Z ddc:004 open_access

Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k Kanté, Mamadou Moustapha Kim, Eun Jung Kwon, O-joung Oum, Sang-il path-width matroid linear rank-width graph forbidden minor vertex-minor pivot-minor Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field F, the list contains only finitely many F-representable matroids, due to the well-quasi-ordering of 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 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 F, every F-representable excluded minor for the class of matroids of path-width at most k has at most 2^{|𝔽|^{O(k²)}} elements. We can therefore compute, for any integer k and a fixed finite field F, the set of 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 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²)}} vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mamadou Moustapha Kanté and Eun Jung Kim and O-joung Kwon and Sang-il Oum 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.40 urn:nbn:de:0030-drops-158507 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.40 eng https://creativecommons.org/licenses/by/4.0/legalcode