Maximum cuts in edge-colored graphs

被引：4

作者：

Faria, Luerbio ^{[1
]}

Klein, Sulamita ^{[2
]}

Sau, Ignasi ^{[3
,4
]}

Souza, Ueverton S. ^{[5
]}

Sucupira, Rubens ^{[1
,2
]}

机构：

[1] Univ Estado Rio De Janeiro, IME, Rio De Janeiro, Brazil

[2] Univ Fed Rio de Janeiro, COPPE, IM, Rio De Janeiro, Brazil

[3] Univ Montpellier, LIRMM, CNRS, Montpellier, France

[4] Univ Fed Ceara, Dept Matemat, Fortaleza, Ceara, Brazil

[5] Univ Fed Fluminense, IC, Niteroi, RJ, Brazil

来源：

DISCRETE APPLIED MATHEMATICS | 2020年 / 281卷

关键词：

Colored cut; Edge cut; Maximum cut; Planar graph; Parameterized complexity; Polynomial kernel; S-T CUT; LABEL; ALGORITHMS; COMPLEXITY;

D O I：

10.1016/j.dam.2019.02.038

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：229 / 234

页数：6