B-chromatic number: Beyond NP-hardness

Fahad Panolan

, Geevarghese Philip

, and Saket Saurabh

1 Institute of Mathematical Sciences, Chennai, India {fahad|saket}@imsc.res.in

2 Chennai Mathematical Institute, India [email protected]

3 University of Bergen, Norway

Abstract

The b-chromatic number of a graphG,χb(G), is the largest integerksuch thatGhas ak-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the b-Chromatic Numberproblem, the objective is to decide whetherχb(G)≥k. Testing whetherχb(G) = ∆(G) + 1, where ∆(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvíl, Tuza and Voigt, WG 2002). In this paper we study b-Chromatic Numberin the realm of parameterized complexity and exact exponential time algorithms. We show that b-Chromatic Number is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k= ∆(G) + 1, we design an algorithm for b-Chromatic Number running in time 2^O(k2logk)n^O(1). Finally, we show that b-Chromatic Numberfor ann-vertex graph can be solved in timeO(3ⁿn⁴logn).

1998 ACM Subject Classification F.2 Analysis of Algorithms and Problem Complexity Keywords and phrases b-chromatic number, exact algorithm, parameterized complexity Digital Object Identifier 10.4230/LIPIcs.IPEC.2015.389

1 Introduction

Graph coloring (proper vertex coloring), is an assignment of colors to the vertices of a graph such that no edge connects two identically colored vertices. In other words graph coloring is a partition of vertex set into independent sets. A proper vertex coloring usingk colors is called ak-vertex coloring. The least number of colors required for a proper vertex coloring of a graphGis called the chromatic numberofG. The most common question about graph coloring is–“what is the chromatic number of a graph”. This question has got lots of attention in graph theory and algorithms. The study of graph coloring leads to the four color theorem in planar graphs by Appel and Haken [1], study of chromatic polynomial introduced by Birkhoff, which was generalised to the Tutte polynomial by Tutte, etc. Graph coloring has been studied as an algorithmic problem since the early 1970s. The chromatic number problem is one of Karp’s 21 NP-complete problems from 1972 [11]. An exact algorithm to compute the chromatic number of a graph dates back to 1976. Lawler [13] gave an algorithm for finding chromatic number running in time 2.4423ⁿn^O(1). Finally, after 30 years, using the principle of inclusion-exclusion Björklund et al. [2] gave an algorithm for chromatic number

∗ Supported by the European Research Council (ERC) via grants Rigorous Theory of Preprocessing, reference 267959 and PARAPPROX, reference 306992; and by the Department of Science and Technology (DST), Government of India, the German Federal Ministry of Education and Research (BMBF), and the Max Planck Society (MPG), via the Indo-German Max Planck Center for Computer Science (IMPECS).

© Fahad Panolan, Geevarghese Philip, and Saket Saurabh;

problem running in time 2ⁿn^O(1). This is still the fastest known exact algorithm to compute the chromatic number of a graph.

Not only finding chromatic number but also different variations of graph coloring has been studied in the literature. Acomplete coloring of a graphGis a proper vertex coloring such that no two color classes together form an independent set. The parameterachromatic numberof a graphGis the largest integerksuch that there is a complete coloring ofGusing kcolors. Irving and Manlove [10] introducedb-chromatic number, another parameter related to graph coloring. Theb-chromatic numberof a graphG, denoted byχb(G), is the largest integerk such thatGhas ak-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. Such a coloring is called ab-coloring. Irving and Manlove showed that determining b-chromatic number is NP-complete for general graphs, but polynomial time solvable for trees [10]. From the definition of b-chromatic number it is clear thatχb(G)≤∆(G) + 1, where ∆(G) is the maximum degree of the graphG. Kratochvíl et al. [12] showed that determining whether χb(G) = ∆(G)+1 is NP-hard even for connected bipartite graphs. Havet et al. [8] showed that b-chromatic number can be computed in polynomial time for split graphs and it is NP-hard for connected chordal graphs. Regarding approximation algorithms for the problem, Galcík et al. [7] showed that b-chromatic number of ann-vertex graph can not be approximated within a factorn^1/4− for any constant >0, in polynomial time, unless P =NP.

In this work we address the algorithmic question of b-chromatic number in the realm of parameterized complexity and exact exponential time algorithms.

b-Chromatic Number Parameter: k

Input: Ann-vertex graphGand an integerk

Question: Is the b-chromatic number ofGis at least k

For a detailed overview of parameterized complexity reader is referred to monographs [5, 4].

In the parameterized complexity framework, the b-Chromatic Numberproblem is studied with a dual parameter by Havet et al. [9]. In particular, they show that one can decide whetherχb(G)≥n−kin time 2^O(klogk)n^O(1)and asked the question whether b-Chromatic Numberis FPT when parameterized byk. Recently, Effantin et al. [6] studied a relaxed version of b-coloring and repeated the question about the parameterized complexity of b-Chromatic Number. In this work we answer this question negatively, by showing that b-Chromatic Numberis W[1]-hard. But, whenk= ∆(G) + 1, we design an algorithm for b- Chromatic Numberrunning in time 2^O(k2logk)n^O(1). Finally we show that b-Chromatic Numberfor ann-vertex graph can be solved in timeO(3ⁿn⁴logn). After the results in this article were presented at IPEC, Manfred Cochefert informed us that he had derived, in his PhD thesis [3] a 3ⁿn^O(1) time algorithm for b-Chromatic Numberusing principle of inclusion-exclusion.

