# Dual Parameterization of Weighted Coloring

Júlio Araújo, Victor A Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, Ana Silva

► To cite this version:

Júlio Araújo, Victor A Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, et al.. Dual Parameterization of Weighted Coloring. Algorithmica, 2020, 82 (8), pp.2316-2336. 10.1007/s00453-020-00686-7 . lirmm-02989870

HAL Id: lirmm-02989870

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02989870

Submitted on 5 Nov 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Dual parameterization of Weighted Coloring

## Júlio Araújo

Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil
julio@mat.ufc.br

https://orcid.org/0000-0001-7074-2753

## Victor A. Campos

Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil
campos@lia.ufc.br

https://orcid.org/0000-0002-2730-4640

## Carlos Vinícius G. C. Lima

Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

carloslima@dcc.ufmg.br

https://orcid.org/0000-0002-6666-0533

## Vinícius Fernandes dos Santos

Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

viniciussantos@dcc.ufmg.br

https://orcid.org/0000-0002-4608-4559

## Ignasi Sau

LIRMM, CNRS, Université de Montpellier, Montpellier, France
ignasi.sau@lirmm.fr

https://orcid.org/0000-0002-8981-9287

## Ana Silva

Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil
anasilva@mat.ufc.br

https://orcid.org/0000-0001-8917-0564

## Abstract

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i \in [1, k]}$ of $V(G)$ into $k$ stable sets $S_1, \dots, S_k$. Given a weight function $w : V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^k w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G, w)$, denoted by $\sigma(G, w)$, as the minimum weight of a proper coloring of $G$. The problem of determining $\sigma(G, w)$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on $n$-vertex trees in time $n^{o(\log n)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree.

We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph $(G, w)$ and an integer $k$, is $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$? This parameterization has been recently considered by Escoffier [WG, 2016], who provided an FPT algorithm running in time $2^{O(k \log k)} \cdot n^{O(1)}$, and asked which kernel size can be achieved for the problem.

We provide an FPT algorithm in time $9^k \cdot n^{O(1)}$, and prove that no algorithm in time $2^{o(k)} \cdot n^{O(1)}$ exists under the ETH. On the other hand, we present a kernel with at most $(2^{k-1} + 1)(k-1)$ vertices, and rule out the existence of polynomial kernels unless NP $\subseteq$ coNP/poly, even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

<figure><img src="image_2.png" /></figure>

© Júlio Araújo, Victor A. Campos, Carlos V. Lima, Vinícius F. dos Santos, Ignasi Sau, Ana Silva; licensed under Creative Commons License CC-BY

Article submitted to Algorithmica, special issue of IPEC 2018.

<figure><img src="image_3.png" /></figure>

Leibniz International Proceedings in Informatics

LIPICS Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
XX:2 Dual parameterization of Weighted Coloring

2012 ACM Subject Classification

Mathematics of computing → Graph algorithms

Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** weighted coloring; max coloring; parameterized complexity; dual para-
meterization; FPT algorithms; polynomial kernels; split graphs; interval graphs.

Digital Object Identifier 10.4230/LIPIcs...

**Related Version** This article is permanently available at [arXiv:1805.06699]. A conference version appeared in the Proc. of the 13th International Symposium on Parameterized and Exact Computation (IPEC), volume 115 of LIPIcs, pages 12:1–12:14, Helsinki, Finland, August 2018.

**Funding** Work supported by French projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010), and by Brazilian projects CNPq 306262/2014-2, CNPq 311013/2015-5, CNPq Universal 421660/2016-3, CNPq Universal 401519/2016-3, FAPEMIG, Funcap PNE-0112-00061.01.00/16, and Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.

**Acknowledgements** We would like to thank the anonymous reviewers for carefully reading the conference version of this article [IPEC 2018], in particular for spotting a flaw in the proof of Claim 5, which we rewrote completely in a simpler way. We also thank Mikko Koivisto for pointing us to reference [4].

1 Introduction

A (vertex) *k*-coloring of a graph *G* = (*V*, *E*) is a function *c* : *V*(*G*) → {1, ..., *k*}. Such coloring *c* is proper if *c*(*u*) ≠ *c*(*v*) for every edge {*u*, *v*} ∈ *E*(*G*). All the colorings we consider in this paper are proper, hence we may omit the word “proper”. The *chromatic number* χ(*G*) of *G* is the minimum integer *k* such that *G* admits a *k*-coloring. Given a graph *G*, determining χ(*G*) is the goal of the classical **VERTEX COLORING** problem. If *c* is a *k*-coloring of *G*, then *S*<sub>*i*</sub> = {*u* ∈ *V*(*G*) | *c*(*u*) = *i*} is a stable (or independent) set. With slight abuse of notation, we shall also call such a set *S*<sub>*i*</sub> a *color*.

In this paper we study a generalization of VERTEX COLORING for vertex-weighted graphs that has been defined by Guan and Zhu [24]. Given a graph G and a weight function w : V(G) → R+, the weight of a color S_i is defined as w(i) = max_{v∈S_i} w(v). Then, the weight of a coloring c is w(c) = ∑k i=1 w(i). In the WEIGHTED COLORING problem, the goal is to determine the weighted chromatic number of a pair (G, w), denoted by σ(G, w), which is the minimum weight of a coloring of (G, w). A coloring c of G such that w(c) = σ(G, w) is an optimal weighted coloring. Guan and Zhu [24] also defined, for a positive integer r, σ(G, w; r) as the minimum of w(c) among all r-colorings c of G, or as +∞ if no r-coloring exists. Note that σ(G, w) = min_{r≥1} σ(G, w; r). It is worth mentioning that the WEIGHTED COLORING problem is also sometimes called MAX-COLORING in the literature; see for instance [18, 34, 39]. Guan and Zhu defined this problem in order to study practical applications related to resource allocation, which they describe in detail in [24]. One should observe that if all the vertex weights are equal to one, then σ(G, w) = χ(G), for every graph G. Consequently, determining σ(G, w) is an NP-hard problem on general graphs [33]. In fact, this problem has been shown to be NP-hard even on very restricted graph classes, such as split graphs with only two different weights, interval graphs, triangle-free planar graphs with bounded degree,
and bipartite graphs [11, 12, 19]. On the other hand, the weighted chromatic number of cographs and of some subclasses of bipartite graphs can be found in polynomial time [11, 12].

The complexity of WEIGHTED COLORING on trees (and forests) has attracted considerable attention in the literature. Guan and Zhu [24] left as an open problem whether WEIGHTED COLORING is polynomial on trees and, more generally, on graphs of bounded treewidth. Escoffier et al. [19] found a polynomial-time approximation scheme to solve WEIGHTED COLORING on bounded treewidth graphs, and Kavitha and Mestre [34] showed that the problem is in P on the class of trees where vertices with degree at least three induce a stable set. But the question of Guan and Zhu has been answered only recently, when Araújo et al. [2] showed that, unless the Exponential Time Hypothesis (ETH)<fnref n="1" /> fails, there is no algorithm computing the weighted chromatic number of *n*-vertex trees in time $n^{o(\log n)}$. Moreover, as discussed in [2], this lower bound is tight. Very recently Araújo et al. [1] focused on the parameterized complexity of computing $\sigma(G, w)$ and $\sigma(G, w; r)$ when $G$ is a forest, and they proved that computing $\sigma(G, w)$ is W[1]-hard parameterized by the size of a largest tree of $G$, and that computing $\sigma(G, w; r)$ is W[2]-hard parameterized by $r$.

In view of the above discussion, we can conclude that WEIGHTED COLORING is a particularly hard problem from a computational point of view, and that the positive results in the literature are quite scarce. In this paper we adopt the perspective of parameterized complexity and consider the dual parameterization of the problem, which we call DUAL WEIGHTED COLORING and is formally defined as follows:

### DUAL WEIGHTED COLORING

**Input:** A vertex-weighted graph $(G, w)$ and a positive integer $k$.

**Parameter:** $k$.

**Question:** Is $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$?

