Destroying Multicolored Paths and Cycles in Edge-Colored Graphs

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.