Maximum cuts in edge-colored graphs

作     者：Faria, Luerbio Klein, Sulamita Sau, Ignasi Souza, Ueverton S. Sucupira, Rubens 

作者机构：Univ Estado Rio De Janeiro IME Rio De Janeiro Brazil Univ Fed Rio de Janeiro COPPE IM Rio De Janeiro Brazil Univ Montpellier LIRMM CNRS Montpellier France Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Fed Fluminense IC Niteroi RJ Brazil 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2020年第281卷

页      面：229-234页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：CNPq CAPES FAPERJ French project DEMOGRAPH [ANR-16-CE40-0028] French project ESIGMA [ANR-17-CE40-0028] 

主　　题：Colored cut Edge cut Maximum cut Planar graph Parameterized complexity Polynomial kernel 

摘      要：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. (c) 2019 Elsevier B.V. All rights reserved.