Our methods. To show b-Chromatic Numberis W[1]-hard, when parameterized byk, we give an FPT-reduction fromMulti Colored Independent Set, which is very well known to be W[1]-hard [4]. Whenk= ∆(G) + 1, to get an FPT algorithm for b-Chromatic Number, we first show that it is enough to findC⊆V(G) such thatχ_b(G[C]) =k(we call such a subsetC as b-chromatic core of orderk). Then we give a polynomial kernel for the problem of finding b-chromatic core of order ∆(G) + 1, which leads to an FPT algorithm for b-Chromatic Numberwhenk= ∆(G) + 1. For the exact exponential time algorithm for b-Chromatic Number, we reduce the problem to many instances of single variate polynomial multiplication of degree 2ⁿ.

2 Preliminaries

We use “graph” to denote simple graphs without self-loops, directions, or labels. We use V(G),E(G) and ∆(G), respectively, to denote the vertex set, edge set and maximum degree of a graphG. We also useG= (V, E) to denote a graphGon vertex setV and edge setE.

Forv, u∈V(G) andV⁰⊆V(G), we useG[V⁰] to denote the subgraph ofGinduced onV⁰, N[v] ={u : (v, u)∈E(G)} ∪ {v}andd(u, v) is the shortest distance betweenuandv. For a graphGand a b-coloring ofGwith color classesC₁, . . . , Ck, we say a vertexv∈Ci is a dominatingvertex for the color classCi ifvis adjacent to a vertex in Cj for eachj6=i.

We use [n] to denote the set {1,2, . . . , n}. We use ] to denote the disjoint union of sets: for any two sets A, B, the set A]B is defined only if (A∩B) = ∅, and in this case (A]B) = (A∪B). We assume that ] associates to the left; that is, we write U

1≤i≤nAi=A1]A2]A3· · · ]An to mean (· · ·((A1]A2)]A3)· · · ]An). Further, every use of]in an expression carries with it the implicit assertion that the two sets involved are disjoint.

