Upper bounds on the size of obstructions for graphs of linear rank-width at most k

2014/12/02 Tuesday **4PM-5PM**

Room 1409

Graph layout problems are a class of optimization problems whose goal is to find a linear ordering of an input graph in such a way that a certain objective function is optimized. The matrix rank function has been studied as an objective function. The linear rank-width of a graph G is the minimum integer k such that G admits a linear ordering \(v_1, v_2, \ldots , v_n\) satisfying that the maximum over all values $$ \operatorname{rank}A_G[\{v_1, v_2, \ldots, v_t\}, \{v_{t+1}, \ldots, v_n\}]$$ is k, where \(A_G\) is the adjacency matrix of G and the rank is computed over the binary field.

In this talk, we present a result that for every graph G that is vertex-minor minimal with the property having linear rank-width larger than p, the number of vertices in G is at most doubly exponential in \(\mathcal{O}(p)\). The number of vertex-minor obstructions for linear rank-width at most p is of interest because the only known fixed parameter tractable algorithm to test whether linear rank-width is at most p is using the finiteness of the number of forbidden vertex-minor obstructions. Our result gives an upper bound of the complexity on this algorithm. Our basic tools are the algebraic operations on labelled graphs introduced by Kanté and Rao, and we extend the notion of vertex-minors in our purpose. This is joint work with Mamadou Moustapha Kanté.

Tags: 권오정

This entry was posted on Monday, November 17th, 2014 at 7:57 pm and is filed under 2014, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.