Approximating chromatic sum coloring of bipartite graphs in expected polynomial time

A. S. Asratyan^a, N. N. Kuzyurin<sup>b

a</sup> Linkopings Universitet, Department of Mathematics
^b Institute for System Programming of the Russian Academy of Sciences

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.

Language: English

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

Bibliographic databases:

•