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.
그래프와 하이퍼그래프, 매트로이드, 선형 코드 등의 조합 구조에서 width parameter를 연구했다. 조합 구조에서 width parameter는 그것의 트리 구조나 선형 구조가 얼마나 두꺼운지를 측정한 것이다. 트리 구조나 선형 구조, 그리고 그것의 두께를 정의하는 방법에 따라 다양한 width parameter들이 존재한다. 우리는 벡터 공간에서의 width parameter인 branch-width와 path-width를 정의했다. Branch-width를 정의할 때 트리 구조로 branch-decomposition을 사용하고 두께로 벡터 공간의 차원을 사용한다. 또한, path-width를 정의할 때는 선형 구조로 linear layout을 사용하고 두께로 벡터 공간의 차원을 사용한다.
많은 조합 문제들은 NP-hard이다. 그러나 만약 입력값과 함께 두께가 얇은 트리 구조나 선형 구조가 주어진다면 다항 시간에 풀 수 있다. 우리의 주요 결과는 벡터 공간의 부분공간들과 정수 k가 주어졌을 때, 너비가 k이하인 branch-decomposition이 존재하는지 판단하고, 존재한다면 그것을 출력하는 fixed-parameter 알고리즘과 너비가 k이하인 linear layout이 존재하는지 판단하고, 존재한다면 그것을 출력하는 fixed-parameter 알고리즘을 개발한 것이다. 이를 이용하여 그래프의 rank-width와 linear rank-width, 하이퍼그래프의 branch-width와 linear-width, 그래프의 carving-width와 cut-width, 매트로이드의 branch-width와 path-width, 선형 코드의 trellis-width 각각에 대해 비슷한 작업을 하는 fixed-parameter 알고리즘을 얻었다.
