Kanté, Mamadou Moustapha ;
Kim, Eun Jung ;
Kwon, Ojoung ;
Oum, Sangil
Obstructions for Matroids of PathWidth at most k and Graphs of Linear RankWidth at most k
Abstract
Every minorclosed class of matroids of bounded branchwidth 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 Frepresentable matroids, due to the wellquasiordering of Frepresentable matroids of bounded branchwidth under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is nonconstructive and does not provide any algorithm for computing these Frepresentable excluded minors in general.
We consider the class of matroids of pathwidth at most k for fixed k. We prove that for a finite field F, every Frepresentable excluded minor for the class of matroids of pathwidth 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 Frepresentable excluded minors for the class of matroids of pathwidth k, and this gives as a corollary a polynomialtime algorithm for checking whether the pathwidth of an Frepresented matroid is at most k. We also prove that every excluded pivotminor for the class of graphs having linear rankwidth at most k has at most 2^{2^{O(k²)}} vertices, which also results in a similar algorithmic consequence for linear rankwidth of graphs.
BibTeX  Entry
@InProceedings{kante_et_al:LIPIcs.STACS.2022.40,
author = {Kant\'{e}, Mamadou Moustapha and Kim, Eun Jung and Kwon, Ojoung and Oum, Sangil},
title = {{Obstructions for Matroids of PathWidth at most k and Graphs of Linear RankWidth at most k}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {40:140:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15850},
URN = {urn:nbn:de:0030drops158507},
doi = {10.4230/LIPIcs.STACS.2022.40},
annote = {Keywords: pathwidth, matroid, linear rankwidth, graph, forbidden minor, vertexminor, pivotminor}
}
09.03.2022
Keywords: 

pathwidth, matroid, linear rankwidth, graph, forbidden minor, vertexminor, pivotminor 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 