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

We give the first linear kernels for the (Connected) Dominating Set problemson H-topological minor free graphs. We prove the existence of polynomial timealgorithms that, for a given H-topological-minor-free graph G and a positiveinteger k, output an H-topological-minor-free graph G' on O(k) vertices suchthat G has a (connected) dominating set of size k iff G' has one. Our resultsextend the known classes of graphs on which the Dominating Set and ConnectedDominating Set problems admit linear kernels. Prior to our work, it was knownthat these problems admit linear kernels on graphs excluding a fixed apex graphH as a minor. Moreover, for Dominating Set, a kernel of size kc(H), where c(H)is a constant depending on the size of H, follows from a more general result onthe kernelization of Dominating Set on graphs of bounded degeneracy. Alon andGutner explicitly asked whether one can obtain a linear kernel for DominatingSet on H-minor-free graphs. We answer this question in the affirmative and infact prove a more general result. For Connected Dominating Set no polynomialkernel even on H-minor-free graphs was known prior to our work. On the negativeside, it is known that Connected Dominating Set on 2-degenerated graphs doesnot admit a polynomial kernel unless coNP $\subseteq$ NP/poly. Ourkernelization algorithm is based on a non-trivial combination of the followingingredients The structural theorem of Grohe and Marx [STOC 2012] for graphsexcluding a fixed graph H as a topological minor; A novel notion ofprotrusions, different than the one defined in [FOCS 2009]; Our results arebased on a generic reduction rule that produces an equivalent instance (in casethe input graph is H-minor-free) of the problem, with treewidth $O(\sqrt{k})$.The application of this rule in a divide-and-conquer fashion, together with thenew notion of protrusions, gives us the linear kernels.

Kernels for (connected) Dominating Set on graphs with Excluded Topological subgraphs