The \emph{linear rank-width} of a graph is the minimum width over all possible linear layouts $(v_1, v_2, \ldots, v_n)$ of the vertex set of the graph, where the width of a linear layout is the maximum rank of the $(0,1)$-adjacency matrices induced by the vertex partitions $(\{v_1, \ldots, v_i\}, \{v_{i+1}, \ldots, v_n\})$.
Linear rank-width is the linearized variant of rank-width, just as path-width is the linearized variant of tree-width. Motivated by numerous results on path-width, we investigate several properties of linear rank-width of graphs.
In Chapters 6,7, and 8, we study structural properties of graphs related to linear rank-width. As a corollary of known theorems by Oum [2008], for each $k$, there is a finite set of graphs such that a graph $G$ has linear rank-width at most $k$ if and only if no vertex-minor of $G$ is isomorphic to a graph in the set. We show that the number of pairwise locally non-equivalent vertex-minor minimal graphs for the class of graphs of linear rank-width at most $k$ is at least $2^{\Omega(3^k)}$.
For a fixed tree $T$, we ask whether every graph with sufficiently large linear rank-width contains a vertex-minor isomorphic to $T$. We show that this question is true if it is true for prime graphs. Prime graphs are graphs with no vertex partition $(A,B)$ with $|A|$, $|B| \ge 2$ such that the set of edges joining $A$ and $B$ induces a complete bipartite graph.
We also investigate a Ramsey type result for prime graphs. We prove that for each $n$, there exists $N$ such that every prime graph on at least $N$ vertices contains a vertex-minor isomorphic to either a cycle of length $n$ or the line graph of the complete bipartite graph $K_{2,n}$.
In Chapters 9, 10, and 11, we develop graph algorithms related to linear rank-width. We first verify that computing linear rank-width on graphs is NP-hard, using the result on matroid path-width by Kashyap [2008]. We then ask which graph classes admit a polynomial-time algorithm for computing linear rank-width. For distance-hereditary graphs, we show that it is possible to compute the linear rank-width in time $\mathcal{O}(n^2 \log_2 n)$. As a corollary, we can compute the path-width of $n$-element matroids of branch-width at most $2$ in time $\mathcal{O}(n^2 \log_2 n)$, provided that the matroid is given by an independent set oracle.
We also discuss graph modification problems related to linear rank-width. We prove that for a positive integer $k$ and an input graph $G$ with $n$ vertices, we can decide in time $8^k\cdot n^{\mathcal{O}(1)}$ whether $G$ contains a vertex subset $S$ of size at most $k$ such that $G\setminus S$ has linear rank-width at most $1$. We also show that this problem admits a polynomial kernel, which means that there exists a polynomial-time algorithm to transform an input graph $G$ and a positive integer $k$ into another instance $G'$ and $k'$ such that $(G, k)$ is a \textsc{Yes}-instance if and only if $(G',k')$ is a \textsc{Yes}-instance, and $|V(G')|$ is bounded by a polynomial function in $k$. Additionally, for a positive integer $k$ and an input graph $G$ with $n$ vertices, we can decide in time $2^{\mathcal{O}(k\log_2 k)}\cdot n^{\mathcal{O}(1)}$ whether $G$ contains a vertex subset $S$ of size at most $k$ such that $G\setminus S$ has rank-width at most $1$.
이 논문에서는 linear rank-width의 성질들에 대해서 알아보았다. 알려진 path-width와 tree-width의 관계와 같이 linear rank-width는 rank-width의 선형형태로 볼 수 있다. Path-width에 대해 알려진 결과들로부터 동기를 부여받아, linear rank-width와 관련된 질문들을 던지고 그 질문들에 답을 하였다.
첫 번째로, linear rank-width와 연관된 그래프의 구조적 성질에 대해 관찰하였다. 본 저자는 linear rank-width가 $k$ 이하인 그래프 모임에 대해 vertex-minor 관계로 최소인 그래프들의 개수가 적어도 $2^{\Omega(3^k)}$ 개 이상 있음을 증명하였다. 주어진 그래프 $G$와 상수 $k$에 대해 $G$의 linear rank-width가 $k$이하임을 테스트하는 문제에 대한 constructive한 fixed parameter tractable 알고리즘이 알려진 것이 없는데, vertex-minor 관계로 최소인 그래프들을 모두 구할 수 있으면, 이런 알고리즘을 제시할 수 있다. Linear rank-width가 $k$ 이하인 그래프 모임에 대한 vertex-minor 관계로 최소인 그래프의 크기의 상한을 구하는 것에 대해 알려진 것이 없으며, 이를 알아내는 것은 흥미로운 미해결 문제이다.
Split과 prime 그래프 개념은 이 논문에서 가장 중요하게 쓰인 도구 중 하나이다. 본 저자는 고정된 트리 그래프 $T$에 대해 충분히 linear rank-width가 큰 그래프는 $T$를 반드시 vertex-minor로 가진다는 질문을 던졌다. 이에 대해 이 질문을 증명하는 것은 이 질문을 prime 그래프 상에서 증명하는 것과 동치임을 증명하였다. 또한, 고정된 상수 $n$에 대해, 다른 상수 $N$이 존재하여 점의 개수가 $N$개 이상인 prime 그래프는 반드시 길이 $n$인 원 그래프를 가지거나 아니면 완전 이분그래프 $K_{2,n}$의 선 그래프를 vertex-minor로 가짐을 증명하였다.
두 번째는, linear rank-width와 관련된 그래프의 알고리즘을 개발하였다. 먼저, 본 저자는 처음으로 $n$개의 점을 가지는 distance-hereditary 그래프 상에서 linear rank-width를 다항식 시간에 계산하는 알고리즘을 고안하였다. 이 결과를 이용하면 independent set 오라클이 있다는 가정 하에 branch-width가 $2$ 이하인 매트로이드의 path-width도 다항식 시간에 계산할 수 있음을 증명하게 된다. 이를 일반화하는 문제로서 rank-width가 상한된 그래프에 대해서도 linear rank-width를 계산하는 다항식 알고리즘을 생각해 볼 수 있는데, 이에 대해 아직 알려진 바가 없다.
마지막으로, 본 저자는 \textsc{Linear rank-width $w$ 점 지우기}과 \textsc{Rank-width $w$ 점 지우기} 문제를 $w$가 $1$인 경우에 대하여 연구하였다. 다음으로 연구해볼 수 있는 것은 $1$보다 큰 $w$에 대해서 비슷한 fixed parameter tractable 알고리즘과 다항식 kernel의 존재 여부이다. 본 저자는 특히, \textsc{Rank-width $1$ 점 지우기} 문제를 $2^{\mathcal{O}(k\log_2 k)}\cdot n^{\mathcal{O}(1)}$ 시간에 해결할 수 있음을 증명하였는데, 이를 어떤 상수 $c$에 대해 $c^k\cdot n^{\mathcal{O}(1)}$ 시간에 풀 수 있음을 미해결 문제로 제시한다.
