Parameterized algorithms for load coloring problem

• We introduce the Parameterized Load Coloring Problem.
• The problem is to decide if a graph G has a 2-coloring.
• G has 2k edges half of which have both end-vertices red and half blue.
• We prove that the problem admits a kernel with at most 7k vertices.
• We prove that the problem has an algorithm of runtime O⁎(4k)O⁎(4k).

One way to state the Load Coloring Problem (LCP) is as follows. Let G=(V,E)G=(V,E) be graph and let f:V→{red,blue}f:V→{red,blue} be a 2-coloring. An edge e∈Ee∈E is called red (blue) if both end-vertices of e are red (blue). For a 2-coloring f  , let rf′ and bf′ be the number of red and blue edges and let μf(G)=min{rf′,bf′}. Let μ(G)μ(G) be the maximum of μf(G)μf(G) over all 2-colorings.We introduce the parameterized problem k  -LCP of deciding whether μ(G)⩾kμ(G)⩾k, where k is the parameter. We prove that this problem admits a kernel with at most 7k. Ahuja et al. (2007) proved that one can find an optimal 2-coloring on trees in polynomial time. We generalize this by showing that an optimal 2-coloring on graphs with tree decomposition of width t   can be found in time O⁎(2t)O⁎(2t). We also show that either G is a Yes-instance of k-LCP or the treewidth of G is at most 2k. Thus, k  -LCP can be solved in time O⁎(4k)O⁎(4k).