In terms of laymen
Consider a network whose connections are colored red or blue, and suppose we want to remove only a few connections so that no path through three vertices uses both colors. This paper shows that finding such a small set of deletions is difficult in general, but gives faster algorithms, useful preprocessing techniques, and special graph classes on which the problem can be solved efficiently.
In Laiensprache (German translation)
Betrachten wir ein Netzwerk, dessen Verbindungen rot oder blau gefärbt sind. Gesucht sind möglichst wenige Verbindungen, die entfernt werden müssen, sodass kein Pfad über drei Knoten mehr beide Farben verwendet. Diese Arbeit zeigt, dass das Finden einer solchen kleinen Menge im Allgemeinen schwierig ist, entwickelt aber schnellere Algorithmen und nützliche Vorverarbeitungstechniken und identifiziert spezielle Netzwerkklassen, für die sich das Problem effizient lösen lässt.
Abstract
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. We also 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 \(\mathcal{O}(1.84^k \cdot |V | \cdot |E|)\) time and that it admits a kernel with \(\mathcal{O}(k \Delta \min(k, \Delta))\) vertices, where \(\Delta\) is the maximum degree of \(G\).
@article{gruttemeier2021destroying,
title = {{Destroying Bicolored P3s by Deleting Few Edges}},
author = {Gr{\"u}ttemeier, Niels and Komusiewicz, Christian and Schestag, Jannik and Sommer, Frank},
journal = {Discrete Mathematics \& Theoretical Computer Science},
volume = {23},
number = {1},
year = {2021},
publisher = {Episciences.org},
doi = {10.46298/dmtcs.6108}
}
