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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For a given graph $G$, a depth-first search (DFS) tree $T$ of $G$ is an$r$-rooted spanning tree such that every edge of $G$ is either an edge of $T$or is between a \textit{descendant} and an \textit{ancestor} in $T$. A graph$G$ together with a DFS tree is called a \textit{lineal topology} $\mathcal{T}= (G, r, T)$. Sam et al. (2023) initiated study of the parameterized complexityof the \textsc{Min-LLT} and \textsc{Max-LLT} problems which ask, given a graph$G$ and an integer $k\geq 0$, whether $G$ has a DFS tree with at most $k$ andat least $k$ leaves, respectively. Particularly, they showed that for the dualparameterization, where the tasks are to find DFS trees with at least $n-k$ andat most $n-k$ leaves, respectively, these problems are fixed-parametertractable when parameterized by $k$. However, the proofs were based onCourcelle's theorem, thereby making the running times a tower of exponentials.We prove that both problems admit polynomial kernels with $\Oh(k^3)$ vertices.In particular, this implies FPT algorithms running in $k^{\Oh(k)}\cdotn^{O(1)}$ time. We achieve these results by making use of a $\Oh(k)$-sizedvertex cover structure associated with each problem. This also allows us todemonstrate polynomial kernels for \textsc{Min-LLT} and \textsc{Max-LLT} forthe structural parameterization by the vertex cover number.

Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves