Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs

In the NP-hard Colored ( s , t )- Cut problem, the input is a graph G = ( V , E ) together with an edge-coloring ℓ : E → C , two vertices s and t , and a number k . The question is whether there is a set S ⊆ C of at most k colors such that deleting every edge with a color from S destroys all paths b...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2022-10, Vol.66 (5), p.1019-1045
Main Authors: Morawietz, Nils, Grüttemeier, Niels, Komusiewicz, Christian, Sommer, Frank
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Communication
Computer Science
Graph coloring
Graph theory
Graphs
Parameterization
Parameters
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the NP-hard Colored ( s , t )- Cut problem, the input is a graph G = ( V , E ) together with an edge-coloring ℓ : E → C , two vertices s and t , and a number k . The question is whether there is a set S ⊆ 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 )- Cut . First, we consider parameters related to the structure of G . For example, we study parameterization by the number ξ i of edge deletions that are needed to transform G into a graph with maximum degree i . We show that Colored ( s , t )- Cut is W[2]-hard when parameterized by ξ 3 , but fixed-parameter tractable when parameterized by ξ 2 . Second, we consider parameters related to the coloring ℓ . 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 rare edge colors.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-022-10101-z