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/

Zendy Plus

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

Zendy Tools

Zendy Open

In the Maximum Independent Set problem we are asked to find a set of pairwisenonadjacent vertices in a given graph with the maximum possible cardinality. Ingeneral graphs, this classical problem is known to be NP-hard and hard toapproximate within a factor of $n^{1-\varepsilon}$ for any $\varepsilon > 0$.Due to this, investigating the complexity of Maximum Independent Set in variousgraph classes in hope of finding better tractability results is an activeresearch direction.  In $H$-free graphs, that is, graphs not containing a fixed graph $H$ as aninduced subgraph, the problem is known to remain NP-hard and APX-hard whenever$H$ contains a cycle, a vertex of degree at least four, or two vertices ofdegree at least three in one connected component. For the remaining cases,where every component of $H$ is a path or a subdivided claw, the complexity ofMaximum Independent Set remains widely open, with only a handful ofpolynomial-time solvability results for small graphs $H$ such as $P_5$, $P_6$,the claw, or the fork.  We show that for every graph $H$ for which Maximum Independent Set is notknown to be APX-hard and SUBEXP-hard in $H$-free graphs, the problem admits aquasi-polynomial time approximation scheme and a subexponential-time exactalgorithm in this graph class. Our algorithm works also in the more generalweighted setting, where the input graph is supplied with a weight function onvertices and we are maximizing the total weight of an independent set.

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs