Parameterized Algorithms for Load Coloring Problem

الأصل · EN

One way to state the Load Coloring Problem (LCP) is as follows. Let G=(V,E) be graph and let f:V→ { red, blue} be a 2-coloring. An edge e∈ E is called red (blue) if both end-vertices of e are red (blue). For a 2-coloring f, let r'f and b'f be the number of red and blue edges and let μf(G)={r'f,b'f}. Let μ(G) be the maximum of μf(G) over all 2-colorings. We introduce the parameterized problem k-LCP of deciding whether μ(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*(2ᵗ). 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*(4ᵏ).