Since by definition of parameterized problem (cf. [10, 16]) the parameter needs to be a non-negative integer, for the above parameterization to make sense we will assume henceforth that all vertex-weights are positive integers. We will denote by $n$ the number of vertices of the input graph of DUAL WEIGHTED COLORING.

The motivation for considering such parameterization is to take as the parameter the “savings” with respect to the trivial upper bound of $\sum_{v \in V(G)} w(v)$ on $\sigma(G, w)$. This approach has proved to be very useful for the classical VERTEX COLORING problem, especially from the approximation point of view [13, 17, 18, 26–28]. From a parameterized perspective, Chor et al. [9] presented an FPT algorithm for DUAL VERTEX COLORING. Concerning kernelization, it is not difficult to see [10, Exercise 2.22] that the problem admits a kernel with at most $3k$ vertices, by applying the so-called *crown reduction rule* to the complement of the input graph $G$. Other results concerning dual parameterization are, for instance, FPT algorithms for the Grundy and *b*-chromatic numbers of a graph [29], the parameterized approximability of subset graph problems [8], or the existence of polynomial kernels for the SET COVER and HITTING SET problems [3, 25].

The dual parameterization of the WEIGHTED COLORING problem, under the equivalent name of MAX COLORING, has been recently considered by Escoffier [18], who provided an FPT algorithm running in time $2^{O(k \log k)} \cdot n^{O(1)}$, and asked which is the smallest kernel size that can be achieved for the problem.

<footnote n="1">¹ The ETH states that 3-SAT cannot be solved in subexponential time; see [31, 32] for more details.</footnote>
XX:4 Dual parameterization of Weighted Coloring

**Our results.** Improving over Escoffier's algorithm [18], our first result is an FPT algorithm for DUAL WEIGHTED COLORING running in time $9^k \cdot n^{O(1)}$, based on some standard dynamic programming ideas used in coloring and partition problems (see, for example, [35] and [20, Section 3.1.2]). It is easy to see that a subexponential algorithm is unlikely to exist. Indeed, consider the 3-COLORING problem, which corresponds to the unweighted version of DUAL WEIGHTED COLORING with parameter $k = n - 3$. Since 3-COLORING cannot be solved in time $2^{o(n)}$ under the ETH [38], the existence of an algorithm for DUAL WEIGHTED COLORING running in time $2^{o(k)} \cdot n^{O(1)}$ would imply, in particular, an algorithm for 3-COLORING running in time $2^{o(k)} \cdot n^{O(1)} = 2^{o(n)}$, contradicting the ETH.

Our main contribution concerns the existence of (polynomial) kernels for DUAL WEIGHTED COLORING. By the well-known equivalence of admitting an FPT algorithm and a kernel (cf. [10,16]), the FPT algorithm mentioned above directly yields a kernel for DUAL WEIGHTED COLORING of size at most $9^k$. On the one hand, we considerably improve this bound by providing a kernel with at most $(2^{k-1}+1)(k-1)$ vertices, inspired by an approach attributed to Jan Arne Telle [16, Exercise 4.12.12] for obtaining a quadratic kernel for DUAL VERTEX COLORING. On the other hand, we complement this result by showing that, unlike the DUAL VERTEX COLORING problem, DUAL WEIGHTED COLORING does not admit a polynomial kernel unless $NP \subseteq \text{coNP/poly}$, even on split graphs with only two different weights. We prove this result by a polynomial parameter transformation from the SET COVER problem parameterized by the size of the universe, proved not to admit polynomial kernels unless $NP \subseteq \text{coNP/poly}$ by Dom et al. [15]. Our reduction is an appropriate modification of a reduction of Demange et al. [12] to prove the NP-hardness of WEIGHTED COLORING on split graphs. Altogether, these results answer Escoffier's question [18] about the smallest kernel size for the problem.

Motivated by the above hardness result, it is natural to identify graph classes on which the DUAL WEIGHTED COLORING problem admits polynomial kernels. We prove that this is the case of graph classes with bounded clique number, comparability graphs, and interval graphs (and more generally, normal Helly circular-arc graphs), for which we present a linear, quadratic, and cubic kernel, respectively. Finally, we identify subclasses of split graphs admitting polynomial kernels. Namely, we prove that DUAL WEIGHTED COLORING restricted to split graphs where each vertex in the clique has at most $d$ non-neighbors in the stable set, for some constant $d \ge 1$, admits a kernel with at most $k^{d+1}$ vertices. We show that the dependency on $d$ in the exponent is necessary, by proving that for any $d \ge 2$ and $\varepsilon > 0$, a kernel with $O(k^{\frac{d-3}{2}-\varepsilon})$ vertices on that graph class does not exist unless $NP \subseteq \text{coNP/poly}$. In other words, we rule out the existence of a *uniform* kernel, that is, a kernel of size $f(d) \cdot k^{O(1)}$ for any function $f$.

**Organization of the paper.** In Section 2 we present some basic preliminaries about graphs and parameterized complexity. In Section 3 we present the FPT algorithm and in Section 4 we provide the kernelization results. Finally, we conclude the article in Section 5.

2 Preliminaries

**Graphs.** We use standard graph-theoretic notation, and we consider simple undirected graphs without loops or multiple edges; see [14] for any undefined terminology. Given a graph $G = (V, E)$, $X \subseteq V$, and $v \in V$, we denote $N_X(v) = N(v) \cap X$, where $N(v) = \{u \in V \mid \{u, v\} \in E\}$, and $\overline{N_X}(v) = X \setminus \{N_X(v) \cup \{v\}\}$. Similarly, we denote the closed neighborhood of $v$ as $N[v] = N(v) \cup \{v\}$. Two vertices $u, v \in V(G)$ are true twins, or simply twins, if $N[u] = N[v]$. An antimatching in a graph $G$ is a matching in the complement of $G$. A
vertex $v \in V(G)$ is *universal* if $N(v) = V(G) \setminus \{v\}$. A graph $G$ is a *split graph* if $V(G)$ can be partitioned into an independent set and a clique, and an *interval graph* if one can associate a real interval with each vertex, so that two vertices are adjacent if and only if the corresponding intervals intersect. A *circular-arc graph* is defined similarly, by associating with each vertex an arc on a circle.

**Parameterized complexity.** We refer the reader to [10, 16] for basic background on parameterized complexity, and we recall here only some basic definitions, with special emphasis on tools for polynomial kernelization. A *parameterized problem* is a language $L \subseteq \Sigma^* \times \mathbb{N}$. For an instance $I = (x, k) \in \Sigma^* \times \mathbb{N}$, $k$ is called the *parameter*. A parameterized problem is *fixed-parameter tractable* (FPT) if there exists an algorithm $\mathcal{A}$, a computable function $f$, and a constant $c$ such that given an instance $I = (x, k)$, $\mathcal{A}$ (called an FPT algorithm) correctly decides whether $I \in L$ in time bounded by $f(k) \cdot |I|^c$.

A fundamental concept in parameterized complexity is that of *kernelization*. A kernelization algorithm, or just *kernel*, for a parameterized problem $\Pi$ takes an instance $(x, k)$ of the problem and, in time polynomial in $|x|+k$, outputs an instance $(x', k')$ such that $|x'|, k' \le g(k)$ for some function $g$, and $(x, k) \in \Pi$ if and only if $(x', k') \in \Pi$. The function $g$ is called the *size* of the kernel and may be viewed as a measure of the “compressibility” of a problem using polynomial-time preprocessing rules. A kernel is called *polynomial* (resp. *linear*) if $g(k)$ is a polynomial (resp. linear) function in $k$. A breakthrough result of Bodlaender et al. [5] gave the first framework for proving that certain parameterized problems do not admit polynomial kernels, by establishing so-called *composition algorithms*. Together with a result of Fortnow and Santhanam [21] this allows to exclude polynomial kernels under the assumption that $\mathrm{NP} \not\subseteq \mathrm{coNP/poly}$, otherwise implying a collapse of the polynomial hierarchy to its third level [41]. Very successful notions for proving such type of result are those of *cross-composition*, introduced by Bodlaender et al. [6], and of *polynomial parameter transformation*, introduced by Bodlaender et al. [7]. We need to define the latter. A polynomial parameter transformation from a parameterized problem $P$ to a parameterized problem $Q$ is an algorithm that, given an instance $(x, k)$ of $P$, computes in polynomial time an equivalent instance $(x', k')$ of $Q$ such that $k'$ is bounded by a polynomial depending only on $k$.

