English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Linear rankwidth is a linearized variant of rankwidth, introduced by Oum andSeymour [Approximating clique-width and branch-width. J. Combin. Theory Ser. B,96(4):514--528, 2006]. Motivated from recent development on graph modificationproblems regarding classes of graphs of bounded treewidth or pathwidth, westudy the Linear Rankwidth-1 Vertex Deletion problem (shortly, LRW1-VertexDeletion). In the LRW1-Vertex Deletion problem, given an $n$-vertex graph $G$and a positive integer $k$, we want to decide whether there is a set of at most$k$ vertices whose removal turns $G$ into a graph of linear rankwidth at most$1$ and find such a vertex set if one exists. While the meta-theorem ofCourcelle, Makowsky, and Rotics implies that LRW1-Vertex Deletion can be solvedin time $f(k)\cdot n^3$ for some function $f$, it is not clear whether thisproblem allows a running time with a modest exponential function.  We first establish that LRW1-Vertex Deletion can be solved in time $8^k\cdotn^{\mathcal{O}(1)}$. The major obstacle to this end is how to handle a longinduced cycle as an obstruction. To fix this issue, we define necklace graphsand investigate their structural properties. Later, we reduce the polynomialfactor by refining the trivial branching step based on a cliquewidth expressionof a graph, and obtain an algorithm that runs in time $2^{\mathcal{O}(k)}\cdotn^4$. We also prove that the running time cannot be improved to $2^{o(k)}\cdotn^{\mathcal{O}(1)}$ under the Exponential Time Hypothesis assumption. Lastly,we show that the LRW1-Vertex Deletion problem admits a polynomial kernel.

An FPT algorithm and a polynomial kernel for Linear Rankwidth-1 Vertex Deletion