Constructive Algorithm for Matroid Pathwidth
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Provides a cubic-time algorithm that decides whether a represented matroid (n vectors over a fixed finite field) has pathwidth ≤ k and actually outputs a linear layout when one exists. Uses dynamic programming on a given branch decomposition, compresses states via typical sequences and encoding of boundary subspaces, and achieves a single-exponential dependence on k, field size and decomposition width (with polynomial n factor). Also yields FPT results for linear rank-width and an FPT approximation for linear clique-width.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:47Matroid: primer
- 3:57Vectors Arrangement
- 7:26Branchwidth of F- represented matroids
- 8:25From graphs to matroids
- 10:31XP algorithms
- 11:10pw(G)sk via minor testing
- 15:25pw()sk via minor testing
- 18:32Issues with the approach
- 21:23Dynamic programming on a branch-decomposition
- 23:19Encoding a linear layout
- 24:53Compressing a dimension sequence
- 25:09Handling a boundary space
- 26:24Encoding of a linear layout
- 28:51Further questions
related talks
25mAn Improved Lower Bound for Matroid Intersection Prophet inequalities
20mA Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
23mWorst-Case to Expander-Case Reductions
27mSuccinct Preferential Attachment Graphs
A Formal Disproof of Hirsch Conjecture
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
37m"Algorithms" is Not a Four-Letter Word
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy