Parameterized Algorithms for Load Coloring Problem

Abstract

One way to state the Load Coloring Problem (LCP) is as follows. Let $G=(V,E)$ be graph and let $f:V\to \{\mathrm{red},\mathrm{blue}\}$ be a 2-coloring. An edge $e\in E$ is called red (blue) if both end-vertices of $e$ are red (blue). For a 2-coloring $f$, let $r_f^{\prime }$ and $b_f^{\prime }$ be the number of red and blue edges and let $\hat{I}{¼}_f(G)=\min \{r_f^{\prime },b_f^{\prime }\}$. Let $\hat{I}¼(G)$ be the maximum of $\hat{I}{¼}_f(G)$ over all 2-colorings. We introduce the parameterized problem $k$-LCP of deciding whether $\hat{I}¼(G)\ge 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^{\ast }(2^t)$. 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^{\ast }(4^k).$