On the complexity of edge-colored subgraph partitioning problems in network optimization

X. Zhang, Zanbo Zhang, Haitze J. Broersma, Xuelian Wen

Abstract

Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph G = (V,E), a subgraph H is said to be monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition V(G). We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph G is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln |V(G)| + 1.
Original languageUndefined
Pages (from-to)227-244
Number of pages18
JournalDiscrete mathematics and theoretical computer science
Volume17
Issue number3
StatePublished - Jul 2016

Fingerprint

Diamonds
Computational complexity
Color
Operations research
Information science
Graph theory
Approximation algorithms
Structural properties

Keywords

  • EWI-27084
  • Partition
  • MSC-05C
  • IR-100738
  • METIS-318463
  • Network optimization
  • Multicolored cycle
  • Monochromatic clique
  • Forbidden induced subgraphs

Cite this

Zhang, X.; Zhang, Zanbo; Broersma, Haitze J.; Wen, Xuelian / On the complexity of edge-colored subgraph partitioning problems in network optimization.

In: Discrete mathematics and theoretical computer science, Vol. 17, No. 3, 07.2016, p. 227-244.

Research output: Scientific - peer-reviewArticle

@article{0c211d70b5664cdfb1a020e2acd6e6c1,
title = "On the complexity of edge-colored subgraph partitioning problems in network optimization",
abstract = "Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph G = (V,E), a subgraph H is said to be monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition V(G). We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph G is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln |V(G)| + 1.",
keywords = "EWI-27084, Partition, MSC-05C, IR-100738, METIS-318463, Network optimization, Multicolored cycle, Monochromatic clique, Forbidden induced subgraphs",
author = "X. Zhang and Zanbo Zhang and Broersma, {Haitze J.} and Xuelian Wen",
note = "eemcs-eprint-27084",
year = "2016",
month = "7",
volume = "17",
pages = "227--244",
journal = "Discrete mathematics and theoretical computer science",
issn = "1462-7264",
publisher = "Maison de l'informatique et des mathematiques discretes",
number = "3",

}

On the complexity of edge-colored subgraph partitioning problems in network optimization. / Zhang, X.; Zhang, Zanbo; Broersma, Haitze J.; Wen, Xuelian.

In: Discrete mathematics and theoretical computer science, Vol. 17, No. 3, 07.2016, p. 227-244.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - On the complexity of edge-colored subgraph partitioning problems in network optimization

AU - Zhang,X.

AU - Zhang,Zanbo

AU - Broersma,Haitze J.

AU - Wen,Xuelian

N1 - eemcs-eprint-27084

PY - 2016/7

Y1 - 2016/7

N2 - Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph G = (V,E), a subgraph H is said to be monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition V(G). We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph G is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln |V(G)| + 1.

AB - Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph G = (V,E), a subgraph H is said to be monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition V(G). We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph G is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln |V(G)| + 1.

KW - EWI-27084

KW - Partition

KW - MSC-05C

KW - IR-100738

KW - METIS-318463

KW - Network optimization

KW - Multicolored cycle

KW - Monochromatic clique

KW - Forbidden induced subgraphs

M3 - Article

VL - 17

SP - 227

EP - 244

JO - Discrete mathematics and theoretical computer science

T2 - Discrete mathematics and theoretical computer science

JF - Discrete mathematics and theoretical computer science

SN - 1462-7264

IS - 3

ER -