Within parameterized problems, the class $\mathrm{W}[1]$ may be seen as the parameterized equivalent to the class $\mathrm{NP}$ of classical optimization problems. Without entering into details (see [10, 16] for the formal definitions), a parameterized problem being $\mathrm{W}[1]$-hard can be seen as a strong evidence that this problem is not FPT. The class $\mathrm{W}[2]$ of parameterized problems is a class that contains $\mathrm{W}[1]$, and such that the problems that are $\mathrm{W}[2]$-hard are even more unlikely to be FPT than those that are $\mathrm{W}[1]$-hard (again, see [10, 16] for the formal definitions).

## 3 FPT algorithm

In this section we present an FPT algorithm for the DUAL WEIGHTED COLORING problem. We first provide our kernelization result on general graphs.

**Theorem 1.** The DUAL WEIGHTED COLORING problem can be solved in time $9^k \cdot n^{O(1)}$.

*Proof.* We start by computing a maximum unweighted antimatching $\bar{M}$ in $G$ (this idea has been already used, in particular, in [12]); note that this can be done in polynomial time by computing a maximum matching in the complement of $G$. If $|\bar{M}| \ge k$, since we assume that all the vertex weights are at least 1, by putting in the same color class each pair of vertices that belong to a non-edge of $\bar{M}$ and coloring any other vertex with a new color, we obtain a
XX:6 Dual parameterization of Weighted Coloring

coloring of G with weight at most $\sum_{v \in V(G)} w(v) - k$, and we can output a constant-sized
yes-instance. Thus, we assume henceforth that $|\bar{M}| \le k - 1$.

Let $V(\bar{M}) \subseteq V(G)$ be the set of vertices that appear in the non-edges in $\bar{M}$. Since $\bar{M}$ is
maximum, the set of vertices $K := V(G) \setminus V(\bar{M})$ induces a clique in $G$. Note that, in any
coloring $c$ of $G$, at least $|K|$ colors will be needed. Let $K = \{v_1, \dots, v_{|K|}\}$ and let $c(v_i) = c_i$.
Hence, it remains just to color the vertices in $V(\bar{M})$, which may be colored with some colors
previously used in $K$ or with new ones.

Let $X \subseteq V(\bar{M})$ and $0 \le i \le |K|$. We define $T(X, i)$ as the minimum weight of a coloring of $G[K \cup X]$ such that no color $c_j$, for $j > i$, is assigned to a vertex of $X$, i.e., the colors assigned to vertices in $X$ are either from the set $\{c_1, \dots, c_i\}$ or new colors not assigned to any vertex of $K$. Note that, by definition, $\sigma(G, w) = T(V(\bar{M}), |K|)$.

We now describe how to compute $T(X, i)$ for every $X \subseteq V(\bar{M})$ and every $0 \le i \le |K|$.

If $X = \emptyset$, then, for any $i$,

$$
T(\emptyset, i) = \sum_{v \in K} w(v),
$$

since $K$ is a clique. This can be done in linear time.

If $i = 0$, then the colors used in $K$ and in $X$ are disjoint. By applying brute force over all
possible stable sets of $X$ we get

$$
T(X, 0) = \min_{\substack{\emptyset \neq S \subseteq X \\ S \text{ stable}}} T(X \setminus S, 0) + w(S),
$$

where $w(S) = \max_{v \in S} w(v)$. The values $T(X, 0)$, for all possible sets $X \subseteq V(\bar{M})$, can be computed in time

$$
\left( \sum_{j=0}^{|V(\bar{M})|} \binom{|V(\bar{M})|}{j} \cdot 2^j \right) \cdot n^{\mathcal{O}(1)} = 3^{|V(\bar{M})|} \cdot n^{\mathcal{O}(1)},
$$

corresponding to considering the sets $X$ by increasing size and choosing an arbitrary subset $S$
inside $X$, and where the polynomial factor comes from checking whether such a set $S$ is
stable or not.

Now, if $i > 0$ and $X \neq \emptyset$, we have two possibilities, namely either color $c_i$ is used in $V(\bar{M})$
or not. If $c_i$ is not used, clearly we have $T(X, i) = T(X, i-1)$. Otherwise, there is a
non-empty set $S \subseteq X$ of vertices colored with color $c_i$. Therefore, taking into account both
cases, we can iterate over every possible set $S \subseteq X$ and compute $T(X, i)$ as follows:

$$
T(X, i) = \min_{S \subseteq X \atop S \cup \{v_i\} \text{ stable}} T(X \setminus S, i-1) + w(S \setminus \{v_i\}) - w(v_i).
$$

Here we have to subtract the weight of $v_i$, which was, in the partial solution $T(X \setminus S, i-1)$,
the weight of color $c_i$, and replace it by $w(S \cup \{v_i\})$, which may be larger. As in the previous
case, for every $i$ it is possible to compute $T(X, i)$ for every $X$ in time $3^{|V(\bar{M})|} \cdot n^{\mathcal{O}(1)}$.

Hence, since $|V(\bar{M})| \le 2k - 2$, in time bounded by $3^{2k} \cdot n^{\mathcal{O}(1)} = 9^k \cdot n^{\mathcal{O}(1)}$ we can compute
$T(V(\bar{M}), |K|) = \sigma(G, w)$ and answer whether $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$ or not. $\triangle$

4 Kernelization results

In this section we focus on the existence of (polynomial) kernels for DUAL WEIGHTED COLORING.
**Theorem 2.** The DUAL WEIGHTED COLORING problem admits a kernel with at most $(2^{k-1} + 1) \cdot (k - 1)$ vertices.

*Proof.* We start with the following trivial polynomial-time reduction rule.

**Rule 1.** If $G$ contains a universal vertex, delete it.

**Claim 1.** Rule 1 is safe.

*Proof.* Since a universal vertex $u$ appears as a singleton in any proper coloring of $G$, it follows that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$ if and only if $\sigma(G - \{u\}, w) \le \sum_{v \in V(G) \setminus \{u\}} w(v) - k$. ◀

As in the proof of Theorem 1, we compute in polynomial time a maximum unweighted antimatching $\bar{M}$ in $G$. Again, if $|\bar{M}| \ge k$, we can correctly answer that we have a yes-instance, so we assume henceforth that $|\bar{M}| \le k - 1$. Let again $V(\bar{M}) \subseteq V(G)$ be the set of vertices that appear in the non-edges in $\bar{M}$, and recall that since $\bar{M}$ is maximum, the set of vertices $K = V(G) \setminus V(\bar{M})$ induces a clique in $G$.

We now partition $K$ into a set of equivalence classes $\mathcal{C}$ according to the neighborhood in $V(\bar{M})$. That is, $u, v \in K$ belong to the same class in $\mathcal{C}$ if and only if $N_{V(\bar{M})}(u) = N_{V(\bar{M})}(v)$. Note that $\mathcal{C}$ can be constructed in polynomial time, by iteratively processing the vertices of $K$, comparing the neighborhood in $V(\bar{M})$ of the currently processed vertex $v$ with those of the already processed vertices, and creating a new class containing only $v$ if no class has exactly the set $N_{V(\bar{M})}(v)$ as neighbors in $V(\bar{M})$. Given an equivalence class $C \in \mathcal{C}$ and a non-edge $\bar{e} \in \bar{M}$, we denote by $N_{\bar{e}}(C)$ the set of neighbors of any vertex in $C$ in the set consisting of the two endpoints of $\bar{e}$. We proceed to analyze the number and the size of the classes in $\mathcal{C}$. We start with an easy claim.

**Claim 2.** Let $C \in \mathcal{C}$ be an equivalence class with $|C| \ge 2$. For every non-edge $\bar{e} \in \bar{M}$ it holds that $|N_{\bar{e}}(C)| \ge 1$.

