A simpler self-reduction algorithm for matroid path-width
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Paths and cycles (05C38) Graph minors (05C83) 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
- scientific article; zbMATH DE number 1284437 (Why is no real title available?)
- 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
- 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)
