Destroying Multicolored Paths and Cycles in Edge-Colored Graphs

DOI10.46298/DMTCS.7636arXiv2104.03138OpenAlexW3150086802MaRDI QIDQ6131783FDOQ6131783

Niels Grüttemeier, Christian Komusiewicz, Frank Sommer, Author name not available (Why is that?)

Publication date: 18 April 2024

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Abstract: We study the computational complexity of $c$-Colored $P_{e}ll$ Deletion and $c$-Colored $C_{e}ll$ 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_{e}ll$ Deletion and $c$-Colored $C_{e}ll$ 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.

Full work available at URL: https://arxiv.org/abs/2104.03138

zbMATH Keywords

parameterized complexityNP-hard problemedge-colored graphsgraph modification

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

This page was built for publication: Destroying Multicolored Paths and Cycles in Edge-Colored Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131783)