Report
Destroying Bicolored $P_3$s by Deleting Few Edges
| العنوان: | Destroying Bicolored $P_3$s by Deleting Few Edges |
|---|---|
| المؤلفون: | Grüttemeier, Niels, Komusiewicz, Christian, Schestag, Jannik, Sommer, Frank |
| المصدر: | Discrete Mathematics & Theoretical Computer Science, vol. 23 no. 1, Graph Theory (June 8, 2021) dmtcs:6108 |
| سنة النشر: | 2019 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Computer Science - Discrete Mathematics, Mathematics - Combinatorics |
| الوصف: | 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 |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.46298/dmtcs.6108 |
| URL الوصول: | http://arxiv.org/abs/1901.03627 |
| رقم الانضمام: | edsarx.1901.03627 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.46298/dmtcs.6108 |
|---|