Maximum cuts in edge-colored graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Discrete Applied Mathematics Year : 2020

Maximum cuts in edge-colored graphs


The input of the Maximum Colored Cut problem consists of a graph G = (V, E) with an edge-coloring c : E → {1, 2, 3,. .. , p} and a positive integer k, and the question is whether G has a nontrivial edge cut using at least k colors. The Colorful Cut problem has the same input but asks for a nontrivial edge cut using all p colors. Unlike what happens for the classical Maximum Cut problem, we prove that both problems are NP-complete even on complete, planar, or bounded treewidth graphs. Furthermore, we prove that Colorful Cut is NP-complete even when each color class induces a clique of size at most three, but is trivially solvable when each color induces an edge. On the positive side, we prove that Maximum Colored Cut is fixed-parameter tractable when parameterized by either k or p, by constructing a cubic kernel in both cases.
Fichier principal
Vignette du fichier
DA9757-R1.pdf (357.63 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-02989852 , version 1 (05-11-2020)



Luerbio Faria, Sulamita Klein, Ignasi Sau, Uéverton dos Santos Souza, Rubens Sucupira. Maximum cuts in edge-colored graphs. Discrete Applied Mathematics, 2020, 281, pp.229-234. ⟨10.1016/j.dam.2019.02.038⟩. ⟨lirmm-02989852⟩
24 View
62 Download



Gmail Facebook X LinkedIn More