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

For a graph property $\Pi$, Subgraph Complementation to $\Pi$ is the problemto find whether there is a subset $S$ of vertices of the input graph $G$ suchthat modifying $G$ by complementing the subgraph induced by $S$ results in agraph satisfying the property $\Pi$. We prove that the problem of SubgraphComplementation to $T$-free graphs is NP-Complete, for $T$ being a tree, exceptfor 41 trees of at most 13 vertices (a graph is $T$-free if it does not containany induced copies of $T$). This result, along with the 4 known polynomial-timesolvable cases (when $T$ is a path on at most 4 vertices), leaves behind 37open cases. Further, we prove that these hard problems do not admit anysubexponential-time algorithms, assuming the Exponential Time Hypothesis. As anadditional result, we obtain that Subgraph Complementation to paw-free graphscan be solved in polynomial-time.

Cutting a tree with Subgraph Complementation is hard, except for some small trees