A Simpler Self-reduction Algorithm for Matroid Path-width

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr

Year of publication 2018
Type Article in Periodical
Magazine / Source SIAM Journal on Discrete Mathematics
MU Faculty or unit

Faculty of Informatics

Citation
Web http://arxiv.org/abs/1605.09520
Doi http://dx.doi.org/10.1137/17M1120129
Keywords matroid; path-width; trellis-width; fixed-parameter tractability; well-quasi-ordering
Description 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 Hlineny [P. Hlieny, 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 "self-reduction" FPT algorithm for a path-decomposition. Precisely, we design an efficient routine that constructs an optimal pathdecomposition 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).
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.