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 introduce and study the Bicolored $P_3$ Deletion problem defined asfollows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitionedinto a set $E_r$ of red edges and a set $E_b$ of blue edges. The question iswhether we can delete at most $k$ edges such that $G$ does not contain abicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path onthree vertices with one blue and one red edge. We show that Bicolored $P_3$Deletion is NP-hard and cannot be solved in $2^{o(|V|+|E|)}$ time onbounded-degree graphs if the ETH is true. Then, we show that Bicolored $P_3$Deletion is polynomial-time solvable when $G$ does not contain a bicolored$K_3$, that is, a triangle with edges of both colors. Moreover, we provide apolynomial-time algorithm for the case that $G$ contains no blue $P_3$, red$P_3$, blue $K_3$, and red $K_3$. Finally, we show that Bicolored $P_3$Deletion can be solved in $ O(1.84^k\cdot |V| \cdot |E|)$ time and that itadmits a kernel with $ O(k\Delta\min(k,\Delta))$ vertices, where $\Delta$ isthe maximum degree of $G$.

Destroying Bicolored $P_3$s by Deleting Few Edges