{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:24Z","timestamp":1787321124085,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["17-00837S"],"award-info":[{"award-number":["17-00837S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The path-width of matroids naturally generalizes the better known parameter of path-width for graphs and is NP-hard by a reduction from the graph case. While the term matroid path-width was formally introduced in [J. Geelen, B. Gerards, and G. Whittle, J. Combin. Theory Ser. B, 96 (2006), pp. 405--425] in pure matroid theory, it was soon recognized in [N. Kashyap, SIAM J. Discrete Math., 22 (2008), pp. 256--272] that it is the same concept as the long-studied so-called trellis complexity in coding theory, later named trellis-width, and hence it is an interesting notion also from the algorithmic perspective. It follows from a result of Hlin\u011bn\u00fd [P. Hlin\u011bn\u00fd, J. Combin. Theory Ser. B, 96 (2006), pp. 325--351] that the decision problem---whether a given matroid over a finite field has path-width at most $t$---is fixed-parameter tractable (FPT) in $t$, but this result does not give any clue about constructing a path-decomposition. The first constructive and rather complicated FPT algorithm for path-width of matroids over a finite field was given in [J. Jeong, E. J. Kim, and S. Oum, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2016, pp. 1695--1704]. Here we propose a simpler \u201cself-reduction\u201d FPT algorithm for a path-decomposition. Precisely, we design an efficient routine that constructs an optimal path-decomposition of a matroid by calling any subroutine for testing whether the path-width of a matroid is at most $t$ (such as the aforementioned decision algorithm for matroid path-width).<\/jats:p>","DOI":"10.1137\/17m1120129","type":"journal-article","created":{"date-parts":[[2018,6,19]],"date-time":"2018-06-19T11:17:18Z","timestamp":1529407038000},"page":"1425-1440","source":"Crossref","is-referenced-by-count":0,"title":["A Simpler Self-reduction Algorithm for Matroid Path-Width"],"prefix":"10.1137","volume":"32","author":[{"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,19]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00046-1"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2082"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.09.005"},{"key":"atypb5","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1007\/978-3-540-45138-9_41","volume":"2747","author":"Hline\u030cny\u0301 P.","year":"2003","journal-title":"Lecture Notes in Comput. Sci."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418589"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.08.005"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/070685920"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/18.669287"},{"key":"atypb10","first-page":"1695","author":"Jeong J.","year":"2016","journal-title":"SIAM"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2740283"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/070691152"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2013.10.007"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"H. Nagamochi,\n                      Linear layouts in submodular systems\n                      , in Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings, Lecture Notes in Comput. Sci. 7676, Springer, 2012, pp. 475-484,https:\/\/doi.org\/10.1007\/978-3-642-35261-4_50.","DOI":"10.1007\/978-3-642-35261-4_50"},{"key":"atypb15","unstructured":"J. G. Oxley,\n                      Matroid Theory\n                      , Oxford Graduate Texts in Mathematics, Oxford University Press, New York, 2006."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"atypb17","first-page":"1989","author":"Vardy A.","year":"1998","journal-title":"Amsterdam"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1120129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:23Z","timestamp":1787317583000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1120129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1120129"],"URL":"https:\/\/doi.org\/10.1137\/17m1120129","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}