*Proof.* Suppose for contradiction that $|N_{\bar{e}}(C)| = 0$, let $x, y$ be the endvertices of $\bar{e}$, and let $u, v$ be any two vertices in $C$. Then we can obtain from $\bar{M}$ a larger antimatching $\bar{M}'$ by replacing the non-edge $\{x, y\}$ with the two non-edges $\{u, x\}$ and $\{v, y\}$, a contradiction. ◀

In the next claim we restrict further the neighborhoods of the equivalence classes in $V(\bar{C})$.

**Claim 3.** Let $C_1, C_2 \in \mathcal{C}$ be two equivalence classes and let $\bar{e} \in \bar{M}$ be a non-edge with endpoints $x$ and $y$. Then it is not possible that $x \notin N_{\bar{e}}(C_1)$ and $y \notin N_{\bar{e}}(C_2)$, or vice versa.

*Proof.* Suppose for contradiction that $x \notin N_{\bar{e}}(C_1)$ and $y \notin N_{\bar{e}}(C_2)$, and let $u \in C_1$ and $v \in C_2$. Then we can obtain from $\bar{M}$ a larger antimatching $\bar{M}'$ by replacing the non-edge $\{x, y\}$ with the two non-edges $\{u, x\}$ and $\{v, y\}$, a contradiction. ◀

We call an equivalence class $C \in \mathcal{C}$ special if for some non-edge $\bar{e} \in \bar{M}$, $|N_{\bar{e}}(C)| = 0$, and we call such an $\bar{e}$ a special non-edge; otherwise we call an equivalence class normal. We call a non-edge $\bar{e} \in \bar{M}$ normal if for every $C \in \mathcal{C}$, $|N_{\bar{e}}(C)| \ge 1$. Let $k_s$ and $k_n$ be the number of special and normal non-edges in $\bar{M}$, respectively, and note that $k_s + k_n = |\bar{M}| \le k - 1$.

By Claim 2, every special class contains exactly one vertex. If $\bar{e} \in \bar{M}$ is a special non-edge and $C \in \mathcal{C}$ is such that $|N_{\bar{e}}(C)| = 0$, then Claim 3 implies that for every other class $C' \in \mathcal{C}$ different from $C$, it holds that $|N_{\bar{e}}(C')| = 2$. Therefore, the number of special classes in $C$ is at most the number of special non-edges in $\bar{M}$, that is, at most $k_s$.

Let $\bar{e} \in \bar{M}$ be a normal non-edge with endpoints $x, y$, let $C \in \mathcal{C}$ be such that $|N_{\bar{e}}(C)| = 1$, and assume that $N_{\bar{e}}(C) = \{x\}$. Then Claim 3 implies that for every class $C' \in \mathcal{C}$ such
XX:8 Dual parameterization of Weighted Coloring

that $|N_{\bar{e}}(C')| = 1$, it holds that $N_{\bar{e}}(C') = \{x\}$. Hence, every normal non-edge $\bar{e} \in \bar{M}$ has at most one endpoint that has some non-neighbor in $K$; we call such a vertex the *avoidable* vertex of $\bar{e}$. This means that for every normal class $C \in \mathcal{C}$ and every non-edge $\bar{e} \in \bar{M}$, there are exactly two possibilities: either $|N_{\bar{e}}(C)| = 2$, or $|N_{\bar{e}}(C)| = 1$ and $N_{\bar{e}}(C)$ consists of the endpoint of $\bar{e}$ distinct from its avoidable vertex. Moreover, by Claim 3 the latter case can only occur if $\bar{e}$ is a normal non-edge. Therefore, the number of normal classes in $\mathcal{C}$ is at most $2^{k_n} - 1$, corresponding to all the choices of neighborhoods in the set consisting of the avoidable vertices in the normal edges in $\bar{M}$, and excluding the class $C$ with $N_{V(\bar{M})}(C) = V(\bar{M})$, since these vertices would be deleted by Rule 1.

Finally, in order to bound the size of the equivalence classes in $\mathcal{C}$, we state the following reduction rule, which says that it is enough to keep, for each equivalence class, the $|\bar{M}|$ heaviest vertices.

**Rule 2.** Suppose there exists an equivalence class $C \in \mathcal{C}$ with $|C| > |\bar{M}|$. Let $W \subseteq C$ be a subset of vertices with $|W| = |\bar{M}|$ and such that, if $u \in W$ and $v \in C \setminus W$, then $w(u) \ge w(v)$. Delete from $G$ all the vertices in $C \setminus W$.

► Claim 4. Rule 2 is safe.

**Proof.** We need to prove that if $(G', w, k)$ results from $(G, w, k)$ after the application of Rule 2, then $(G, w, k)$ and $(G', w, k)$ are equivalent instances of DUAL WEIGHTED COLORING.

Assume first that $\sigma(G', w) \le \sum_{v \in V(G')} w(v) - k$, and let $c'$ be a coloring of $(G', w)$ satisfying this bound. We define a coloring $c$ of $(G, w)$ starting from $c'$ and creating a new color for each of the vertices in $C \setminus W$. Clearly, $w(c) = w(c') + \sum_{v \in C \setminus W} w(v) \le \sum_{v \in V(G)} w(v) - k$.

Conversely, assume that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$, and let $c$ be a coloring of $(G, w)$ satisfying this bound. Due to Rule 1, we can clearly assume that $|\bar{M}| \ge 1$. Hence, since Rule 2 has been applied on $C \in \mathcal{C}$, it follows that $|C| \ge 2$. Thus, by Claim 2, we have that for every non-edge $\bar{e} \in \bar{M}$, $|N_{\bar{e}}(C)| \ge 1$. This implies, together with the fact that the vertices in $C$ induce a clique, that in the coloring $c$ of $(G, w)$, at most $|\bar{M}|$ vertices of $C$ appear in colors containing vertices of $V(\bar{M})$, and every other vertex in $C$ is a singleton in its color. Let $T \subseteq C$ be this set of at most $|\bar{M}|$ vertices, and let $W \subseteq C$ be the set such that Rule 2 has deleted from $G$ the vertices in $C \setminus W$. We iteratively modify the coloring $c$ by updating the set $T$ as follows (the set $W$ remains the same). While there exists a vertex $u \in V(G)$ such that $u \in T$ and $u \notin W$, let $v \in W$ such that $v \notin T$ (note that vertex $v$ exists, since $|T| \le |\bar{M}| = |W|$), and swap $u$ and $v$ in the coloring, that is, now $u$ is a singleton in its color and $v$ is in a color containing vertices of $V(\bar{M})$. Since $u$ and $v$ are twins, this procedure indeed creates a proper coloring of $G$, which we also call $c$ with abuse of notation. Let us now argue that the weight of the coloring has not increased. Note that since $u \notin W$ and $v \in W$, it follows that $w(v) \ge w(u)$. If we denote by $S_i$ and $S_j$ the colors of $c$ before the swapping, so that $u \in S_i$ and $S_j = \{v\}$, and by $S'_i$ and $S'_j$ the corresponding colors after the swapping, note that $w(S_i) \ge w(u)$, $w(S_j) = w(v)$, $w(S'_i) = \max\{w(S_i), w(v)\}$, and $w(S'_j) = w(u)$. Therefore,

$$w(S'_i) + w(S'_j) = \max\{w(S_i), w(v)\} + w(u) \le w(S_i) + w(v) = w(S_i) + w(S_j),$$

where we have used that $w(v) \ge w(u)$. Thus, at the end of this procedure we obtain a coloring $c$ with $w(c) \le \sum_{v \in V(G)} w(v) - k$ such that every vertex in $C \setminus W$ is a singleton in its color class. We define $c'$ to be the restriction of $c$ to $G'$. Since every vertex in $C \setminus W =$
$V(G) \setminus V(G')$ is a singleton in its color class in $c$, it follows that

$$w(c') = w(c) - \sum_{v \in C \setminus W} w(v) \le \left( \sum_{v \in V(G)} w(v) - k \right) - \sum_{v \in C \setminus W} w(v) = \sum_{v \in V(G')} w(v) - k,$$

and the claim follows.

<figure><img src="image_4.png" /></figure>

