Destroying Multicolored Paths and Cycles in Edge-Colored Graphs
share
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 P_4 Deletion that can be solved in polynomial time.
READ FULL TEXT