Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
verfasst von : Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, Frank Sommer
Erschienen in: SOFSEM 2020: Theory and Practice of Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In the Colored \((s,t)\hbox {-}{\textsc {cut}}\) problem, the input is a graph \(G=(V,E)\) together with an edge-coloring \(\ell :E\rightarrow C\), two vertices s and t, and a number k. The question is whether there is a set \(S\subseteq C\) of at most k colors, such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored \((s,t)\hbox {-}{\textsc {cut}}\). First, we consider parameters related to the structure of G. For example, we study parameterization by the number \(\xi _i\) of edge deletions that are needed to transform G into a graph with maximum degree i. We show that Colored \((s,t)\hbox {-}{\textsc {cut}}\) is \(\mathrm {W}[2]\)-hard when parameterized by \(\xi _3\), but fixed-parameter tractable when parameterized by \(\xi _2\). Second, we consider parameters related to the coloring \(\ell \). We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C| and provide a linear-size problem kernel for a parameter related to the number of edges with a rare edge color.