Discrete Mathematics & Theoretical Computer Science 
We introduce and study the Bicolored $P_3$ Deletion problem defined as follows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitioned into a set $E_r$ of red edges and a set $E_b$ of blue edges. The question is whether we can delete at most $k$ edges such that $G$ does not contain a bicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path on three vertices with one blue and one red edge. We show that Bicolored $P_3$ Deletion is NPhard and cannot be solved in $2^{o(V+E)}$ time on boundeddegree graphs if the ETH is true. Then, we show that Bicolored $P_3$ Deletion is polynomialtime solvable when $G$ does not contain a bicolored $K_3$, that is, a triangle with edges of both colors. Moreover, we provide a polynomialtime 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 it admits a kernel with $ O(k\Delta\min(k,\Delta))$ vertices, where $\Delta$ is the maximum degree of $G$.
Source : ScholeXplorer
IsRelatedTo ARXIV 1712.06442 Source : ScholeXplorer IsRelatedTo DOI 10.1073/pnas.1412770112 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1712.06442 Source : ScholeXplorer IsRelatedTo PMC PMC4343152 Source : ScholeXplorer IsRelatedTo PMID 25646426
