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

Dallard, Milani\v{c}, and \v{S}torgel [arXiv '22] ask if for every classexcluding a fixed planar graph $H$ as an induced minor, Maximum Independent Setcan be solved in polynomial time, and show that this is indeed the case when$H$ is any planar complete bipartite graph, or the 5-vertex clique minus oneedge, or minus two disjoint edges. A positive answer would constitute afar-reaching generalization of the state-of-the-art, when we currently do notknow if a polynomial-time algorithm exists when $H$ is the 7-vertex path.Relaxing tractability to the existence of a quasipolynomial-time algorithm, weknow substantially more. Indeed, quasipolynomial-time algorithms were recentlyobtained for the $t$-vertex cycle, $C_t$ [Gartland et al., STOC '21] and thedisjoint union of $t$ triangles, $tC_3$ [Bonamy et al., SODA '23].  We give, for every integer $t$, a polynomial-time algorithm running in$n^{O(t^5)}$ when $H$ is the friendship graph $K_1 + tK_2$ ($t$ disjoint edgesplus a vertex fully adjacent to them), and a quasipolynomial-time algorithmrunning in $n^{O(t^2 \log n)+t^{O(1)}}$ when $H$ is $tC_3 \uplus C_4$ (thedisjoint union of $t$ triangles and a 4-vertex cycle). The former extends aclassical result on graphs excluding $tK_2$ as an induced subgraph [Alekseev,DAM '07], while the latter extends Bonamy et al.'s result.

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$