A simpler self-reduction algorithm for matroid path-width
From MaRDI portal
Combinatorial aspects of matroids and geometric lattices (05B35) Paths and cycles (05C38) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Decoding (94B35)
Abstract: 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 by Geelen-Gerards-Whittle [JCTB 2006] in pure matroid theory, it was soon recognized by Kashyap [SIDMA 2008] that it is the same concept as 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 [JCTB 2006] 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 by Jeong-Kim-Oum [SODA 2016]. Here we propose a simpler "self-reduction" 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).
Recommendations
Cites work
- A Parametrized Algorithm for Matroid Branch-Width
- Branch-width and well-quasi-ordering in matroids and graphs.
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Constructive algorithm for path-width of matroids
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Finding Branch-Decompositions and Rank-Decompositions
- Graph minors. I. Excluding a forest
- scientific article; zbMATH DE number 1284437 (Why is no real title available?)
- Linear layouts in submodular systems
- Mathematical Foundations of Computer Science 2003
- Matroid Pathwidth and Code Trellis Complexity
- On Rota's conjecture and excluded minors containing large projective geometries.
- On the excluded minors for the matroids of branch-width \(k\)
- Outerplanar obstructions for matroid pathwidth
- Te "art of trellis decoding" is computationally hard-for large fields
- The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
Cited in
(2)
This page was built for publication: A simpler self-reduction algorithm for matroid path-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4569568)
