Parameterized algorithms for width parameters

Abstract

We study width parameters on graphs, hypergraphs, matroids, and linear codes, which are combinatorial structures. A width parameter on a combinatorial structure is a measure of how thick its tree-like structure or its path-like structure is. There are various width parameters depending on the definition of a tree-like structure or a path-like structure and its thickness. We define width parameters on vector spaces, which are called the branch-width and the path-width. For the branch-width of subspaces of a vector space, we use a branch-decomposition as a tree-like structure and use the dimension of vector spaces as the thickness. For the path-width of subspaces of a vector space, we use a linear layout as a path-like structure and use the dimension of vector spaces as the thickness. Many combinatorial problems are NP-hard. However, if an input is given with its thin tree-like structure or path-like structure, then the problem can solved in polynomial time. One of our main results is to provide a fixed-parameter algorithm, for input subspaces of a vector space and an integer k, that determines whether a branch-decomposition of width at most k exists, and if it exists, finds such a branch-decomposition. In addition, we provide a fixed-parameter algorithm, for input subspaces of a vector space and an integer k, that determines whether a linear layout of width at most k exists, and if it exists, finds such a linear layout. From the algorithms, we present an analogous fixed-parameter algorithm for each of the following width parameters: the rank-width and the linear rank-width of graphs, the branch-width and the linear-width of hypergraphs, the carving-width and the cut-width of graphs, the branch-width and the path-width of matroids represented over a fixed finite field, and the trellis-width of linear codes.