Processing math: 88%

Niels Grüttemeier ; Christian Komusiewicz ; Jannik Schestag ; Frank Sommer - Destroying Bicolored P3s by Deleting Few Edges

dmtcs:6108 - Discrete Mathematics & Theoretical Computer Science, June 8, 2021, vol. 23 no. 1 - https://doi.org/10.46298/dmtcs.6108
Destroying Bicolored P3s by Deleting Few EdgesArticle

Authors: Niels Grüttemeier ; Christian Komusiewicz ORCID; Jannik Schestag ; Frank Sommer ORCID

    We introduce and study the Bicolored P3 Deletion problem defined as follows. The input is a graph G=(V,E) where the edge set E is partitioned into a set Er of red edges and a set Eb of blue edges. The question is whether we can delete at most k edges such that G does not contain a bicolored P3 as an induced subgraph. Here, a bicolored P3 is a path on three vertices with one blue and one red edge. We show that Bicolored P3 Deletion is NP-hard and cannot be solved in 2o(|V|+|E|) time on bounded-degree graphs if the ETH is true. Then, we show that Bicolored P3 Deletion is polynomial-time solvable when G does not contain a bicolored K3, that is, a triangle with edges of both colors. Moreover, we provide a polynomial-time algorithm for the case that G contains no blue P3, red P3, blue K3, and red K3. Finally, we show that Bicolored P3 Deletion can be solved in O(1.84k|V||E|) time and that it admits a kernel with O(kΔmin vertices, where \Delta is the maximum degree of G.


    Volume: vol. 23 no. 1
    Section: Graph Theory
    Published on: June 8, 2021
    Accepted on: May 7, 2021
    Submitted on: February 17, 2020
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 703 times.
    This article's PDF has been downloaded 350 times.