A binary vector is a finite sequence of bits, and its width is the number of bits in the sequence. IfA, B are binary vectors, then byA+B we mean theinteger val(A) +val(B) where for a binary vectorX the expressionval(X) denotes the integer of whichX is a binary representation. Let U = {u₁, u₂, . . . , un} be a set of cardinalityn, and let S ⊆U. The characteristic vector χ(S) of S with respect to U is the binary vector with |U| = n bits whose`<sup>th</sup>bit, for 1≤`≤n, is 1 if elementu` belongs to setS, and 0 otherwise. We useN to denote the set of non-negative integers. TheHamming weight H(r) of a binary vectorr is the number of 1s inr. For a finite set U, a subsetS⊆U, and the characteristic vector χ(S) of S with respect toU, observe that H(χ(S)) =|S|. We define the Hamming weight ofn∈Nto be the number H(n) of the number of 1s in a binary representation ofn. Note that an integern∈Ndoes not have aunique binary representation, since we can pad any such representation with zeroes on the left without changing its numerical value. We call the total number of bits in a binary representationrofnthewidthofr.

ILemma 1 (?¹). LetS₁, S₂ be two disjoint subsets of a set U ={u1, u₂, . . . , u_n}, and let S=S1]S2. Then

1. χ(S) =χ(S1) +χ(S2)

2. χ(S₁) +χ(S₂) has a binary representation of widthn 3. H(χ(S)) =H(χ(S1)) +H(χ(S2))

We make extensive use of single-variate polynomials with integer coefficients. Let P = Pn

i=0a_ixⁱ be such a polynomial. We say that polynomialP contains monomialxⁱ, or that monomialxⁱispresent inpolynomialP, if the coefficientai ofxiis not zero. We say that the polynomialP⁰=Pn

i=0b_ixⁱis the representative polynomial ofP ifb_i= 1 whenevera_i6= 0 andbi= 0 otherwise. That is, the representative polynomial remembers just the degrees of the monomials which are present in P, and forgets their coefficients. For anh∈N, we define theHamming projection of polynomialP tohto beHh(P) =Pn

i=0bixⁱ wherebi = ai ifH(i) =hand 0 otherwise.That is,Hh(P) is the sum of all those monomials inP whose degrees have Hamming weighth. To obtain the stated running time for our exponential-time algorithm, we make use of the fast algorithm for multiplying polynomials which is based on the Fast Fourier Transform.

1 Proofs of results marked with a?are deferred to the full version of the paper.

c1

. . . c_i−1 ci ci+1

. . . ck

V₁ . . . Vi−1 V_i Vi+1 . . . V_k G

a₁ . . .

a_i−1 a_i

ai+1

. . . a_k

b1

. . .

bi

. . . bk

s ^s

Figure 1 The graphG⁰ constructed from the input instanceG= (V1]. . .]Vk, E) ofMulti- Colored Independent Set. The thick edges represent all possible edges between two corresponding sets of vertices.

ILemma 2([14]). Two polynomials of degree at most nover any commutative ringRcan be multiplied using O(nlognlog logn)additions and multiplications in R.

3 Hardness

In this section we show that b-Chromatic Numberis W[1]-hard by giving an FPT-reduction fromMulti-Colored Independent Set.

Multi-Colored Independent Set Parameter: k

Input: Ak-partite graph Gwith itsk-partitionV1]. . .]Vk ofV(G)

Question: Is there an independent set of sizekcontaining one vertex from each V_i? I Theorem 3. There is a polynomial time algorithm that given an instance G = (V₁] . . .]Vk, E)of Multi-Colored Independent Set, constructs an instance(G⁰,2k+ 1) of b-Chromatic Numbersuch thatGis a Yes instance ofMulti-Colored Independent

Setif and only if (G⁰,2k+ 1) is aYes instance of b-Chromatic Number.

Proof. LetGbe an instance ofMulti-Colored Independent Set, with its k-partition V1]. . .]Vk.

Construction. We construct a graphG⁰ fromGas follows. The vertex set ofG⁰, V(G⁰) = V(G)∪A∪B∪C∪ {s}, where A = {a1, . . . , ak}, B ={b1, . . . , bk} and C ={c1, . . . , ck}.

The edge setE(G⁰) containsE(G) and the following sets of new edges (see Figure 1).

{(ai, aj)|i6=j} ∪ {(ci, cj)|i6=j} (i.eA andCforms cliques), {(ai, cj)|1≤i, j≤k}(i.eA∪C forms a clique),

{(ai, b_j)|i6=j},

{(a_i, v)|v∈V_i} ∪ {(c_i, v)|v∈V(G)\V_i}, {(s, bi),(s, ci)| 1≤i≤k}.

Completeness. Suppose Gis an Yes instance of Multi-Colored Independent Set. Let I = {v1, . . . , vk} be an independent set such that vi ∈ Vi for all i ∈ [k]. Now we give a b-coloring of G⁰ using 2k+ 1 colors as follows. We define 2k+ 1 color classes – C0, C1, . . . , C2k. The color classC0=I∪ {s}. For all 1≤i≤k,Ci= (Vi∪ {ci})\ {vi}. For allk+ 1≤i≤2k,C_i ={a_i, b_i}. Note that for all 0≤i≤2k, C_i is an independent set in G⁰ andC0]C1]. . .]C2k =V(G⁰). Now we show that each color class has a dominating vertex. For color classC₀, the vertexsis a dominating vertex, becausesis adjacent to all the vertices in the setB∪C. For each 1 ≤i ≤k, the vertexci is the dominating vertex of the color classCi, because it is adjacent to the verticesA∪ {s}andC\ {ci}. For each k+ 1≤i≤2k,a_i is the dominating vertex for the color classC_i, because it is adjacent to all the vertices inC∪(A\ {ai}) and the vertexviin the color classC0.

Soundness. Let (G⁰,2k+ 1) is anYesinstance of b-Chromatic Number. Letφbe a b-coloring for the graphG⁰using at least 2k+ 1 colors. SinceA∪Cis a clique, all the vertices inA∪C are colored differently byφ. For 1 ≤i≤k, letCi be the the color class which contains the vertexci and for eachk+ 1≤i≤2k, letCi be the color class which contains the vertexai. LetC0 be an arbitrary color class other thatC1, . . . , C2k in the coloringφ.

First note that since the degree of any vertex inBisk, no vertex inBcan be a dominating vertex for any color class. Now consider the following claim.

IClaim 1. No vertex u∈ V(G) can be a dominating vertex for any of the color classes C₀, C_k+1, C_k+2, . . . , C_2k.

Proof. Suppose u ∈ V(G) is a dominating vertex for the color class Cj for some j ∈ {0, k+ 1, k+ 2, . . . ,2k}. Letu∈Vi for some 1≤i≤k. Consider the color class Ci. Note thatc_i ∈C_i. This implies thatC_i⊆V_i∪B, because the non-neighborhood ofc_i is V_i∪B.

But since u∈ Vi, uis not adjacent to any vertex in Vi∪B. This contradicts that uis a

dominating vertex forC_j. J

SinceC₀is disjoint fromA∪C and by Claim 1, we can conclude thatsis the dominating vertex forC0. Also note that for anyk+ 1≤i≤2k,Ci is disjoint from (A∪C∪ {s})\ {ai}.

By Claim 1, this implies that a_i is the dominating vertex for the class C_i. Since a_i is a dominating vertex for the classCi for eachk+ 1≤i≤2k, there is a vertexv inC0 such that (ai, v)∈E(G⁰). SinceC0∩(A∪B∪C) =∅ (becauses∈C0), we have thatv∈V_i−k. This implies that for eachk+ 1≤ i ≤2k, there is a vertex v ∈ Vi−k such that v ∈ C0. This implies thatGhas an independent set of sizekcontaining one vertex from eachVj for

1≤j≤k. This completes the proof of the lemma. J

4 FPT Algorithm for deciding whether χ

(G) = ∆(G) + 1

In this section we design a parameterized algorithm for b-Chromatic Numberto decide whetherχb(G) = ∆(G) + 1. For this section we setk= ∆(G) + 1. Towards this we define a notion of b-chromatic-core. Given a graphG, and a positive integer`, a set C⊆V(G) is called a b-chromatic-core of order`ifχb(G[C])≥`. Observe that a minimal set such that χ<sub>b</sub>(G[C])≥` has size upper bounded by`². We start by showing that for the case, when we want to test whetherχb(G) = ∆(G) + 1 =k, it is sufficient to find a b-chromatic-core of orderk.

