The “Art of Trellis Decoding” Is FixedParameter Tractable
Jeong, Jisu; Kim, Eun Jung; Oum, SangIl (2017), The “Art of Trellis Decoding” Is FixedParameter Tractable, IEEE Transactions on Information Theory, 63, 11, p. 71787205. 10.1109/TIT.2017.2740283
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/1507.02184Date
2017Journal name
IEEE Transactions on Information TheoryVolume
63Number
11Publisher
IEEE  Institute of Electrical and Electronics Engineers
Pages
71787205
Publication identifier
Metadata
Show full item recordAuthor(s)
Jeong, JisuDepartment of Mathematical Sciences, KAIST
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Oum, SangIl
Department of Mathematical Sciences, KAIST
Abstract (EN)
Given n subspaces of a finitedimensional vector space over a fixed finite field F, we wish to find a linear layout V 1 , V 2 ,..., V n of the subspaces such that dim((V 1 + V 2 + ··· + V i ) ∩ (V i+1 + ··· + V n )) ≤ k for all i; such a linear layout is said to have width at most k. When restricted to 1dimensional subspaces, this problem is equivalent to computing the trelliswidth (or minimum trellis statecomplexity) of a linear code in coding theory and computing the pathwidth of an Frepresented matroid in matroid theory. We present a fixedparameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finitedimensional vector space over F. As corollaries, we obtain a fixedparameter tractable algorithm to produce a pathdecomposition of width at most k for an input Frepresented matroid of pathwidth at most k, and a fixedparameter tractable algorithm to find a linear rankdecomposition of width at most k for an input graph of linear rankwidth 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 pathwidth and treewidth of graphs. It was previously known that a fixedparameter tractable algorithm exists for the decision version of the problem for matroid pathwidth; a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field F, there are finitely many forbidden Frepresentable minors for the class of matroids of pathwidth at most k. An algorithm by Hlinený (2006) can detect a minor in an input Frepresented matroid of bounded branchwidth. However, this indirect approach would not produce an actual pathdecomposition. Our algorithm is the first one to construct such a pathdecomposition and does not depend on the finiteness of forbidden minors.Subjects / Keywords
Parameterized complexity; Branchwidth; Pathwidth; Matroid; Trelliswidth; Trellis statecomplexity; Linear code; Linear rankwidth; Linear cliquewidthRelated items
Showing items related by title and author.

Jeong, Jisu; Kim, Eun Jung; Oum, Sangil (2016) Communication / Conférence

Jeong, Jisu; Kim, Eun Jung; Oum, SangIl (2021) Article accepté pour publication ou publié

Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, Ojoung; Oum, SangIl (2023) Article accepté pour publication ou publié

Kim, Eun Jung; Oum, Sangil; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018) Article accepté pour publication ou publié

Kim, Eun Jung; Oum, SangIl; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2015) Communication / Conférence