On the complexity of edge-colored subgraph partitioning problems in network optimization
Xiaoyan Zhang, Zan-Bo Zhang, Hajo 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.
Full Text: PDF PostScript