ILemma 4. Let Gbe a graph. Thenχb(G) =k if and only ifG has a b-chromatic-core of orderk. Here k= ∆(G) + 1.

Proof. For the forward direction letχb(G) =k. ThenV(G) is a b-chromatic-core of orderk.

For the reverse direction assume thatG has a b-chromatic-coreC of orderk. By the definition of b-chromatic-core we have that χb(G[C]) ≥ k. Since χb(G[C]) ≤ ∆(G) + 1 we have thatχ_b(G[C]) =k. LetC₁, . . . , C_k be the partition of C witnessing the fact that χb(G[C]) =k. Now we will show that we can extend this partition to the vertex set ofG.

Letw1, . . . , wq denote the vertices of V(G)\C. We iteratively go through the vertices in V(G)\C and try to place it in the already existing partition. Suppose at some stage we have taken care of vertices until saywi. Forwi+1 we do as follows. Since the degree of every vertex is upper bounded by ∆ we have that there is a partition C_j such thatw_i+1 does not have any neighbor inCj. We placewi+1∈Cj. That is,Cj:=Cj∪ {wi+1}. Observe that the placement preserves the fact thatC_j after the addition of the vertex remains independent.

This proves the lemma. J

Lemma 4 allows us to look for b-chromatic-core of orderkforG. Towards this we define the following reduction rule.

IReduction Rule 1. Let(G, k)be an instance to b-Chromatic Numberandv be a vertex such that every vertexw∈N[v] has degree at mostk−2. Then(G\ {v}, k).

ILemma 5(?). Reduction Rule 1 is safe. That is,(G, k)is a Yesinstance to b-Chromatic Numberif and only if (G⁰ =G\ {v}, k)is a Yes instance to b-Chromatic Number. ITheorem 6. Let(G, k)be an instance to b-Chromatic Numbersuch thatk= ∆(G) + 1.

Then there is an algorithm that decides whetherχb(G) =k, in time2^O(k2logk)+n^O(1). Proof. We first apply Reduction Rule 1 exhaustively. Then, we greedily find a maximal setS such that (a) degree of every vertex is equal tok−1 and (b) for any pair of vertices v, w∈S, we have thatd(v, w)≥4. We have two cases either|S| ≥k or|S|< k. In the first case we can show thatχb(G) =kin polynomial time and in the later case we will bound the number of vertices ofGby a polynomial function ofk.

Case I:|S| ≥k. In this case we will show thatS and its neighbors form b-chromatic-core of orderkforG. LetC={v1, . . . , vk}be an arbitrary subset of sizekofS. For everyvi∈C letW_i =N(v_i). Let the vertices ofW_i be denoted by {wⁱ₁, . . . , w_i−1ⁱ , wⁱ_i+1, w_kⁱ}. Observe that since for any pair of verticesv, w∈S,d(v, w)≥4, we have thatWi∩Wj=∅and there are no edges betweenW_i andW_j for i6=j. Now we make color class I_i,i∈ {1, . . . , k}, as follows: Ii ={w_i^j |j6=i} ∪ {vi}. Observe that by construction every vertex vi has neighbor in every color class exceptIi and thusC∪W forms a b-chromatic-core of order k for G.

Given the partition ofC∪W we can find a b-chromatic partition of Gin polynomial time using the procedure described in Lemma 4.

Case II:|S|< k. In this case we claim that for every vertexv∈V(G)\S, there exists a vertexu∈S such thatd(u, v)≤4. First of all notice that either the degree ofv isk−1 or has a neighborwwith degree k−1. The last assertion follows from the fact that we can not apply Reduction Rule 1 onG. Suppose the degree ofv is k−1 then since the greedy algorithm did not pickv∈S, we have that there exists a vertexu∈S such thatd(u, v)≤3.

In the case when whas degree k−1, we have that there exists a vertex u∈S such that d(u, w)≤3 and thusd(u, v)≤4. This implies that every vertex in V(G) can be reached from a vertex inS by a path of length at most 4. Since the maximum degree of this graph is at mostk−1, we have that |V(G)|= 5k⁵ =O(k⁵). Thus, to test whetherχb(G) =kwe

guess the b-chromatic-core of order k. We know that there exists one of size at mostk². Thus, this results in

5k⁵ k²

≤2^O(k2logk)

guesses. GivenC we can test whetherχb(G[C]) =k in time 2^O(|C|)= 2^O(k2) (see the exact algorithm for the mentioned running time). Even the brute force partition intokparts will led to an algorithm with running time 2^O(k2logk). This concludes the proof. J

