Skip to Main content Skip to Navigation
Journal articles

Maximum cuts in edge-colored graphs

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02989852
Contributor : Ignasi Sau <>
Submitted on : Thursday, November 5, 2020 - 12:20:29 PM
Last modification on : Friday, November 6, 2020 - 11:22:13 AM
Long-term archiving on: : Saturday, February 6, 2021 - 7:10:35 PM

File

DA9757-R1.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

22

Files downloads

24