Counting Equitable k-Colorings in Graphs of Bounded Clique-Width
Holger Dell, Thore Husfeldt, Amir Nikabadi · arXiv (Cornell University) · 2009
For a graph G, a proper k-coloring of G is equitable if the sizes of any two color classes differ by at most one. The Equitable k-Coloring problem asks, for a given graph G and integer k, whether G admits an equitable k-coloring. Bodlaender and Fomin (Theoretical Computer Science 2005) showed that it is polynomial-time solvable on graphs of bounded treewidth, while it remains NP-hard on cographs, and thus on graphs of constant clique-width. Fellows et al. (Information and Computation 2011) showed that the problem becomes W[1]-hard when parameterized by tree-width (and hence clique-width) plus the number of colors k. We first show that, there exists an algorithm, given an integer k ≥ 1 and an n-vertex graph G together with a w-expression whose underlying unlabelled graph is G, computes the number of equitable k-colorings of G in time 2^O(k⋅w) ⋅ n^O(k). In particular, we show that for every fixed k, counting equitable k-colorings is polynomial-time solvable on graph classes of bounded clique-width, given a clique-width expression. We then show that, under SETH, the dependence on clique-width in this algorithm is essentially optimal. As a consequence, our results provide a fairly tight picture of the complexity of Equitable k-Coloring with respect to the combined parameter k+clique-width in the following sense: For variable k, the problem is W[1]-hard, however for every fixed integer k, it is polynomial-time solvable on graphs of bounded clique-width given a clique-width expression, and this remains true even for the counting version. Second, we refine our clique-width algorithm for the linear setting. We show that there exists an algorithm, given an integer k ≥ 1 and an n-vertex graph G together with a linear w-expression constructing G, computes the number of equitable k-colorings of G in time max{1,2^k-2}^w ⋅ n^{k+O(1)}. Thus, for bounded linear clique-width, we obtain a significantly sharper dependence on the width parameter than in the general clique-width case. Third, we consider a different structural restriction, namely the class of P_t-free graphs. A graph is called P_t-free if it does not contain the path on t vertices as an induced subgraph. This is a different setting from bounded clique-width; in particular, already P₅-free graphs have unbounded clique-width. Nevertheless, we show that for every P_t-free graph G, the number of equitable list 3-colorings of G can be computed in subexponential time.