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 consider the following problem: for a given graph G and two integers k andd, can we apply a fixed graph operation at most k times in order to reduce agiven graph parameter $\pi$ by at least d? We show that this problem is NP-hardwhen the parameter is the independence number and the graph operation is vertexdeletion or edge contraction, even for fixed d=1 and when restricted to chordalgraphs. We also give a polynomial time algorithm for bipartite graphs when theoperation is edge contraction, the parameter is the independence number and dis fixed. Further, we complete the complexity dichotomy on H-free graphs whenthe parameter is the clique number and the operation is edge contraction byshowing that this problem is NP-hard in ($C_3+P_1$)-free graphs even for fixedd=1. Our results answer several open questions stated in [Diner et al.,Theoretical Computer Science, 746, p. 49-72 (2012)].

Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number