5 Exact Algorithm

In this section we show that given a graph G on n vertices as input, we can find the b- chromatic number ofGin running time which is single-exponential inn, modulo polynomial factors:

ITheorem 7. There is an algorithm which, given a graphGon nvertices as input, finds the b-chromatic number ofGin O(3ⁿn⁴logn)time.

Our algorithm works by checking, for k=n,(n−1), . . . ,1 in this order, whetherGhas a b-coloring withkcolors. It outputs the first (and so, the largest) value ofkfor which the check returnsYes.

ITheorem 8. There is an algorithm which, given a graphGon nvertices and an integer 1≤k≤nas input, checks if Ghas a b-coloring with kcolors inO( ⁿ_k

2^(n−k)n⁴logn) time.

Given Theorem 8, the proof of Theorem 7 is immediate:

Proof of Theorem 7. Since our algorithm for Theorem 7 consists of invoking the algorithm of Theorem 8 once for eachk∈ {1,2, . . . , n}, we get that the former algorithm runs in time

X

0≤k≤n

O(

n k

2^(n−k)n⁴logn) =O(n⁴logn X

0≤k≤n

n k

2^(n−k)) =O(3ⁿn⁴logn),

where we get the simplified form from the Binomial Theorem. J Observe that our goal in Theorem 8 is to check whether we can partition the vertex set ofGinto exactlyknon-empty partsV1, V2, . . . , Vk such that

each setVi is an independent set inG, and

for each 1≤i≤kthere is a vertexvi∈Vi which has a neighbour in each of the other sets V_j ; j6=i.

Such a partition is a b-coloring of Gwith k colors, and we call such a set of k vertices {v1, v₂, . . . , v_k}adominator setfor the b-coloringV₁, V₂, . . . , V_k. Our algorithm for Theorem 8 checks, for each vertex subset{v1, v2, . . . , vk} ofGof sizek, whether there is a b-coloring of Gwithkcolors for which{v₁, v₂, . . . , v_k}is a dominator set.

ILemma 9. Given a graph G on n vertices and a vertex subset D ={v1, v2, . . . , vk} of Gof size k, we can find whether graphG has a b-coloring with k colors for whichD is a dominator set, inO(2^(n−k)n⁴logn) time.

Note that Theorem 8 follows directly from Lemma 9. In the next subsection we describe an algorithm of the kind specified in Lemma 9. We then prove its correctness (subsection 5.2) and show that it runs within the stated time bounds (subsection 5.3).

5.1 The Algorithm

We describe an algorithm which, given a graph Gonn vertices and a vertex subsetD = {v1, v2, . . . , vk}ofGof sizek, finds whether graphGhas a b-coloring withkcolors for which Dis a dominator set. Let I denote the set of all vertex subsets ofGwhich are independent sets inG. Let V⁰=V(G)\D be the set of all vertices of graphGwhich arenot part of the candidate dominator setD. We label the vertices of V⁰ asV⁰={u1, u2, . . . , u_n−k}. Letx be an indeterminate.

For each pair of distinct indicesi, j; 1≤i6=j≤k, letSij denote the set of subsetsX of V⁰ such that (X∪ {vi}) is an independent set inG, and (X∪ {vi, vj}) isnotan independent set inG:

Sij ={X ⊆V⁰ ; (X∪ {vi})∈ I and∀1≤j6=i≤k: (X∪ {vi, vj})∈ I}/ (1) For each indexi; 1≤i≤k, letTi denote the intersection, over allj6=i, of the setsSij:

Ti= \

1≤j6=i≤k

Sij (2)

Note thatTi is the set of all independent sets inV⁰ which couldpotentially form a color class together with vertexv_i in a b-coloring of interest to us. Indeed, anyb-coloring ofGof the specified kind will consist—apart from the vertices ofD—of a pairwise disjoint collection ofkindependent sets, one from each setTi; 1≤i≤k, such that their union makes up all of V⁰. Our algorithm looks for such a collection of independent sets, one from each setTi.

For each vertexvi∈D we construct the setTi. We then useTito construct a polynomial Pi inxfor each vertexvi∈D, in the following manner: We initializePi to zero. For each setX ∈ Ti we compute the characteristic vectorχ(X) ofX with respect to the setV⁰. We then add the monomialx^χ(X)to the polynomialPi:

Pi = X

X∈Ti

x^χ(X) (3)

