Linear matroid and algorithm for computing pathwidth

biography

KAIST산업공학과에서 학부와 석사학위를 마친 후 2010년 영국 런던대학교 Royal Holloway에서 전산학 박사학위를 받았다. 프랑스 몽펠리에의 LIRMM연구소에서 박사후 과정(2010-2011)을 거쳐 현재 프랑스 국립과학연구센터 (CNRS, Centre National de la Recherche Scientifique)의 1급 책임연구원으로 재직 중이다. 이론 전산분야에서 알고리즘 설계 및 분석,복잡도 이론, 그래프 및 조합적 대상에 대한 이론을 연구하고 있다. CNRS에서 매년 젊은 연구자들 중 선정해 수여하는 메달(medialle bronze)의 2017년 전산 분야 수상자이다.

Abstract

Given 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.