Proceedings of ISP RAS


Approximating Chromatic Sum Coloring of Bipartite Graphs in Expected Polynomial Time

A.S. Asratian (Linkopings Universitet, Sweden), N.N. Kuzyurin (ISP RAS, Moscow)

Abstract

It is known that if complexity class P is not equal to NP the sum coloring problem cannot be approximated within 1+epsilon for some positive constant epsilon.
We consider finite, undirected graphs without loops and multiple edges.
Let G=(V,E) be a graph. By a coloring of G we mean a mapping c of V to the numbers 1,2, ..., |V| . A coloring c is proper if c(v) is not equal to c(u) whenever the vertices u and v are adjacent.
Let S(G,c) is the sum_of c(v) over all vertices v. By a chromatic sum of G we mean the number S(G)=min S(G,c) where minimum is taken over all proper colorings c of G.
The problem of finding S(G) is called the sum coloring problem.
It was shown that the sum coloring problem is NP-complete.
A graph G is called bipartite if the set of vertices of G can be partitioned into
two non-empty sets V1 and V2 such that every edge of G has one end in each of the sets.
For a number b, we say that an algorithm A approximates the chromatic sum within factor b over graphs on n vertices, if for every such graph G the algorithm A outputs a proper coloring c, such that S(G,c) is not greater than b S(G).
It is known that there exists 27/26-approximation polynomial algorithm for the chromatic SUM COLORING PROBLEM on any bipartite graph. On the other side, it was shown that here exists epsilon>0, such that there is no (1+epsilon)-approximation polynomial algorithm for the sum coloring problem on bipartite graphs, unless P is not equal to NP.
In this paper we consider the problem of developing an (1+epsilon)-approximation algorithm for the sum coloring of bipartite graphs which is polynomial in the average case for arbitrary small epsilon. We prove the existence of such algorithm.

Keywords

sum coloring problem, bipartite graphs, expected polynomial time

Edition

Proceedings of the Institute for System Programming, vol. 27, issue 5, 2015, pp. 191-198.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2015-27(5)-11

Full text of the paper in pdf Back to the contents of the volume