We now compute a sequence of polynomialsQ1,Q2, . . . ,Qk. We setQ1=P1. Now for each 2≤`≤kwe compute the polynomialQ` as follows. We initializeQ`to zero. For each pair of integersi, j≥0 ; i+j≤(n−k), we

Compute the polynomials Qi = Hi(Q_{(`−1)</sub>) and Pj = Hj(P<sub>(`)}), and their product R⁰_ij =Q_i×P_j;

Compute the representative polynomialR⁰⁰_ij ofR⁰_ij. Compute the Hamming projectionRij =H_(i+j)(R⁰⁰_ij);

SetQ⁰_{`</sub>:=Q<sub>`}+R_ij.

SetQ` to be the representative polynomial ofQ<sup>0</sup><sub>`</sub>.

IRemark. Note that this construction ensures that every nonzero monomial in each polyno- mialQi; 1≤i≤khas the form x^d for somed∈N. That is, no monomial has a coefficient greater than 1 in any of these polynomials.

Our algorithm returnsYesif the polynomialQk contains at least one monomial whose degree has Hamming weight (n−k), and Nootherwise. This completes the description of the algorithm.

5.2 Correctness

We now prove that the algorithm of the previous section indeed works exactly as specified in the statement of Lemma 9. We prove this in two parts; first we show that the algorithm is complete (Lemma 10), and then we show that it is sound (Lemma 12).

I Lemma 10. If a graph G on n vertices has a b-coloring with k colors for which D = {v₁, v₂, . . . , v_k} ⊆V(G)is a dominator set, then the algorithm of subsection 5.1 returns Yes on input(G, D).

Proof. Suppose graph G has a b-coloring V1, V2, . . . , Vk with k colors for which the set D = {v1, v2, . . . , vk} is a dominator set. Let V⁰ = V(G)\D and for 1 ≤ i ≤ k, let Xi =Vi\ {vi}. Letχ(X) be the characteristic vector of a subsetX ⊆V⁰ with respect to the setV⁰. For each 1≤i≤kletm_i=x^χ(Xi). It is not difficult to see that for each 1≤i≤k, the setXicontributes the monomial mi to the polynomialPi computed by the algorithm.

IClaim 2(?). For each1≤i≤k, the polynomialP_i constructed by the algorithm contains the monomialmi=x^χ(Xi).

Our method of computing the polynomialsQ1,Q2, . . . ,Qk has two desirable implications:

(i) the final polynomialQk computed by the algorithm contains the product of all them_is as a monomial, and (ii) the degree of this monomial has Hamming weight exactly (n−k). To see this, consider first some properties satisfied by all the polynomialsQ_`:

IClaim 3. For each 1≤`≤k, the following hold:

1. Let dbe the degree of the monomial m=Q

1≤i≤`mi. Then

a. d≤2^(n−k), and hencedhas a binary representation rof width (n−k).

b. Let S=U

1≤i≤`Xi. Thenχ(S) =r.

2. The polynomial Q` contains the monomial m.

Proof of Claim 3. We prove the claim by induction on`.

Base case: `= 1.

1. Here m=m₁=x^χ(X1).

(a) Since X1 ⊆ V⁰, |V⁰| = (n−k), and the degree d of m1 is χ(X1), we have that d≤2^(n−k) and thatdhas—by definition–the binary expansionr=χ(X₁) of width (n−k).

(b) The setSis just the subsetX1⊆V⁰, and hence we get directly thatχ(S) =χ(X1) = r.

2. We get from Claim 2 that the polynomial Q_(`−1) = Q1 = P1 contains the monomial m=m₁=x^χ(X1).

Induction step: 2≤`≤k

1. Here m=m1m2· · ·m`. Letm<sup>0</sup> =m1m2· · ·m<sub>(`−1)</sub>.

(a) Letdbe the degree of monomialm, and letd⁰ be the degree of monomialm⁰. Let S⁰ =U

1≤i≤(`−1)Xi. By the inductive hypothesis,d<sup>0</sup> has a binary expansionr<sup>0</sup> of width (n−k), andχ(S<sup>0</sup>) =r<sup>0</sup>. Also,m<sub>`</sub>=x<sup>χ(X`)</sup>by definition. Sincem=m<sup>0</sup>·m<sub>`</sub> we get that m=x^d0 ·x^{χ(X`)</sup>=x<sup>r0</sup> ·x<sup>χ(X`)} =x^χ(S0)·x^{χ(X`)</sup> =x<sup>χ(S0)+χ(X`)}, where we got the second expression by rewritingd⁰ in binary. Now by assumption the setsS⁰ andX` are disjoint subsets of V<sup>0</sup>, and hence we get—see Lemma 1—that d=χ(S<sup>0</sup>) +χ(X`)≤2^(n−k), and hence thatdhas a binary representationrof width (n−k).

Algorithm 1Algorithm for computing the setsT_i as bit stringsT_i . 1: functionComputeTs(G, V⁰, k)

2: Create bit stringsT₁, T₂, . . . , T_k of length 2^(n−k) each, with all bits set to zero.

3: forX ⊆V⁰ do 4: for1≤i≤kdo

5: if (X∪ {vi}) is an independent set inGthen

6: inT i←True

7: for1≤j≤k, j6=ido

8: if (X∪ {vi, vj}) is an independent set inGthen

9: inT i←False

10: if inT i==True then

11: T_i[χ(X)]←1

12: return (T₁, T₂, . . . , T_k)

(b) Here S = S⁰ ]X_`, and so from the above argument and Lemma 1 we get that r=χ(S).

2. We reuse notation from part (a) above. Leti be the Hamming weight of χ(S⁰). Note thati=|S⁰|. Letj =|X`|; then j is the Hamming weight ofχ(X`). SinceS⁰ andX`

are disjoint subsets of the setV⁰, we get from Lemma 1 thati+j≤(n−k). Therefore i, j is among the pairs of integers over which we iterate during the computation of the polynomialQ`. Let us examine carefully that step in this computation where we consider the pairi, j. Recall that we compute the polynomialsQi, Pj, R⁰_ij, R⁰⁰_ij, and Rij in this step.

From the inductive assumption we get that (i) the polynomial Q_{(`−1)</sub> contains the monomialm<sup>0</sup> =m1m2· · ·m<sub>(`−1)}, and (ii)χ(S⁰) is the binary representation of the degree of m⁰, and hence that i is the Hamming weight of the degree of m⁰. From these we get that the polynomialQ_i=Hi(Q<sub>(`−1)</sub>) contains the monomialm<sup>0</sup>. Further, we have shown that the polynomialP`contains the monomialm`=x<sup>χ(X`)</sup>, and by definition,j is the Hamming weight of the degreeχ(X_{`</sub>) ofm<sub>`}. From this we get that the polynomial Pj=Hj(P`) contains the monomialm`. Hence the productR⁰_ij =Qi×Pj, and thence its representative polynomialR_ij⁰⁰ both contain the monomialm⁰m`.

