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

We revisit recent developments for the Maximum Weight Independent Set problemin graphs excluding a subdivided claw $S_{t,t,t}$ as an induced subgraph[Chudnovsky, Pilipczuk, Pilipczuk, Thomass\'{e}, SODA 2020] and provide asubexponential-time algorithm with improved running time$2^{\mathcal{O}(\sqrt{n}\log n)}$ and a quasipolynomial-time approximationscheme with improved running time $2^{\mathcal{O}(\varepsilon^{-1} \log^{5}n)}$.  The Gy\'arf\'as' path argument, a powerful tool that is the main buildingblock for many algorithms in $P_t$-free graphs, ensures that given an$n$-vertex $P_t$-free graph, in polynomial time we can find a set $P$ of atmost $t-1$ vertices, such that every connected component of $G-N[P]$ has atmost $n/2$ vertices. Our main technical contribution is an analog of thisresult for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph,in polynomial time we can find a set $P$ of $\mathcal{O}(t \log n)$ verticesand an extended strip decomposition (an appropriate analog of the decompositioninto connected components) of $G-N[P]$ such that every particle (an appropriateanalog of a connected component to recurse on) of the said extended stripdecomposition has at most $n/2$ vertices.

Max Weight Independent Set in graphs with no long claws: An analog of the Gy\'arf\'as' path argument