{"docId":7553,"paperId":6108,"url":"https:\/\/dmtcs.episciences.org\/6108","doi":"10.46298\/dmtcs.6108","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":418,"name":"vol. 23 no. 1"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"1901.03627","repositoryVersion":4,"repositoryLink":"https:\/\/arxiv.org\/abs\/1901.03627v4","dateSubmitted":"2020-02-17 10:32:22","dateAccepted":"2021-05-07 08:58:25","datePublished":"2021-06-08 10:23:01","titles":["Destroying Bicolored $P_3$s by Deleting Few Edges"],"authors":["Gr\u00fcttemeier, Niels","Komusiewicz, Christian","Schestag, Jannik","Sommer, Frank"],"abstracts":["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 NP-hard and cannot be solved in $2^{o(|V|+|E|)}$ time on bounded-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 a polynomial-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 it admits a kernel with $ O(k\\Delta\\min(k,\\Delta))$ vertices, where $\\Delta$ is the maximum degree of $G$.","Comment: 25 pages"],"keywords":["Computer Science - Data Structures and Algorithms","Computer Science - Discrete Mathematics","Mathematics - Combinatorics"]}