From the inductive assumption we get thatm⁰=x^χ(S0), and by definition we have that m` =x<sup>χ(X`)</sup>. Thus m⁰m`=x<sup>χ(S0)+χ(X`)</sup>. Now sinceS⁰ andX` are disjoint subsets of the setV<sup>0</sup>, we get from Lemma 1 thatχ(S<sup>0</sup>) +χ(X`) has Hamming weightexactlyi+j.

Hence the monomialm=m⁰m_` survives in the Hamming projectionR_ij =H(i+j)(R⁰⁰_ij).

Thereforemis present in the polynomial Q`. J

ICorollary 11(?).Letm=Q

1≤`≤kmi. Then the polynomialQk containsmas a monomial, and the Hamming weight of the degree dofm is exactly (n−k).

SinceQk contains the monomial Q

1≤`≤kmi whose degree has Hamming weight (n−k),

our algorithm returnsYeson this input. J

ILemma 12(?). If the algorithm of subsection 5.1 returns Yeson input(G, D), then graph Ghas a b-coloring withkcolors for which D is a dominator set.

Algorithm 2 Algorithm for computing the polynomialQ_{`</sub>as a bit stringS<sub>`}. 1: functionComputeQs(S<sub>(`−1)</sub>, T`)

. S_{(`−1)</sub>, T<sub>`} represent the polynomials Q_{(`−1)</sub>,P<sub>`}; see the text.

2: Create bit stringsP1, P2, . . . , P_(n−k)of length 2^(n−k) each, with all bits set to zero.

3: Create bit stringsQ₁, Q₂, . . . , Q_(n−k) of length 2^(n−k)each, with all bits set to zero.

4: Create bit stringS` of length 2^(n−k), with all bits set to zero.

5: for1≤i≤2^(n−k)do . Compute all the projectionsPi andQi in one pass.

6: h←the Hamming weight ofi

7: if T`[i] == 1then . The polynomialP` contains the monomialxⁱ

8: P_h[i]←1

9: if Q<sub>(`−1)</sub>[i] == 1then . The polynomialQ` contains the monomialxⁱ

10: Qh[i]←1

11: for0≤i≤(n−k)do 12: for0≤j≤(n−k−i)do

13: R⁰⁰_ij ←FFT-Multiply(Qi, Pj) .See explanation in text.

14: for1≤p≤2^(n−k)do

15: if the Hamming weight ofpisi+j then 16: if R⁰⁰_ij[p] == 1then

17: S`[p]←1

18: returnS`

5.3 Running Time Analysis

ILemma 13. The algorithm of subsection 5.1 runs inO(2^(n−k)n⁴logn) time where nis the number of vertices of the input graph G, andk is the size of the dominator setD.

Proof. We assume that we are given the adjacency matrix of graphGas input. If required, we relabel the vertices of graph G as V(G) = {v1, v2, . . . , vn} in such a way that the k vertices of the setD appearlast in this list. In other words, such thatV⁰ =V(G)\D= {v1, v2, . . . , v_(n−k)}. This can be done inO(n) time.

We compute the sets T1,T2, . . . ,Tk asbit strings T1, T2, . . . , Tk, respectively, of length 2^n−keach, with the following semantics: thej^thbitTi[j] of bit stringTiis 1 if and only if the subsetX⊆V⁰ whose characteristic vectorχ(X) with respect toV⁰ satisfies the condition val(X) =j is in the setTi. We use Algorithm 1 to compute these bit strings.

Creating the empty bit strings (line 2) takesO(2^(n−k)) time. The innermostforloop (starting at line 7) hasO(k) iterations, each of which takesO(n²) time: this is the time we need for a brute-force check for independence of the set X∪ {vi, vj} using the adjacency matrix of G. Theforloop at line 7 therefore takes O(kn²) time. Assuming that we can access any one bit of a 2^(n−k)-sized bit string in timeO(log(2^(n−k))) =O(n), line 11 takes O(n) time. The independence test of line 5 takes, as above,O(n²) time. Thus the contents of theforloop at line 4 takeO(n²) +O(kn²) + +O(n) =O(kn²) time. From this we get that the loop at line 3 takesO(2^(n−k)·k·kn²) =O(k²n²2^(n−k)) time. The algorithm for creating the bit stringsT1, T2, . . . , Tk therefore takesO(k²n²2^(n−k)) time.

Observe now that each bit-string Ti servesalso as a representation of the polynomial P_i. This follows directly from the way we defined the polynomials P_i from the sets T_i. Specifically: monomialx^d is present in polynomialPi if and only if the bitTi[d] is set to 1.

Hence we do not need to explicitly compute the polynomialsPi; we just use the bit-strings Ti instead.

Recall thatQ1=P1. For each 2≤`≤kwe compute the polynomialQ`, again as a bit stringS` of length 2<sup>(n−k)</sup>, as in Algorithm 2. We first setS1=T1. For each 2≤`≤k, in increasing order of`, we invoke the function ComputeQswith the argumentsS<sub>(`−1)</sub>, T<sub>`</sub> to obtain the bit stringS`. The bit stringSk which we obtain at the end of this process is the representation of the polynomialQ_`.

The functionComputeQsis mostly self-explanatory, except perhaps for lines 13 to 17.

On line 13 we invoke the functionFFT-Multiplywhich takes the bit string representations of two polynomialsQi, Pj, computes the bit string representation of their productR⁰_ij using the Fast Fourier Transform, and returns the (bit string representation of the) representative polynomialR⁰⁰_ij ofR⁰_ij (see Lemma 2). In lines 14 to 17 we then add the Hamming projection R_ij =H_(i+j)(R⁰⁰_ij) toS_` without explicitly computingR_ij as a separate bit string.

We now analyze the time taken by one invocation of ComputeQs. Lines 2 to 4 together take timeO((n−k)2^(n−k)). Lines 6 to 10 can each be executed in timeO(n−k), and so thefor loop at line 5 takesO((n−k)2^(n−k)) time. Line 13 can be performed inO(2^(n−k)(n−k) log(n−

k)) time (by Lemma 2), and the forloop at line 14 can be executed inO((n−k)2^(n−k)) time as well. It follows that theforloop at line 11 takesO((n−k)³2^(n−k)) time. In total, therefore, one invocation ofComputeQstakesO(2^(n−k)(n−k)³log(n−k)) time.

Since we invokeComputeQs(k−1) times, it follows that the complete algorithm runs

inO(2^(n−k)(n−k)³klog(n−k)) =O(2^(n−k)n⁴logn) time. J

6 Conclusion

In this paper we studied b-Chromatic Numberin the realm of parameterized and exact algorithm and resolved the parameterized complexity of the problem. We would like to conclude with two concrete open problems.

Is there an algorithm for b-Chromatic Numberrunning in time 2ⁿn^O(1)? Does there exist an XP algorithm for b-Chromatic Number?

Is the problem of finding ab-chromatic core of orderkFPT when parameterized byk?

References

1 Kenneth Appel and Wolfgang Haken. The solution of the four-color-map problem.Sci Am, 237(4):108–121, October 1977.

2 Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion- exclusion. SIAM J. Computing, 39(2):546–563, 2009.

3 Manfred Cochefert. Algorithmes Exacts et Exponentiels pour les Problèmes NP-difficiles sur les Graphes et Hypergraphes. PhD thesis, Université de Lorraine, December 2014.

4 Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015.

5 Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity.

Texts in Computer Science. Springer, 2013.

6 Brice Effantin, Nicolas Gastineau, and Olivier Togni. A characterization of b-chromatic and partial grundy numbers by induced subgraphs. CoRR, abs/1505.07780, 2015.

7 Frantisek Galcík and Ján Katrenic. A note on approximating the b-chromatic number.

Discrete Applied Mathematics, 161(7-8):1137–1140, 2013.

8 Frédéric Havet, Cláudia Linhares Sales, and Leonardo Sampaio. b-coloring of tight graphs.

Discrete Applied Mathematics, 160(18):2709–2715, 2012.

9 Frédéric Havet and Leonardo Sampaio. On the grundy andb-chromatic numbers of a graph.

Algorithmica, 65(4):885–899, 2013.

10 Robert W. Irving and David Manlove. The b-chromatic number of a graph. Discrete Applied Mathematics, 91(1-3):127–141, 1999.

11 Richard M. Karp. Reducibility among combinatorial problems. InComplexity of computer computations, pages 85–103. Plenum Press, New York, 1972.

12 Jan Kratochvíl, Zsolt Tuza, and Margit Voigt. On the b-chromatic number of graphs. In Ludek Kucera, editor,Graph-Theoretic Concepts in Computer Science, 28th International Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, Revised Papers,

volume 2573 ofLecture Notes in Computer Science, pages 310–320. Springer, 2002.

13 E. L. Lawler. A note on the complexity of the chromatic number problem. Information Processing Lett., 5(3):66–67, 1976.

14 Arnold Schönhage and Volker Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7(3-4):281–292, 1971.