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

The notion of $\mathcal{H}$-treewidth, where $\mathcal{H}$ is a hereditarygraph class, was recently introduced as a generalization of the treewidth of anundirected graph. Roughly speaking, a graph of $\mathcal{H}$-treewidth at most$k$ can be decomposed into (arbitrarily large) $\mathcal{H}$-subgraphs whichinteract only through vertex sets of size $O(k)$ which can be organized in atree-like fashion. $\mathcal{H}$-treewidth can be used as a hybridparameterization to develop fixed-parameter tractable algorithms for$\mathcal{H}$-deletion problems, which ask to find a minimum vertex set whoseremoval from a given graph $G$ turns it into a member of $\mathcal{H}$. Thebottleneck in the current parameterized algorithms lies in the computation ofsuitable tree $\mathcal{H}$-decompositions.  We present FPT approximation algorithms to compute tree$\mathcal{H}$-decompositions for hereditary and union-closed graph classes$\mathcal{H}$. Given a graph of $\mathcal{H}$-treewidth $k$, we can compute a5-approximate tree $\mathcal{H}$-decomposition in time $f(O(k)) \cdot n^{O(1)}$whenever $\mathcal{H}$-deletion parameterized by solution size can be solved intime $f(k) \cdot n^{O(1)}$ for some function $f(k) \geq 2^k$. The current-bestalgorithms either achieve an approximation factor of $k^{O(1)}$ or constructoptimal decompositions while suffering from non-uniformity with unknownparameter dependence. Using these decompositions, we obtain algorithms solvingOdd Cycle Transversal in time $2^{O(k)} \cdot n^{O(1)}$ parameterized by$\mathsf{bipartite}$-treewidth and Vertex Planarization in time $2^{O(k \logk)} \cdot n^{O(1)}$ parameterized by $\mathsf{planar}$-treewidth, showing thatthese can be as fast as the solution-size parameterizations and giving thefirst ETH-tight algorithms for parameterizations by hybrid width measures.

5-Approximation for $\mathcal{H}$-Treewidth Essentially as Fast as $\mathcal{H}$-Deletion Parameterized by Solution Size