We can easily apply Rule 2 exhaustively in polynomial time to all the classes $C \in \mathcal{C}$ with $|C| > |\bar{M}|$. We call an instance reduced if none of Rule 1 and Rule 2 can be applied anymore. The above discussion implies that if $(G, w, k)$ is a reduced instance, then

$$|V(G)| = |V(\bar{M})| + |K| \le 2(k-1) + k_s + (2^{k_n} - 1) \cdot (k-1).$$

Using that $k_s + k_n \le k - 1$, from the above equation we get that

$$|V(G)| \le 2(k-1) + (2^{k-1} - 1) \cdot (k-1) = (2^{k-1} + 1) \cdot (k-1),$$

and the theorem follows. The different claims and reduction rules stated throughout the proof are illustrated in Figure 1, where the red larger red vertices are the avoidable vertices of the non-edges of $\bar{M}$.

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /><figcaption>Figure 1 Illustration of the configuration considered in the proof of Theorem 2.</figcaption></figure>

It is worth mentioning that the analysis of the kernel size in the proof of Theorem 2 is tight. Indeed, let $G$ consist of an antimatching $\bar{M}$ of size $k-1$, and let $K$ consist of $2^{k-1}-1$ equivalence classes with $k-1$ vertices, each having a distinct non-complete neighborhood in the set consisting of one (arbitrary) vertex of each non-edge in $\bar{M}$. One can easily check that $|V(G)| = (2^{k-1} + 1) \cdot (k-1)$, that none of Rule 1 and Rule 2 can be applied to $G$, and that $G$ contains no antimatching strictly larger than $k-1$.

We complement the result of Theorem 2 by showing that, unless $NP \subseteq \text{coNP/poly}$, the problem does not admit polynomial kernels.

**Theorem 3.** The DUAL WEIGHTED COLORING problem does not admit a polynomial kernel unless $NP \subseteq \text{coNP/poly}$, even on split graphs with only two different weights.
XX:10 Dual parameterization of Weighted Coloring

**Proof.** We present a polynomial parameter transformation from the SET COVER problem parameterized by the size of the universe; Dom et al. [15] proved that this problem does not admit a polynomial kernel unless NP ⊆ coNP/poly. Our reduction is almost the same as the reduction of Demange et al. [12] from SET COVER to WEIGHTED COLORING on split graphs, only the vertex weights change. Let (U, S, k, ℓ) be an instance of SET COVER, where S is a family of sets of elements over a universe U of size k, and the question is whether there exists a subset S' ⊆ S of at most ℓ sets covering all the elements of U. We construct an instance (G, w, k') of DUAL WEIGHTED COLORING as follows. The graph G contains a clique K on |S| vertices and an independent set I on k vertices. The vertices of K and I are associated, respectively, with the sets in S and the elements in U. There is an edge between a vertex in K and a vertex in I if and only if the corresponding set does not contain the corresponding element. All the vertices in K have weight ℓ, and all the vertices in I have weight ℓ + 1. Note that G is indeed a split graph with only two different weights. Finally, we set k' = k(ℓ + 1) − ℓ. See Figure 2 for an illustration. Since we can clearly assume that ℓ ≤ k, as otherwise the instance is trivial, it follows that k' = O(k²), which is required in a polynomial parameter transformation. We claim that (U, S, k, ℓ) is a yes-instance of SET COVER if and only if σ(G, w) ≤ ∑_{v∈V(G)} w(v) − k'.

