New algorithms for the minimum coloring cut problem

• Author: Thiago Gouveia Silva,Fábio Protti,Gilberto Farias Sousa Filho,Augusto Bordini
• Published date: 01 September 2019
• Date: 01 September 2019
• DOI: http://doi.org/10.1111/itor.12494

Intl. Trans. in Op. Res. 26 (2019) 1868–1883

DOI: 10.1111/itor.12494

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

New algorithms for the minimum coloring cut problem

Augusto Bordinia,b,F

´

abio Prottia, Thiago Gouveia da Silvaa,c and Gilberto Farias de

Sousa Filhod

aUniversidade FederalFluminense, Niter ´

oi, RJ, Brazil

bPETROBRAS, Rio de Janeiro, RJ, Brazil

cInstituto Federal de Educac¸˜

ao, Ciˆ

encia e Tecnologia da Para´

ıba, Jo˜

ao Pessoa, PB, Brazil

dUniversidade Federalda Para´

ıba, Jo˜

ao Pessoa, PB, Brazil

E-mail: gutocnet@ic.uff.br [Bordini];fabio@ic.uff.br [Protti]; thiago.gouveia@ifpb.edu.br [Silva];

gilberto@ci.ufpb.br [Sousa Filho]

Received 27 March 2017; receivedin revised form 6 October 2017; accepted 10 November 2017

Abstract

The minimum coloring cut problem is defined as follows: given a connected graph Gwith colored edges,find

an edge cut Eof G(a minimal set of edges whose removal renders the graph disconnected) such that the

number of colors used by the edges in Eis minimum. In this work, we present two approaches based on

variable neighborhood searchto solve this problem. Our algorithms are able to find all the optimum solutions

described in the literature.

Keywords: minimum coloring cut problem; combinatorial optimization; graph theory; variable neighborhood search;

label cut problem

1. Introduction

The minimum coloring cut problem (MCCP) has as input a connected (undirected) graph G=

(V,E), with colored (or labeled) edges. Each color is assigned to one or more edges, but each edge

ehas a unique color c(e). The aim of the MCCP is to find an edge cut Eof G(a minimal set Eof

edges such that G=(V,E\E)is disconnected) with the following property: the set of colors used

by the edge s in Ehas minimum size. Formally:

Minimum coloring cut problem

Input: a connected (undirected) graph G=(V,E,C)such that Vis the set of nodes of G,Eis

the set of edges of G,andC={c(e)|e∈E}is the set of colors (or edge labels).

Goal: Find a subset E⊆Esuch that G=(V,E\E)is disconnected and the set of colors

C={c(e)|e∈E}is minimized. Figure 1 shows a simple example.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

A. Bordini et al. / Intl. Trans.in Op. Res. 26 (2019) 1868–1883 1869

Fig. 1. In the above graph,colors are represented by labels in the set {1,2,3}. The cut consisting of the dashed edges is

an optimal solution of the MCCP. The value of the optimal solution is 2 because the removalof any subset of edges with

only one color does not disconnect the graph.

Note that if all the edge colors are distinct then the MCCP amounts to finding a usual minimum

cut, a task that can be easily performed in polynomial time using max-flow algorithms. However,

the complexity of the MCCP still remains as a theoretical open question. Intuitively, the MCCP is

unlikely to be solvable in polynomial time because the related problem of finding an s-tcut with

the minimum number of colors is NP-hard (Coudert et al., 2007). This fully justifies the design of

heuristic algorithms to solve the MCCP.

Colored cut problems are related to the vulnerability of multilayer networks since they pro-

vide tight lower bounds on the number of failures that can disconnect totally or partially a net-

work (Coudert et al., 2016).

The minimum color s-tcut problem (MCstCP) is closely related to the MCCP. The input of

the MCstCP consists of a connected edge-colored graph G=(V,E)and two nodes s,t∈V,and

its objective is to find the minimum number of colors whose removal separates sand tin the

remaining graph (where “removing a color” means removing all the edges with that color). Jha

et al. (2002) observed that the MCstCP is NP-hard via a simple reduction from the minimum

hitting set problem. Coudert et al. (2007) presented another proof of the NP-hardness of the

MCstCP, as well as approximation hardness results.

The papers by Coudert et al. (2007, 2016) approach the MCCP and MCstCP with the goal

of measuring the network’s capability of remaining connected when sets of links share risks. For

instance, in a WiFi network, an attacker could drop all links on a certain frequency by adding a

strong noise signal to it. Another exampleis a case when two links use the same physical environment.

Another potential application of the MCCP is in transportation planning systems, where nodes

represent locations served by bus and edge colors represent bus companies. In this case, a solution

of the MCCP gives the minimum number of companies that must stop working in order to create

pairs of locations not reachableby bus from one another. Such application is moresuitably modeled

by allowing a multigraph as the input of the MCCP, since two locations can be connected by bus

services offered by more than a single company.

Zhang (2014) shows that the MCCP can be solved in polynomial time when the input graph is

planar, has bounded treewidth, or has a small value of fmax (the maximum number of edges a color

is assigned).

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies