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 finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION(resp. ${\cal F}$-TM-DELETION) problem consists in, given a graph $G$ and aninteger $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as aminor (resp. topological minor). We are interested in the parameterizedcomplexity of both problems when the parameter is the treewidth of $G$, denotedby $tw$, and specifically in the cases where ${\cal F}$ contains a singleconnected planar graph $H$. We present algorithms running in time $2^{O(tw)}\cdot n^{O(1)}$, called single-exponential, when $H$ is either $P_3$, $P_4$,$C_4$, the paw, the chair, and the banner for both $\{H\}$-M-DELETION and$\{H\}$-TM-DELETION, and when $H=K_{1,i}$, with $i \geq 1$, for$\{H\}$-TM-DELETION. Some of these algorithms use the rank-based approachintroduced by Bodlaender et al. [Inform Comput, 2015]. This is the second of aseries of articles on this topic, and the results given here together withother ones allow us, in particular, to provide a tight dichotomy on thecomplexity of $\{H\}$-M-DELETION in terms of $H$.

Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms