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

Fomin and Villanger (STACS 2010) proved that Maximum Independent Set,Feedback Vertex Set, and more generally the problem of finding a maximuminduced subgraph of treewith at most a constant $t$, can be solved inpolynomial time on graph classes with polynomially many minimal separators. Weextend these results in two directions. Let $\Gpoly$ be the class of graphswith at most $\poly(n)$ minimal separators, for some polynomial $\poly$.  We show that the odd powers of a graph $G$ have at most as many minimalseparators as $G$. Consequently, \textsc{Distance-$d$ Independent Set}, whichconsists in finding maximum set of vertices at pairwise distance at least $d$,is polynomial on $\Gpoly$, for any even $d$. The problem is NP-hard on chordalgraphs for any odd $d \geq 3$.  We also provide polynomial algorithms for Connected Vertex Cover andConnected Feedback Vertex Set on subclasses of $\Gpoly$ including chordal andcircular-arc graphs, and we discuss variants of independent dominationproblems.

On Distance-$d$ Independent Set and other problems in graphs with few minimal separators