episciences.org_6108_1660006432
1660006432
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
06
08
2021
vol. 23 no. 1
Graph Theory
Destroying Bicolored $P_3$s by Deleting Few Edges
Niels
GrÃ¼ttemeier
Christian
Komusiewicz
Jannik
Schestag
Frank
Sommer
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$.
06
08
2021
6108
arXiv:1901.03627
10.48550/arXiv.1901.03627
https://arxiv.org/abs/1901.03627v3
https://arxiv.org/abs/1901.03627v2
10.46298/dmtcs.6108
https://dmtcs.episciences.org/6108

https://dmtcs.episciences.org/7553/pdf