Informatics colloquium 16. 5. The "art of trellis decoding" is fixed-parameter tractable
Informatics colloquium 16. 5. 2017, 14:00 lecture hall D2
Dr. Eun Jung Kim, Centre national de la recherche scientifique, Paris
The "art of trellis decoding" is fixed-parameter tractable
Abstract: Given n subspaces of a finite-dimensional vector space over a fixed
finite field F, we wish to find a linear layout V1, V2, . . . , Vn of the
subspaces such that dim((V1 + V2 +···+Vi)∩(Vi+1 +···+Vn)) ≤ k for all i; such a
linear layout is said to have width at most k. When restricted to 1- dimensional
subspaces, this problem is equivalent to computing the trellis- width (or
minimum trellis state-complexity) of a linear code in coding theory and
computing the path-width of an F-represented matroid in matroid theory. We
present a fixed-parameter tractable algorithm to construct a linear layout of
width at most k, if it exists, for input subspaces of a finite-dimensional
vector space over F. As corollaries, we obtain a fixed-parameter tractable
algorithm to produce a path- decomposition of width at most k for an input F-
represented matroid of path-width at most k, and a fixed-parameter tractable
algorithm to find a linear rank-decomposition of width at most k for an input
graph of linear rank-width at most k. In both corollaries, no such algorithms
were known previously. Our approach is based on dynamic programming combined
with the idea developed by Bodlaender and Kloks (1996) for their work on
path-width and tree-width of graphs.
It was previously known that a fixed-parameter tractable algorithm exists for
the decision version of the problem for matroid path-width; a theorem by Geelen,
Gerards, and Whittle (2002) implies that for each fixed finite field F, there
are finitely many forbidden F-representable minors for the class of matroids of
path-width at most k. An algorithm by Hlineny (2006) can detect a minor in an
input F-represented matroid of bounded branch-width. However, this indirect
approach would not produce an actual path-decomposition. Our algorithm is the
first one to construct such a path-decomposition and does not depend on the
finiteness of forbidden minors.