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 Graphs

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

We study the computational complexity of $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ 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 $\ell$ 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_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion are NP-hard for each non-trivial combination of $c$ and $\ell$. 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 $P_4$ 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