Nils Jakob Eckstein ; Niels Grüttemeier ; Christian Komusiewicz ; Frank Sommer - Destroying Multicolored Paths and Cycles in Edge-Colored Graphs

dmtcs:7636 - Discrete Mathematics & Theoretical Computer Science, March 3, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.7636
Destroying Multicolored Paths and Cycles in Edge-Colored GraphsArticle

Authors: Nils Jakob Eckstein ; Niels Grüttemeier ; Christian Komusiewicz ; Frank Sommer

    We study the computational complexity of c-Colored P Deletion and c-Colored C Deletion. In these problems, one is given a c-edge-colored graph and wants to destroy all induced c-colored paths or cycles, respectively, on vertices by deleting at most k edges. Herein, a path or cycle is c-colored if it contains edges of c distinct colors. We show that c-Colored P Deletion and c-Colored C Deletion are NP-hard for each non-trivial combination of c and . We then analyze the parameterized complexity of these problems. We extend the notion of neighborhood diversity to edge-colored graphs and show that both problems are fixed-parameter tractable with respect to the colored neighborhood diversity of the input graph. We also provide hardness results to outline the limits of parameterization by the standard parameter solution size k. Finally, we consider bicolored input graphs and show a special case of 2-Colored P4 Deletion that can be solved in polynomial time.


    Volume: vol. 25:1
    Section: Graph Theory
    Published on: March 3, 2023
    Accepted on: February 17, 2023
    Submitted on: June 30, 2021
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Discrete Mathematics,Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 898 times.
    This article's PDF has been downloaded 723 times.