<figure><img src="image_7.png" /><figcaption>Figure 2 Instance (G, w, k') of DUAL WEIGHTED COLORING defined in the proof of Theorem 3.</figcaption></figure>

Assume first that (U, S, k, ℓ) is a yes-instance, and let S' ⊆ S be a solution with |S'| ≤ ℓ.
We define a coloring c of G as follows. We start with a color for each vertex in K and, for every
element of U, we include its corresponding vertex of I into one of the colors corresponding
to the sets in S' containing that element. One can easily check that w(c) ≤ |S| · ℓ + ℓ =
∑_{v∈V(G)} w(v) − k'.

Conversely, assume that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k' = |S| \cdot \ell + \ell$, and let $c$ be a coloring of $G$ achieving this bound. Since $\sum_{v \in K} w(v) = |S| \cdot \ell$ and the vertices in $I$ have weight $\ell + 1$, all the vertices in $I$ have to be included in at most $\ell$ out of the $|S|$ colors of $c$ containing the vertices of the clique $K$. By construction of $G$, this is possible only if there exists a subset of at most $\ell$ sets in $S$ covering all the elements of $U$, and the theorem follows. ◀

In view of Theorem 3, in what follows we focus on identifying graph classes on which the
DUAL WEIGHTED COLORING problem admits a polynomial kernel.

► Remark. The problem clearly admits a kernel of size O(k) on sparse graphs, since if there are no large cliques, then the clique K defined in the proof of Theorem 3 (that is, the remaining vertices of those in a maximum antimatching) is of constant size. More formally, if ω is the maximum clique size of a graph in the class, then we get a kernel with at most 2k − 2 + ω vertices.
From now on we focus on graph classes with arbitrarily large cliques. We first present a simple quadratic kernel on comparability graphs. Recall that a comparability graph is a graph that admits a *transitive orientation*, that is, an orientation of the edges of the graph such that the adjacency relation of the resulting directed graph is transitive. Note that the WEIGHTED COLORING problem is NP-hard on comparability graphs, since they are bipartite [12].

**Proposition 4.** *The DUAL WEIGHTED COLORING problem restricted to comparability graphs admits a quadratic kernel.*

**Proof.** Let $G$ be a comparability graph, let $\bar{M}$ be a maximum antimatching in $G$, and let $K = V(G) \setminus V(\bar{M}) = \{v_1, \dots, v_\ell\}$. Let $\bar{G}$ be a transitive orientation of $G$. Since $K$ is a clique, we may assume that $(v_1, \dots, v_\ell)$ is a path in $\bar{G}$. For a vertex $w \in V(\bar{M})$, note that if $(w, v_i) \in E(\bar{G})$, then $(w, v_j) \in E(\bar{G})$ for every $i \le j \le \ell$, since $\bar{G}$ is transitively oriented. Similarly, if $(v_i, w) \in E(\bar{G})$, then $(v_j, w) \in E(\bar{G})$ for $1 \le j \le i$.

Let $A = \{v_i \in K \mid \exists w \in V(\bar{M}), (w, v_i) \in E(\bar{G}), \forall j < i, (w, v_j) \notin E(\bar{G})\}$ and let $B = \{v_i \in K \mid \exists w \in V(\bar{M}), (v_i, w) \in E(\bar{G}), \forall j > i, (v_j, w) \notin E(\bar{G})\}$. Note that, since $G$ is a comparability graph, $|A|, |B| \le |V(\bar{M})|$.

Now, let $v_i, v_{i+1}$ be vertices of $K$ such that $\{v_i, v_{i+1}\} \cap A = \emptyset$ and $\{v_i, v_{i+1}\} \cap B = \emptyset$. Note that it holds that $N[v_i] = N[v_{i+1}]$, since $K \subseteq N[v_i] \cap N[v_{i+1}]$ and if $N[v_i] \neq N[v_{i+1}]$ one of them would belong to either $A$ or $B$, by definition of these sets.

Hence, using the notation defined in the proof of Theorem 2, the set $C = K \setminus (A \cup B)$ contains at most $2|V(\bar{M})| + 1$ equivalence classes. After application of Rule 2, at most $k-1$ elements of each equivalence class will remain, resulting in a kernel of size at most $|V(\bar{M})| + |A| + |B| + (2|V(\bar{M})| + 1)(k-1)$. Using the fact that $|A|, |B| \le |V(\bar{M})| \le 2(k-1)$, the result follows. ◀

In our next result we provide a polynomial kernel on another relevant class of dense graphs, namely that of interval graphs, that is, intersection graphs of a set of arcs on the real line.

**Proposition 5.** *The DUAL WEIGHTED COLORING problem restricted to interval graphs admits a kernel with at most $k^3 - k^2 + k - 1$ vertices.*

**Proof.** We will proceed as in the proof of Theorem 2 and show that, if the input graph $G$ is an interval graph, then the number of equivalence classes is quadratic in the parameter $k$. As before, we assume that $\bar{M}$ is a maximum antimatching of $G$, that $|\bar{M}| \le k-1$, and that Rule 1 and Rule 2 have been exhaustively applied. We also consider $K = V(G) \setminus V(\bar{M})$ and, as before, note that $K$ induces a clique.

We will show that the number of maximal cliques of $G$ is bounded by a linear function of $|\bar{M}|$. For that, we will make use of a well-known result of Fulkerson and Gross [22] stating that a graph $G$ is an interval graph if and only if the 0/1 incidence matrix $M$ of vertices and maximal cliques of $G$ has the *consecutive ones property*, i.e., the columns of $M$ can be permuted so that the ones in each row appear consecutively. A consequence of this result is that the set $C$ of maximal cliques of $G$ can be arranged as $\{C_1, \dots, C_p\}$ in such a way that, for each vertex $v$, there are indices $\ell_v$ and $r_v$ such that $v \in C_i$ if and only if $\ell_v \le i \le r_v$. It is worth mentioning that this property appears implicitly in [23, proof of Theorem 2].

Note that the incidence of a vertex to the maximal cliques completely defines its neighborhood. This implies that $G$ has at most $\binom{p}{2}$ neighborhood classes. Hence, for obtaining a cubic kernel it suffices to show that $p = O(k)$. In what follows we provide explicit bounds on both $p$ and the size of the kernel; we will show later that these bounds are tight.
XX:12 Dual parameterization of Weighted Coloring

**Claim 5.** Let $G$ be an interval graph with $p \ge 2$ maximal cliques and let $\bar{M}$ be a maximum antimatching of $G$. Then $p \le 2|\bar{M}| + 1$.

**Proof.** We proceed by induction on $p$. Clearly, if $p \in \{2,3\}$, then there are at least two non-adjacent vertices, so $|\bar{M}| \ge 1$ and $p \le 2|\bar{M}| + 1$.

Let $\{C_1, \dots, C_p\}$ be an ordering of the maximal cliques of $G$ as defined above. Since the $C_i$'s are maximal cliques, for any two consecutive cliques $C_i$ and $C_{i+1}$ it holds that $C_i \setminus C_{i+1} \ne \emptyset$ and $C_{i+1} \setminus C_i \ne \emptyset$. In particular, together with the consecutive ones property, this implies that $C_1$ has at least one exclusive vertex $u_1$, that is, a vertex that does not belong to any maximal clique other than $C_1$. Similarly, $C_p$ has at least an exclusive vertex $u_p$. Let $G' = G[V(G) \setminus \{U_1 \cup U_p\}]$ be the graph obtained by removing all exclusive vertices of $C_1$ and $C_p$, respectively denoted by $U_1$ and $U_p$ (that is, $U_1 = C_1 \setminus C_2$ and $U_p = C_p \setminus C_{p-1}$). Moreover, let $\bar{M}'$ be a maximum antimatching of $G'$ and $p'$ be the number of maximal cliques of $G'$.

Note that $C_2, \dots, C_{p-1}$ are the maximal cliques of $G'$, because each one contains an exclusive vertex that has not been removed. Hence $p' = p-2$ and, by the induction hypothesis, $p' \le 2|\bar{M}'| + 1$. On the other hand, $|\bar{M}'| \le |\bar{M}| - 1$, otherwise $\bar{M}' \cup \{u_1 u_p\}$ would be an antimatching of cardinality greater than $|\bar{M}|$ in $G$. Putting all together,

$$p-2 = p' \le 2|\bar{M}'| + 1 \le 2(|\bar{M}'| - 1) + 1 = 2|\bar{M}'| - 1,$$

and $p \le 2|\bar{M}| + 1$, completing the proof of the claim.

<figure><img src="image_8.png" /></figure>

Since $K$ is a clique, there is an index $i$ such that $K \subseteq C_i$. For each $v \in K$, let $\ell_v$ be the smallest index such that $v \in C_{\ell_v}$ and $r_v$ be the largest index such that $v \in C_{r_v}$. Recall that $\ell_v$ and $r_v$ completely define the neighborhood of $v$. Note that for all $v \in K$, $\ell_v \le i \le r_v$ and that either $\ell_v \ne 1$ or $r_v \ne p$, since otherwise $v$ would be a universal vertex, which is impossible because we applied Rule 1 exhaustively. Hence, the maximum number of distinct possible combinations of indices $\ell_v$ and $r_v$ is $i \cdot (p - i + 1) - 1$, which is maximized when $i = \lfloor \frac{p+1}{2} \rfloor$, giving a total number of

$$\lfloor \frac{p+1}{2} \rfloor \cdot \lfloor \frac{p+1}{2} \rfloor - 1$$

distinct equivalence classes. Using the fact that $p \le 2|\bar{M}|+1$ by Claim 5, and that $|\bar{M}| \le k-1$, we get

$$\lfloor \frac{p+1}{2} \rfloor \cdot \lfloor \frac{p+1}{2} \rfloor - 1 = k^2 - 1.$$

Since, by virtue of the application of Rule 2, each class has at most $(k-1)$ elements, we have

$$|V(G)| = |V(\bar{M})| + |V(K)| \le 2(k-1) + (k-1) \cdot (k^2 - 1) = k^3 - k^2 + k - 1.$$

<figure><img src="image_9.png" /></figure>

Similarly to Theorem 2, we can show that the analysis of the kernel size in the proof of Proposition 5 is tight. Indeed, given an integer $k$, it is possible to build an interval graph with $2k-1$ maximal cliques, with $(k-1)$ vertices belonging exactly to cliques $C_i, \dots, C_j$, for each

$$(i, j) \in [1, k] \times [k, 2k-1] \setminus \{(1, 2k-1)\},$$

and one exclusive vertex in each clique, except for clique $C_k$, corresponding to vertices of $V(\bar{M})$. That interval graph attains the bound in the statement of Proposition 5 and cannot be reduced by Rule 1 or Rule 2.
Note that the result of Proposition 5 cannot be generalized to chordal graphs, as split graphs are chordal, and by Theorem 3 the existence of a polynomial kernel on split graphs would imply that $NP \subseteq coNP/poly$. Another natural candidate would be the class of circular-arc graphs, that is, intersection graphs of a set of arcs on a circle. However, if one tries to mimic the proof of Proposition 5 for circular-arc graphs, one encounters a major obstacle: there is no simple characterization of circular-arc graphs by a (circular) consecutive ones property of their vertex-maximal clique adjacency matrix [37, 40]. Nevertheless, we can obtain a cubic kernel for a natural subclass of circular-arc graphs that strictly generalizes interval graphs, namely normal Helly circular-arc graphs, that is, circular-arc graphs that are both normal and Helly. A circular-arc graph is normal if it admits an intersection model in which no two arcs cover the circle. Helly circular-arc graphs are defined as intersection graphs of a set of arcs on a circle having the Helly property, that is, such that any pairwise intersecting set of arcs have a non-empty common intersection, as it happens on interval graphs. Equivalently, Helly circular-arc graphs can be defined as those graphs whose incidence matrix $M$ of vertices and maximal cliques has the circular consecutive ones property, i.e., the columns of $M$ can be permuted so that the ones in each row appear consecutively in a cyclic way [37]. Normal Helly circular-arc graphs can be recognized in polynomial time and have nice structural and algorithmic properties [36].

**Proposition 6.** The DUAL WEIGHTED COLORING problem restricted to normal Helly circular-arc graphs admits a cubic kernel.

*Proof.* A circular-arc model of a graph $G$, or simply a model, $M = (C, \mathcal{A})$ is a circle $C$ and a collection $\mathcal{A}$ of arcs of $C$. We can assume that $\mathcal{A}$ covers the entire $C$, as otherwise $G$ is an interval graph and the result follows by Proposition 5. We can also assume that we have a circular-arc model of $G$ respecting the Helly and the normality properties at hand, since Normal Helly circular-arc graphs can be recognized in polynomial time [36].

We proceed as in the proof of Proposition 5, and we will again prove that, if the input graph $G$ is a normal Helly circular-arc graph, then the number of equivalence classes is quadratic in the parameter $k$, by showing that the number of maximal cliques of $G$ is bounded by a linear function of $|\bar{M}|$. For that, we now use the circular consecutive ones property of Helly circular-arc graphs discussed above, which implies that the set $C$ of maximal cliques of $G$ can be cyclically arranged as $\{C_1, \dots, C_p\}$ in such a way that, for each vertex $v$, there are indices $\ell_v$ and $r_v$ such that $v \in C_i$ if and only if $\ell_v \le i \le r_v$, the indices being taken modulo $p$. This implies that $G$ has at most $2(\frac{p}{2})$ neighborhood classes, hence Claim 7 below, which is the equivalent of Claim 5, concludes the proof. Before proving Claim 7, we need another claim.

**Claim 6.** The removal of a vertex from a normal Helly circular-arc graph decreases its number of maximal cliques by at most two.

*Proof.* Let $G$ be a normal Helly circular-arc graph given along with a circular-arc model $(C, \mathcal{A})$ respecting the normality and Helly properties, let $u \in V(G)$ be an arbitrary vertex, and let $G_u$ be the graph obtained from $G$ by removing $u$. Note that $G_u$ is also a normal Helly circular-arc graph and that the model obtained from $(C, \mathcal{A})$ by removing the arc associated with $u$ is a circular-arc model of $G_u$ respecting the normality and Helly properties. By the Helly property, with each maximal clique $C$ of $G$ we can associate a point $p(C)$ in the circle where all the arcs in $C$ intersect.

If $u$ is contained in at most two maximal cliques, the claim clearly holds, so assume that $u$ is contained in at least three maximal cliques. Fix a clockwise orientation of the circle,
XX:14 Dual parameterization of Weighted Coloring

and let $p(C_f)$ and $p(C_\ell)$ be the first and last points in the circle, respectively, among all the points associated with the maximal cliques containing $u$. The removal of $u$ may cause the cliques $C_f$ and $C_\ell$ not be maximal anymore in $G_u$. Assume for contradiction that a third maximal clique $C$ of $G$ is not maximal anymore in $G_u$. Clearly, $u \in C$, and $C$ is different from $C_f$ and $C_\ell$ by hypothesis. Since $C, C_f, C_\ell$ are different maximal cliques in $G$, there is a vertex $v_1 \in C \setminus C_\ell$ and a vertex $v_2 \in C \setminus C_f$. Since $C \setminus \{u\}$ is not maximal in $G_u$, there exists a clique $C'$ in $G_u$ with $C \setminus \{u\} \subseteq C'$. Note that $u \notin C'$, as otherwise $C \subseteq C'$ and $C$ would not be maximal in $G$. Therefore, $p(C')$ is disjoint from the arc associated with $u$ in $G$. Since $v_1, v_2 \in C \cap C'$, $v_1 \notin C_\ell$, and $v_2 \notin C_f$, it follows that $v_1 \neq v_2$ and that the union of the two arcs associated with $v_1$ and $v_2$ covers the whole circle, a contradiction to the hypothesis that $(C, A)$ is a circular-arc model of $G$ respecting the normality property; see Figure 3 for an illustration. ◀

<figure><img src="image_10.png" /><figcaption>Figure 3 Illustration of the configuration considered in the proof of Claim 6.</figcaption></figure>

**Claim 7.** Let $G$ be a normal Helly circular-arc graph with $p$ maximal cliques and let $\bar{M}$ be a maximum antimatching of $G$. Then $p \le 4|\bar{M}| + 1$.

**Proof.** We will prove the claim by induction on the number of vertices of $G$, the cases where $|V(G)| \le 3$ holding trivially. If $G$ is a clique, $|\bar{M}| = 0$, $p = 1$, and the claim holds. Otherwise, let $u$ and $v$ be a pair of non-adjacent vertices in $G$, let $G' = G[V(G) \setminus \{u, v\}]$, and let $p'$ and $\bar{M}'$ be the number of maximal cliques and a maximum antimatching of $G'$, respectively. Clearly, since $\{u, v\} \notin E(G)$, we have that $|\bar{M}'| \le |\bar{M}| - 1$, and by Claim 6 we have that $p' \ge p - 4$. Thus, by applying induction we have that

$$p \le p' + 4 \le (4|\bar{M}'| + 1) + 4 \le 4(|\bar{M}| - 1) + 5 = 4|\bar{M}| + 1,$$

and the claim follows. ◀

The above claim implies that $G$ has $O(k^2)$ equivalence classes that, together with exhaustive application of Rule 2, yield the desired cubic kernel. ◀

Our last result deals with a subclass of split graphs motivated by the fact that DUAL WEIGHTED COLORING on split graphs seems to have a close relation with the SET COVER problem.

**Proposition 7.** The DUAL WEIGHTED COLORING problem restricted to split graphs such that each vertex in the clique has at most $d$ non-neighbors in the stable set, for some constant $d \ge 1$, admits a kernel with at most $k^{d+1}$ vertices. Furthermore, for any $d \ge 2$ and $\epsilon > 0$, a kernel with $O(k^{\frac{d-3}{2}-\epsilon})$ vertices does not exist unless $\text{NP} \subseteq \text{coNP/poly}$.
**Proof.** For the positive result, let $(G, w, k)$ be an instance of DUAL WEIGHTED COLORING, with $G$ being a split graph such that each vertex in the clique has at most $d$ non-neighbors in the stable set, for some integer $d \ge 2$. We mimic the proof of Theorem 2, and we slightly change the analysis. Recall that $|V(\bar{M})| \le 2(k-1)$ and that the number of special classes in $\mathcal{C}$, each containing exactly one vertex, is at most $k_s$. Concerning the normal classes in $\mathcal{C}$, we will obtain an improved bound using that each vertex in the clique has at most $d$ non-neighbors in the stable set, and therefore in the graph $G$ itself as well. Thus, the number of distinct neighborhoods in the set consisting of the avoidable vertices in the normal edges in $\bar{M}$, which is an upper bound on the number of normal classes, is at most $\sum_{i=0}^{d} \binom{k_n}{i} \le \sum_{i=0}^{d} \binom{k_n}{i} \le \max\{2, k_n^d\}$, where the last inequality can be easily proved by induction.

Therefore, if $(G, w, k)$ is a reduced instance, then

$$ \begin{aligned} |V(G)| &= |V(\bar{M})| + |K| \le 2(k-1) + k_s + k_n^d \cdot (k-1) \\ &\le 2(k-1) + (k-1)^d \cdot (k-1) \le k^{d+1}. \end{aligned} $$

For the negative result, we reuse the reduction of Theorem 3, but starting from the $d$-SET COVER problem, that is, the restriction of SET COVER to instances where each set contains at most $d$ elements. Hermelin and Wu [30] proved that, for any fixed $d \ge 2$, $d$-SET COVER does not admit kernels of size $\mathcal{O}(k^{d-3-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly, where $k$ is the size of the solution. Nevertheless, in the hardness proof for $d$-SET COVER given in [30], the size of the universe of the constructed instance is equal to $kd$. Therefore, we can conclude that $d$-SET COVER does not admit kernels of size $\mathcal{O}(k^{d-3-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly, where $k$ is the size of the universe. Moreover, the results in [30] also rule out the existence of a bikernel, that is, a relaxed kernelization notion where the output instance is not necessarily of the same problem.

Given an instance $(U, S, k, \ell)$ of $d$-SET COVER, where $k$ is the size of the universe, we construct an instance $(G, w, k')$ of DUAL WEIGHTED COLORING as in the proof of Theorem 3. Note that $G$ is indeed a split graph such that each vertex in the clique has at most $d$ non-neighbors in the stable set, and recall that $k' = k(\ell+1) - \ell$. Since we may assume that $\ell \le k$, it follows that $k' \le k^2$. Assume for contradiction that DUAL WEIGHTED COLORING restricted to this type of instances admits a kernel with $\mathcal{O}(k^{\frac{d-3}{2}-\epsilon})$ vertices, for some $\epsilon > 0$. Then the composition of the above reduction with such a kernel would yield a bikernel for $d$-SET COVER of size $\mathcal{O}(k^{d-3-\epsilon})$ for some $\epsilon > 0$, which is impossible by the results of [30] unless NP $\subseteq$ coNP/poly. ◀

# 5 Further research

In this article we investigated the dual parameterization of the WEIGHTED COLORING problem, and we provided several positive and negative results, especially concerning polynomial kernelization. It would be interesting to identify other classes of (dense) graphs on which the problem admits polynomial kernels. For instance, the existence of a polynomial kernel on circular-arc graphs, and even on Helly or normal circular-arc graphs, remains open. It remains to close the gap in the degree of the polynomial kernels on the subclasses of split graphs considered in Proposition 7. Another question is whether the cubic kernel on interval graphs given in Proposition 5 can be improved, even on proper interval graphs.

Concerning Theorem 1, using the techniques of Björklund et al. [4] it may be possible to compute the values $T(X, i)$ defined in the proof, for every $X$ and $i$, in time $2^{|V(\bar{M})|} \cdot n^{\mathcal{O}(1)} \cdot \max_{v \in V(G)} w(v)$, which would yield an overall running time of $4^k \cdot n^{\mathcal{O}(1)} \cdot \max_{v \in V(G)} w(v)$.
XX:16 Dual parameterization of Weighted Coloring

Finally, one could try to prove lower bounds under the SETH (see [38]) on the running time of any FPT algorithm solving DUAL WEIGHTED COLORING, hopefully getting close to the running time given in Theorem 1.

References

1 J. Araújo, J. Baste, and I. Sau. Ruling out FPT algorithms for Weighted Coloring on forests. *Theoretical Computer Science*, 729:11–19, 2018.

2 J. Araújo, N. Nisse, and S. Pérennes. Weighted coloring in trees. *SIAM Journal on Discrete Mathematics*, 28(4):2029–2041, 2014.

3 M. Basavaraju, M. C. Francis, M. S. Ramanujan, and S. Saurabh. Partially polynomial kernels for set cover and test cover. *SIAM Journal on Discrete Mathematics*, 30(3):1401–1423, 2016.

4 A. Björklund, T. Husfeldt, and M. Koivisto. Set partitioning via inclusion-exclusion. *SIAM Journal on Computing*, 39(2):546–563, 2009.

5 H. L. Bodlaender, R. G. Downey, M. R. Fellows, and D. Hermelin. On problems without polynomial kernels. *Journal of Computer and System Sciences*, 75(8):423–434, 2009.

6 H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Kernelization lower bounds by cross-composition. *SIAM Journal on Discrete Mathematics*, 28(1):277–305, 2014.

7 H. L. Bodlaender, S. Thomassé, and A. Yeo. Kernel bounds for disjoint cycles and disjoint paths. *Theoretical Computer Science*, 412(35):4570–4578, 2011.

8 É. Bonnet and V. T. Paschos. Dual parameterization and parameterized approximability of subset graph problems. *RAIRO - Operations Research*, 51(1):261–266, 2017.

9 B. Chor, M. Fellows, and D. W. Juedes. Linear Kernels in Linear Time, or How to Save *k* Colors in $O(n^2)$ Steps. In *Proc. of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 3353 of LNCS, pages 257–269, 2004.

10 M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. *Parameterized Algorithms*. Springer, 2015.

11 D. de Werra, M. Demange, B. Escoffier, J. Monnot, and V. T. Paschos. Weighted coloring on planar, bipartite and split graphs: Complexity and approximation. *Discrete Applied Mathematics*, 157(4):819–832, 2009.

12 M. Demange, D. de Werra, J. Monnot, and V. T. Paschos. Weighted node coloring: When stable sets are expensive. In *Proc. of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 2573 of LNCS, pages 114–125. Springer, 2002.

13 M. Demange, P. Grisoni, and V. T. Paschos. Approximation results for the minimum graph coloring problem. *Information Processing Letters*, 50(1):19–23, 1994.

14 R. Diestel. *Graph Theory*, volume 173. Springer-Verlag, 4th edition, 2010.

15 M. Dom, D. Lokshtanov, and S. Saurabh. Kernelization Lower Bounds Through Colors and IDs. *ACM Transactions on Algorithms*, 11(2):13:1–13:20, 2014.

16 R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013.

17 R. Duh and M. Fürer. Approximation of *k*-Set Cover by Semi-Local Optimization. In *Proc. of the 29th Annual ACM Symposium on the Theory of Computing (STOC)*, pages 256–264, 1997.

18 B. Escoffier. Saving colors and max coloring: Some fixed-parameter tractability results. In *Proc. of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, volume 9941 of LNCS, pages 50–61, 2016.

19 B. Escoffier, J. Monnot, and V. T. Paschos. Weighted coloring: further complexity and approximability results. *Information Processing Letters*, 97(3):98–103, 2006.

20 F. V. Fomin and D. Kratsch. *Exact Exponential Algorithms*. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010.
21 L. Fortnow and R. Santhanam. Infeasibility of instance compression and succinct PCPs for NP. *Journal of Computer and System Sciences*, 77(1):91–106, 2011.

22 D. Fulkerson and O. Gross. Incidence matrices and interval graphs. *Pacific journal of mathematics*, 15(3):835–855, 1965.

23 P. Gilmore and A. Hoffman. A characterization of comparability graphs and of interval graphs. *Canadian Journal of Mathematics*, 16:539–548, 1964.

24 D. J. Guan and X. Zhu. A coloring problem for weighted graphs. *Information Processing Letters*, 61(2):77–81, 1997.

25 G. Z. Gutin, M. Jones, and A. Yeo. Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems. *Theoretical Computer Science*, 412(41):5744–5751, 2011.

26 M. M. Halldórsson. Approximating discrete collections via local improvements. In *Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 160–169, 1995.

27 M. M. Halldórsson. Approximating *k*-Set Cover and Complementary Graph Coloring. In *Proc. of the 5th International Conference on Integer Programming and Combinatorial Optimization (IPCO)*, volume 1084 of LNCS, pages 118–131, 1996.

28 R. Hassin and S. Lahav. Maximizing the number of unused colors in the vertex coloring problem. *Information Processing Letters*, 52(2):87–90, 1994.

29 F. Havet and L. Sampaio. On the Grundy and *b*-Chromatic Numbers of a Graph. *Algorithmica*, 65(4):885–899, 2013.

30 D. Hermelin and X. Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In *Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 104–113, 2012.

31 R. Impagliazzo and R. Paturi. On the Complexity of *k*-SAT. *Journal of Computer and System Sciences*, 62(2):367–375, 2001.

32 R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? *Journal of Computer and System Sciences*, 63(4):512–530, 2001.

33 R. M. Karp. Reducibility among combinatorial problems. In *Proc. of a symposium on the Complexity of Computer Computations*, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.

34 T. Kavitha and J. Mestre. Max-coloring paths: tight bounds and extensions. *Journal of Combinatorial Optimization*, 24(1):1–14, 2012.

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

36 M. C. Lin, F. J. Soulignac, and J. L. Szwarcfiter. Normal helly circular-arc graphs and its subclasses. *Discrete Applied Mathematics*, 161(7-8):1037–1059, 2013.

37 M. C. Lin and J. L. Szwarcfiter. Characterizations and recognition of circular-arc graphs and subclasses: A survey. *Discrete Mathematics*, 309(18):5618–5635, 2009.

38 D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the Exponential Time Hypothesis. *Bulletin of the EATCS*, 105:41–72, 2011.

39 S. V. Pemmaraju, S. Penumatcha, and R. Raman. Approximating interval coloring and max-coloring in chordal graphs. *ACM Journal of Experimental Algorithmics*, 10, 2005.

40 A. Tucker. Matrix characterizations of circular-arc graphs. *Pacific Journal of Mathematics*, 39(2):535–545, 1971.

41 C. Yap. Some consequences of non-uniform conditions on uniform classes. *Theoretical Computer Science*, 26:287–300, 1983.