Applying Convex Integer Programming: Sum Multicoloring and
Bounded Neighborhood Diversity
Tomáš Gavenčiak1 , Dušan Knop1,2 , and Martin Koutecký1,3

arXiv:1711.02032v1 [] 6 Nov 2017

1

Department of Applied Mathematics, Charles University, Prague, Czech Republic
2
Department of Informatics, Univerisity of Bergen, Bergen, Norway
3
Technion - Israel Institute of Technology, Haifa, Israel
November 7, 2017
Abstract
In the past 30 years, results regarding special classes of integer linear (and, more generally, convex)
programs flourished. Applications in the field of parameterized complexity were called for and the
call has been answered, demonstrating the importance of connecting the two fields. The classical
result due to Lenstra states that solving Integer Linear Programming in fixed dimension is
polynomial. Later, Khachiyan and Porkolab has extended this result to optimizing a quasiconvex
function over a convex set. While applications of the former result have been known for over 10
years, it seems the latter result has not been applied much in the parameterized setting yet. We give
one such application.
Specifically, we deal with the Sum Coloring problem and a generalization thereof called
Sum-Total Multicoloring, which is similar to the preemptive Sum Multicoloring problem. In
Sum Coloring,
P we are given a graph G = (V, E) and the goal is to find a proper coloring c : V → N
minimizing v∈V c(v). By formulating these problems as convex integer programming in small dimension, we show fixed-parameter tractability results for these problems when parameterized by the
neighborhood diversity of G, a parameter generalizing the vertex cover number of G.

1

Introduction

In 1983 Lenstra proved that solving integer linear programming (ILP) is polynomial in fixed dimension [Len83]. In the subsequent years this result has been extended by many authors to wider optimization classes (e.g. minimizing a quasiconvex function over a convex set) and improved in running
time and space. The setting of these results fits well with that of parameterized complexity. There, the
complexity of a problem is studied as a function of not just the size of the input, but also of multiple
parameters, allowing for a more refined analysis and classification of runtimes. In the case of convex
integer programming the dimension is a natural parameter.
Consequently, several authors called for applications of ILP in the field of parameterized complexity,
e.g. Niedermeier in his book [Nie04]:
[...] It remains to investigate further examples besides Closest String where the described
ILP approach turns out to be applicable. More generally, it would be interesting to discover
more connections between fixed-parameter algorithms and (integer) linear programming.
This call has been answered in the following years, for example by Fellows et al. [FLM+ 08] in a paper
studying graph layout problems parameterized by vertex cover, Lampis [Lam12] and Ganian [Gan12]
when studying a related parameter called neighborhood diversity, or by Mnich and Wiese [MW15] when
studying scheduling problems.
Curiously, it seemed that a problem can either be tackled already by use of integer linear programming,
or not even the advanced results regarding integer convex programming suffice. This naturally lead to
an interest in problems requiring the use of these advanced techniques, as Lokshtanov states in his PhD
thesis [Lok09]:
1

It would be interesting to see if these even more general results can be useful for showing
problems fixed parameter tractable.
In this paper, we give one such example. We show that the Sum-Total Multicoloring problem, a
generalization of Sum Coloring, is fixed-parameter tractable with respect to the neighborhood diversity
of the input graph and the number of different vertex demands. We do so by minimizing a (non-linear)
convex function over integral points of a polyhedron. We also discuss how, under certain assumptions,
a Sum-Total Multicoloring instance admits reformulation to a mixed integer linear program. The
technique we use to do so has been known for a long time, but has been only scarcely used in parameterized
complexity.
Furthermore, we give a short review of the advances in the field of convex integer programming
from the past 25 years that we find particularly relevant, with a particular emphasis on results in fixeddimension. We do this with the hope of providing an accessible toolbox to the benefit of parameterized
complexity researchers.

1.1

Neighborhood Diversity

Courcelle’s theorem [Cou90] states that deciding a Monadic Second Order (MSO) formula on a graph
of treewidth k can be done in time f (k, ϕ)n for some computable function f . However, this function f
is non-elementary and this cannot be improved unless P=NP [FG04, Lam14]. Thus a question arose: is
there a graph class such that MSO formulas can be decided in f (k, ϕ)n time for an elementary function
f ? This question was answered in the affirmative by Lampis [Lam12] for graphs of bounded vertex cover
and neighborhood diversity.
Definition 1. The neighborhood diversity of a graph G, denoted by nd(G), is the minimum number t
of classes (called types) of a partition V1 , . . . , Vt of the vertex set VG such that
• each type Vi induces either an empty subgraph (independent type) or a complete subgraph (clique
type) of G, and
• for each distinct Vi and Vj there are either no edges between Vi and Vj , or every vertex of Vi is
adjacent to all vertices of Vj .
cw
mw

tw

Figure 1: A map of assumed parameters. Full arrow stands
for linear upper bounds, while dashed arrow stands for exponential upper bounds. Note that treewidth and neighborhood diversity are incomparable. This can be observed by checking that,
tw(Kn ) = n − 1

nd
vc

nd(Kn ) = 1

tw(Pn ) = 1
nd(Pn ) = n,
where Kn and Pn are the complete graph and path on n vertices,
respectively.

Observe in Figure 1 that neighborhood diversity occupies an important place with respect to other
relevant parameters (vertex cover number, treewidth and cliquewidth). Studying the parameterized
complexity of a problem with respect to treewidth can be seen as a stepping stone to understanding its
parameterized complexity with respect to cliquewidth. Since neighborhood diversity is incomparable to
treewidth in this regard, it provides a different step towards cliquewidth and gives different insights. The
next possible step towards cliquewidth is so-called modular width introduced by Gajarský et al. [GLO13]
as a direct generalization of neighborhood diversity.
Notice that an n-vertex graph
 of bounded neighborhood diversity can be described in a compressed
way using only O log n · nd(G)2 space:

Definition 2. The type graph T (G) of a graph G is a graph on nd(G) vertices t1 , . . . , tnd(G) , where
each ti is assigned weight s(ti ) = |Vi |, and where (ti , tj ) is an edge or a loop in T (G) if and only if two
distinct vertices of Vi and Vj are adjacent.
2

1.2

The Sum-Total Multicoloring Problem

A (proper) coloring of a graph G = (V, E) is a function c : V → N satisfying that c(u) 6= c(v) whenever
{u, v} ∈ E. The cost of c is then the number of different colors used, that is |c[V ]|. Here by c[V ] we
denote the set {f (v) | v ∈ V }. The chromatic number χ(G) of G is then the minimum attainable cost of
a proper coloring c of G.
The motivation for this particular formulation is the following coloring problem with a different
objective.

Input:
Task:

Sum Coloring
Graph G = (V, E).
P
Find a proper coloring c of G minimizing v∈V c(v).

In addition to Sum Coloring, we consider a generalized problem combining Sum Coloring with
multicoloring. A (proper) multicoloring of a graph G with given vertex demands (weights) w(v) is a map
c : V → 2N such that c(u) ∩ c(v) = ∅ whenever {u,
S v} ∈ E and |c(v)| ≥ w(v). Similarly, the objective is
to minimize the number of different colors used | c[V ]|. The generalization is then defined as follows.
Input:

Sum-Total Multicoloring
Graph G = (V, E), vertex demands w : V → N.

Task:

Find a proper multicoloring c of G with demands w minimizing

P

v∈V

P


x
.
x∈c(v)

This generalization differs from the classical Sum Multicoloring problem whose objective function
P
is v∈V maxx∈c(v) x. However, we believe it is quite natural and can be motivated as follows. Irani and
Leung [IL96] study scheduling with conflicts in the context of traffic control. Imagine an intersection
which needs to be used by multiple cars. Then our goal is to schedule times when each car can pass
through the intersection such that we avoid collisions, and the satisfaction of drivers can be expressed as
the sum of times when they passed through the intersection. Thus, each individual driver’s completion
time needs to be a part of the objective function, not just the last driver’s, as would be the case if we
modeled the problem as classical Sum Multicoloring.
Let G = (V, E) be a graph, w : V → N be demands and T = {T1 , . . . , Tt } be a decomposition of G
such that the following holds.
• For all v ∈ V there is exactly one i for which v ∈ Ti and
• the demand is the same for all vertices in Ti for every 1 ≤ i ≤ t.
Then, we say that w is uniform for G with respect to decomposition T and we say that (G, T , w) is
an instance of Uniform Sum-Total Multicoloring. In this case we denote the demand of the
vertices of a type Ti by w(Ti ). Note that Sum Coloring is a special case of Uniform Sum-Total
Multicoloring with w ≡ 1 for any T . Note further that it is possible to use the neighborhood diversity
decomposition as a decomposition T .
The Sum Coloring problem has been introduced by Kubicka and Schwenk [KS89]. They showed
that a polynomial algorithm for Sum Coloring would be easily modified to compute the chromatic
number and presented a linear algorithm for computing the Sum Coloring for trees. Furthermore
Erdös et al. [EKS90] gave a constructive proof of the unexpected property that, for any k ≥ 2 and any
positive integer t, there exists a family of k-chromatic graphs for which any optimal sum coloring must
use at least k + t colors. This builds upon a previous result [KS89], where the same was proven for trees.
The Sum Coloring problem is studied because of the natural connection to scheduling. Scheduling
problems form a fundamental class of problems studied in the approximation algorithms theory. Here
the completion time of a job corresponds to the largest assigned color to the associated vertex. One
possible goal is to minimize the average completion time of the jobs, which is the same as to minimize
the sum of the completion times.
Nicoloso et al. [NSS99] and Halldórsson et al. [HKS03] study the Sum Coloring problem on the
class of interval graphs, together with application to scheduling of dependent jobs. Marx [Mar05] gave a
short proof of NP-completeness of Sum Coloring for interval graphs.
3

See Bar-Noy et al. [BHK+ 00] for detailed information about the connection of scheduling and the Sum
Multicoloring problem. Marx [Mar02] showed that the Sum Multicoloring problem is NP-hard
even if restricted to binary trees. Note that this shows also that the Sum Multicoloring problem is
W [1]-hard when parametrized by treewidth. Borodin et al. [BIYZ12] studied approximation algorithms
for several proper intersection families of graphs and for Kk -free graphs.

1.3

Our results

We first extend the original idea of Lampis [Lam12] for coloring of bounded neighborhood diversity graphs
to multicoloring, and then show how to express the objective function of Sum-Total Multicoloring,
and that it is convex:
Theorem 1. Given a graph G with nd(G) = k and a Sum-Total Multicoloring instance with d
different demands, Sum-Total Multicoloring can be expressed as a convex integer program in at
most (2d)k variables.
Using one of existing algorithms for solving convex integer programming in fixed dimension, we get
an FPT result as a corollary:
Corollary 1. The Sum-Total Multicoloring problem parameterized by nd(G) and the number of
different demands d is fixed parameter tractable.
Moreover, we show that in the special case when the vertex demands are bounded by poly(n) (by f
being poly(n) we mean that there exists c ∈ N such that f ∈ O(nc )), the convex integer program can
be reformulated as a mixed integer linear program in p = (2d)k integer variables, poly(n) continuous
variables and poly(n) inequalities. This, unlike in Corollary 1, allows applying MILP solvers which are
mature and run in space poly(p).

2

Convex Integer Programming and Parameterized Complexity

In this section we overview existing results regarding minimization of convex (Subsection 2.1), concave
(Subsection 2.2) and indefinite (Subsection 2.3) objectives in fixed dimension, and also briefly mention
the rapidly growing area of integer linear programming in variable dimension (Subsection 2.4). The
outline is inspired by Chapter 15 of the book 50 Years of Integer Programming [HKLW10], omitting
some parts but including many recent developments.

2.1

Convex Integer Minimization in Fixed Dimension

Lenstra’s result from 1983 shows that solving mixed integer linear programming (MILP) is polynomial
when the integer dimension is fixed [Len83]. This was significantly improved by Kannan [Kan87] and
Frank and Tardos [FT87] in two ways. First, the required space was reduced from exponential to
polynomial in the dimension, and second, running time dependency on the dimension p was reduced
O(p)
from 22
to pO(p) . To solve the optimization variant of MILP using these algorithms one has to
do binary search, as described by Fellows et al. [FLM+ 08]. We would like to point out that while
Lenstra’s result is old, we are aware of only a few [BFN+ 15, JSO10] applications which involve mixed
ILPs. However, as we show in Subsection 3.3, under certain conditions MILP can be used to express a
convex objective function in a way which ILP does not allow.
p-Variable Mixed Integer Linear Programming Optimization (p-Opt-MILP)
Input: A matrix A ∈ Zm×(p+n) and vectors b ∈ Zm and c ∈ Zp+n .
Task:
Find a vector x ∈ Zp × Rn that minimizes (or maximizes) the objective function c⊺ · x and
satisfies the m inequalities, that is, A · x ≤ b. Or report that there is no vector fulfilling
A · x ≤ b.
+
Theorem 2 (Frank and
 Tardos [FT87], Fellows et al. [FLM 08]). It is possible to solve p-Opt-MILP
2.5p
using O p
poly(L) arithmetic operations and space polynomial in L, where L is the number of bits
in the input.

4

This result was later generalized to minimizing a quasiconvex function over a convex set. A function
f : Rn → R is called quasiconvex if for every α ∈ R, the level set {x ∈ Rn | f (x) ≤ α} is a convex subset
of Rn . The first to show this were Khachiyan and Porkolab [KP00], followed by multiple authors (see
below). Unlike above, all of the following results require space exponential in the dimension.
The subsequent research diverged in several directions. The main difference between the papers we
survey is in the formalism chosen to represent the convex set. Since there is no better or worse formalism,
choosing one is a matter of preference with respect to a specific scenario. Another difference is in their
motivation – some authors seek to achieve better time complexity while others contribute by simplifying
existing proofs. Our list is categorized according to the formalism chosen to represent the convex set.
Semialgebraic convex set. Khachiyan and Porkolab [KP00] state their result for minimizing a quasiconvex function over a semialgebraic convex set. These are closely related to spectrahedra, the solution
spaces of semidefinite programs. Independently, convex sets and semialgebraic sets have been studied
for a long time, but together they have been studied only in the past ten years as Convex Algebraic
Geometry. There is a book on the topic by Blekherman, Parillo and Thomas [BPT12]. A drawback of
this result is an exponential dependence on the number of polynomials defining the semialgebraic convex
set.
Theorem 3 (Khachiyan and Porkolab [KP00]). Minimizing a quasiconvex function over a semialgebraic
convex set defined by k polynomials in dimension p is FPT with respect to k and p.
Quasiconvex polynomials. Heinz [Hei05] studied a more specific case of minimizing a quasiconvex
polynomial over a convex set given by a system of quasiconvex polynomials, that is, polynomials that are
quasiconvex functions. His result improves over Khachiyan and Porkolab in terms of time complexity,
dropping
 exponential dependence on the number of polynomials. The dependence on the dimension
 the
3
p is O 2p , which was further improved by Hildebrand and Köppe [HK13] to 2O(p log p) . The latter
result can be stated as follows:

Input:
Task:

p-Variable Polynomial Integer Programming Minimization (p-Min-PIP)
Quasiconvex polynomials F̂ , F1 , . . . , Fm ∈ Z[x] = Z[x1 , . . . , xp ] with integer coefficients.
Either find a vector x ∈ Zp that minimizes the objective function F̂ (x) and satisfies the m
inequalities, that is, Fi (x) < 0, for all i. Or report that no x satisfying Fi (x) < 0, for all i
exists.

o
n
Theorem 4 (Hildebrand and Köppe [HK13]). Given a p-Min-PIP instance with F = F̂ , F1 , . . . , Fm .
Let d ≥ 2 be the upper bound on the degree of each F ∈ F , M is the maximum number of monomials in
each F ∈ F and ℓ bounds the binary length of the coefficients of F . Then it can be solved in time:
• pO(p) · m(rℓM d)O(1) , thus FPT with respect to the dimension p, if the feasible region is bounded
such that r is the binary encoding length of that bound with r ≤ ℓdO(p) ,
• dO(p) p2p · mℓO(1) , thus FPT with respect to the dimension p and the maximum degree d, if the
feasible region is unbounded.
Note that, in particular, the running time is polynomial with respect to the number of polynomials m.
Oracles. Further research lead to splitting the Convex Integer Programming (CIP) problem in two
independent parts to allow more focus on each of them. The first part is showing that a certain problem
formulation (such as quasiconvex polynomial inequalities, semialgebraic set etc.) can be used to give a
set of geometric oracles. The second part is to show that, given these oracles, solving a CIP problem can
be done in a certain time.
This approach is taken by Dadush, Peikert and Vempala [DPV11] who further improve the time complexity of Hildebrand and Köppe [HK13] when the convex set is given by three oracles: a so-called weak
membership, strong separation and weak distance oracles. Observe
 4 that
 the running time of Theorem 4

∗ 2p
∗
p
can be rewritten as O p ; Dadush et al. improve it to O p 3 . Moreover, Dadush claims in his
5

PhD thesis [Dad12] a randomized O∗ (pp ) algorithm; for derandomization cf. [DV13]. (Here and in the
following we use the O∗ notation which suppresses polynomial factors.)
This sequence of results can be seen as a part of a race for the best running time. Dadush [Dad12] classifies existing algorithms as Lenstra-type and Kannan-type, depending on the space decomposition they
use (hyperplane and subspace, respectively). The type of algorithm determines the best possible running
time – Lenstra-type algorithms depend on a so-called
theorem, which gives a lower-bound O∗ (pp ).
 flatness

4

The best known Lenstra-type algorithm is the O∗ p 3 p algorithm of Dadush et al. [DPV11]. Note that
both Theorem 3 and 4 are Lenstra-type algorithms. On the other hand, Kannan-type algorithms could
run as fast as O∗ ((log p)p ) if a certain conjecture of Kannan and Lovász holds [Dad12, Theorem 7.1.3].
The O∗ (pp ) algorithm given in Dadush’s thesis [Dad12] is Kannan-type. It is also worth noting that the
only known lower bound for CIP in general is the trivial one of O∗ (2p ).
The oracle approach is also taken by Oertel, Wagner and Weismantel [OWW14]. They show that
a general convex integer program given by a so-called first order evaluation oracle can be reduced
to several p-Opt-MILP subproblems, which are readily solved by existing solvers (implementing for
example Theorem 2). In a previous paper [OWW12] the same authors take a more generic approach
requiring a set of oracles to solve a minimization problem, and discuss how to construct these oracles
specifically for the p-Min-PIP problem.

2.2

Concave Integer Minimization in Fixed Dimension

When we make the step from a linear to a general quasiconvex objective function, we have to distinguish
carefully between minimization and maximization. Here we mention two results that can be applied in
this case.
Vertex Enumeration. Provided bounds on the encoding length and number of inequalities, a good
bound on the number of vertices of the integer hull exists:
Theorem 5 (Cook et al. [CHKM92]). Let P = {x ∈ Rp | Ax ≤ b} be a rational polyhedron with
A ∈ Qm×p and let φ be the largest binary encoding size of any of the rows of the system Ax ≤ b. Let
P I = conv(P ∩ Zp ) be the integer hull of P . Then the number of vertices of P I is at most 2mp (6p2 φ)p−1 .
Since Hartmann [Har89] also gave an algorithm for enumerating all the vertices running in polynomial
time in fixed dimension, it is possible to evaluate the convex objective function on each of them and
pick the best. This is sufficient, because any convex objective is maximized on the boundary, which will
be a vertex. Moreover, in parameterized complexity ILP is often used to model combinatorial problems,
which implies that the encoding length φ is logarithmic in the input length n. Since (log n)k for fixed k
is order o(n) [CCHM15, Lemma 6.1], convex integer maximization is FPT in all such cases.

2.3

Indefinite Optimization in Fixed Dimension

Results regarding optimizing indefinite polynomials in fixed dimension are few, indicating this area merits
much attention. De Loera et al. [DLHKW08] show that optimizing an indefinite non-negative polynomial
over the mixed-integer points in fixed-dimension polytopes admits a fully-polynomial time approximation
scheme (FPTAS); however, the runtime of this algorithm is XP from the perspective of parameterized
complexity, and it has not yet found applications.
Hildebrand et al. [HWZ16] recently also provided an FPTAS, however, their results are incomparable
to the previous one. On one hand, their results are stronger because they use a different notion of
approximation, and because they do not require the non-negativity of the objective function. On the
other hand, there are additional requirements on the polynomial, namely that it is quadratic and has at
most one negative or at most one positive eigenvalue.
The most significant contribution from the perspective of parameterized complexity is an FPT algorithm for Quadratic Integer Programming by Lokshtanov [Lok15]:
Theorem 6 (Lokshtanov [Lok15]). Let A ∈ Zm×p , Q ∈ Zp×p and b ∈ Zm . The
min {f (x) = x⊺ Qx | Ax ≤ b, x ∈ Zp }
is fixed-parameter tractable parameterized by p, kAk∞ , and kQk∞ .
6

While this parameterization may seem very restrictive, it lead to the resolution of a major open
graph layout problem regading the parameterized complexity of Minimum Linear Arrangement
parameterized by the vertex cover number.

2.4

Integer Linear Programming in Variable Dimension

Two major well-known cases of linear programs (LPs) that can be solved integrally in polynomial time
are LPs in fixed dimension (as discussed above) and LPs given by totally unimodular matrices (such as
flow polytopes). Several significant additional cases have been discovered recently.
Graver basis optimization. A large stream of research of the past 20 years focuses on using the
concept of a Graver basis. For a self-contained exposition of these ideas see the books of Onn [Onn10]
and De Loera, Hemmecke and Köppe [LHK13], or a short survey of Koutecký [Kou16]. Specifically, in
n-fold Integer Programming, the constraint matrix is composed of one row of small matrices D and a
diagonal of small matrices A. In 2-stage stochastic IP, the constraint matrix is composed of one column
of small matrices B and again a diagonal of small matrices A. 4-block n-fold IP combines these two
notions. It is known that, parameterized by the size of blocks and the largest coefficients, n-fold and
2-stage stochastic IP are fixed-parameter tractable, while 4-block n-fold IP is XP. The relevance of these
results is highlighted by Downey and Fellows [DF13]:
Conceivably, [ Minimum Linear Arrangement] might also be approached by the recent
(and deep) FPT results of Hemmecke, Onn and Romanchuk [HOR13] concerning nonlinear
optimization.
As already mentioned, the MLA problem was finally resolved using different methods. However, nfold IPs have lately played an important role in providing exponential speed-ups for several existing FPT
results [KKM17a, KK16] as well as resolving other open problems [KKM17b].
A notable result from this area which has not yet found applications is due to Lee et al. [LORW12].
It states that minimizing even certain non-convex objectives is polynomial-time solvable provided they
fall in the so-called quadratic Graver cone. It would be interesting to see which problems are modeled
by such objectives.
Structural parameterizations of the constraint matrix. A major stream of research in graph
theory and parameterized complexity is that of structural parameterizations of graphs. Recently, it
was shown that similar tools can be applied also to integer programming. Specifically, one may study
structural parameterizations of two graphs associated to the constraint matrix:
1. The primal graph, which has a vertex for every column, and two vertices share an edge if a row
exists where both corresponding entries are non-zero.
2. The incidence graph, which has a vertex for every row and every column, and two vertices share
an edge if they correspond to a row-column coordinate which is non-zero.
One way how to view the results based on Graver bases is via the parameter fracture number : a graph
has a small fracture number if there exists a small subset of vertices whose deletion decomposes the graph
into (possibly many) small components. Dvořák et al. [DEG+ 17] show that ILP parameterized by the
largest coefficient and the constraint or variable fracture number of the primal graph is FPT. In the case
of constraint fracture number, one must delete small set of vertices corresponding only to constraints
of the ILP at hand. The variable fracture number is defined accordingly. They provide an equivalent
instance of either n-fold IP or 2-stage stochastic IP.
Ganian and Ordyniak [GO16] show that when not only the coefficients but also the right hand
sides are bounded by a parameter, than fixed-parameter tractability can be obtained even for the less
restrictive parameter tree-depth of the primal graph. Moreover, they show several hardness results, thus
more clearly delineating the tractable region.
Continuing towards even more general structural parameterizations, let us focus on treewidth. Because ILPs can be viewed as a special case of Constraint Satisfaction
 Problem (CSP), it follows from
Freuder’s algorithm [Fre90] that ILP can be solved in time O∗ dk , where d is the maximum domain
7

size of any variable and k is the primal treewidth. Recently, Jansen and Kratsch [JK15] studied the
kernelizability of ILP and show that instances with bounded domains and bounded primal treewidth are
efficiently kernelizable. Moreover, they introduce so-called r-boundaried ILPs which significantly generalize totally unimodular ILPs and ILPs of bounded treewidth, and they give an FPT result regarding
r-boundaried ILPs.
Finally, Ganian et al. [GOR17] show that ILP parameterized by incidence treewidth and the largest
constraint partial sum of any feasible solution is FPT. They also combine primal treewidth with Lenstra’s
algorithm to obtain a new structural parameter called torso-width, and give an FPT algorithm for this
parameterization.

3

Solving Sum-Total Multicoloring on bounded neighborhood
diversity

3.1

Overview

The algorithms of this section are based on the concept of the vertex coloring polytope of a graph
(in particular its independent set formulation [MT96]),
P where there is a binary variable xI for every
independent set I of G = (V, E) with the constraint I∋v xI = 1 for every v ∈ V . This encodes which
independent sets correspond to
Pactual color classes in a coloring, every vertex being colored exactly once.
The goal is then to minimize I independent xI – the number of used colors.
As Lampis [Lam12] observed any independent type ti can be colored with one color and every clique
type tj needs exactly s(tj ) colors. Every color class of such coloring (and even multicoloring) then
corresponds to an independent set in T (G). Thus, every such coloring can be represented by stating
how many times is each independent set of T (G) used (up to permuting the colors, and permuting the
vertices of clique types). Denote I = {I | I independent in T (G)} the set of independent sets of T (G)
and recall that s(ti ) = |Vi | for every type.
Recall that an instance of Sum Multicoloring is called uniform with respect to decomposition
T = {t1 , . . . , tt } if all vertices in Ti have the same demand (denoted w(ti )) for all i. For graphs of small
neighborhood diversity and uniform demands, this can be expressed as the integer linear programs below,
which have a variable xI for every I ∈ I. Note that since multiple color classes of G can correspond to
one I ∈ I, xI is no longer binary variable.
In the independent set formulation of the vertex coloring polytope an integer point x corresponds
to a certain coloring up to permuting the colors. In our formulation we only capture (multi)colorings
which, for a given color γ and an independent type ti , either color all vertices of ti with γ or none of
them. We call such colorings essential, and, accordingly, the polytope corresponding to our formulation
the essential (multi)coloring polytope.
In case of non-uniform demands of only few different values we may use the following transformation.
Lemma 7. For a graph G with nd(G) = k, type graph
P T and non-uniform demands w, there is a type
graph T ′ with uniform demands w′ such that |T ′ | = ti ∈T |w[Vi ]|, where the last term is the number of
different demand values for Vi .
Proof. Take T and replace every vertex (type) ti with |w[Vi ]| = zi clones (vertices with the same neighborhood), one for every value of w[Vi ], setting w′ to this value and s′ to the number of vertices with such
demand. Then T ′ represents G with equal demands represented uniformly.
While the restriction to a bounded number of different demand values might seem limiting, bear
in mind that, for example, different demand values for every vertex would generally
require Ω(n) sized

input, substantially more that the graph itself requiring only O log n nd(G)2 space. This might be an
indication that general demands could encode problems with significantly higher inner complexity.
Essential Coloring and Uniform Multicoloring polytope

8

Coloring
X
xI = 1
I∈I,ti ∈I

X

xI = s(ti )

I∈I,ti ∈I

Uniform Multicoloring
X
xI = w(ti )

for every ti independent

I∈I,ti ∈I

X

xI = s(ti )w(ti )

for every ti clique

0 ≤ xI

for every I ∈ I

I∈I,ti ∈I

0 ≤ xI

Notice that there are at most 2k independent sets in a graph with nd(G) = k. ThePColoring and
Multicoloring problems then correspond to the above ILPs minimizing the sum
I∈I xI in both
cases, counting the different colors used. In essence, these programs solve a covering problem with I as
the covering sets and types ti as the elements to be covered, requiring each ti to be covered a certain
number of times. This problem has been studied under the name Weighted Set Multicover by
Bredereck et al. [BFN+ 15].
Note that together with the results of the previous section, this also shows that Uniform Multicoloring is FPT with respect to nd(G). However, a stronger FPT result can be obtained for general
Multicoloring by noticing that in any independent type ti only the maximum demand is relevant in
the optimal solution, and similarly, that in any clique type tj only the sum of the demands matters. We
leave the details to the kind reader.

3.2

The Convex Integer Program

While these polytopes also contain all essential solutions to Sum Coloring and Sum-Total Multicoloring problems, their objective function is not as straightforward to obtain. However, given I in a
uniform demand setting, the number of vertices every color class of this type will contain is independent
of the actual xI ’s. Namely, define the number of vertices of a color class σ : I → N ∪ {0} as
X
X
σ(I) =
1+
s(ti ).
ti ∈I
ti clique

ti ∈I
ti indep.

Lemma 8. Given the numbers xI of occurrences of every independent set I ∈ I as a color class inside the
essential (multi)coloring polytope, the assignment to colors 1, 2, . . . minimizing the cost of Sum-Total
Multicoloring is by decreasing σ(I).
Proof. See Figure 2 for an illustration of the situation. The lemma is shown by looking at the price
difference of swapping the numbers assigned to two color classes with different σ.
To get a quadratic objective function, we express it in terms of auxiliary variables y1 , . . . , yn which are
a linear projection of variables x = (xI1 , xI2 , . . . ). Namely, yj indicates how many color classes contain
at least j vertices:
X
xI .
yj =
σ(I)≥j

Finally, the total objective function can be expressed as
S(x) =

p
X

|iσ(Ii )| =

n  
X
yj
j=1

i=1

2

,

where i = 1, . . . , p is the order of the color classes given by Lemma 8, every class of type I present xI
times, where we enumerate only those I with xI ≥ 1. The equivalence of the two is straightforward to
check.
Finally, S is convex with respect to x. This is because:
• all xI are linear (thus affine) functions,
P
• yi = I:σ(I)≥i xI is a sum of affine functions, thus affine,
9

Color number

10
9
8
7
6
5
4
3
2
1

x6
x5
x4
x3
x2
x1

y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11

yn

Number of vertices in a colorclass (σ)
Figure 2: Illustration of the price decomposition to the individual classes. Note that i-th row (color i)
has price i per vertex.
• yi (yi − 1)/2 is convex: it is a basic fact that h(x) = g(f (x)) is convex if f is affine and g is convex.
Here f = yi is affine by the previous point and g = f (f − 1)/2 is convex.
• S is the sum of yi (yi − 1)/2, which are convex by the previous point.
We summarize these observations into the following theorem.
Theorem 9. Given a graph G with nd(G) = k by its type graph T (G) and given uniform demands
w : VT → N, the Sum-Total Multicoloring (as well as Sum Coloring) problem is FPT with respect
O (2k )
to k and can be solved in time 2k
· (log n)O(1) by a PIP solver.
Proof. The essential multicoloring polytope
exactly contains all x corresponding to a valid essential

multicoloring. Such polytope has O 2k variables and O(k) linear constraints, with the coefficients
represented by O(log n) bits each.
The objective function S(x) is a convex function and can be expressed directly in terms of x by
substituting all the yj ’s by their definition. The resulting function can be easily computed in linear time
when the sets of I are preordered by σ.
Finally, the running time follows from the CIP tools presented in the previous section, e.g. Theorem 4.
The Sum Coloring variant is obtained with w ≡ 1.
We also get the following by application of Lemma 8.
Corollary 2. Given a graph G with nd(G) = k by its type graph T (G) and arbitrary demands w : VG → N,
the Sum-Total Multicoloring problem is FPT with respect to k and the number of different demand
values used.

3.3

Reduction to Mixed Integer Linear Programming

Under certain conditions a p-Min-MILP problem with a convex polynomial objective function can be
reformulated as a pure (i.e., linear objective) p-Min-MILP problem. Here we will show how this can be

10

zi
6

Figure 3: f (yi ) can be approximated by a piecewise
linear function given by the integer points of f . The first
four resulting inequalities are:
3

zi ≥ 0zi ≥ yi − 1zi ≥ 2yi − 3zi ≥ 3yi − 6
In general, the j-th inequality is zi ≥ jyi −(j +2)(j +1)/2.

1
yi
1

2

3

4

done in our case if the maximum demand wmax = maxv∈V w(v) is bounded by poly(n) (in particular for
Sum Coloring).
Examine the objective function S(x). It can be seen as an additively separable functionPof n convex
n
univariate functions zi = f (yi ) = yi (yi − 1)/2. Equivalently, we could write it as S(x) = i=1 zi such
that, for every i, zi ≥ f (yi ). Observe that the convex region given by zi ≥ f (yi ) can be approximated
by the piecewise linear function given by all integer points of f which could be possibly evaluated in the
convex integer program, as depicted in Figure 3.
Formally, our MILP reformulation consists of adding n continuous variables yi as defined at the
beginning of this section, n continuous variables zi as defined above and, for each i, O(nwmax ) new
inequalities in these continuous variables as in Figure 3. The correctness of this construction follows
from the integrality of x, the fact that the yi variables are a linear projection of x, preserving integrality,
and the zi variables are integral due to the integrality of the yi variables. Obviously, the size of this
formulation is poly(n) if and only if wmax is bounded by poly(n).

4

Conclusion and Open Problems

In Section 2 we have provided an overview encompassing a substation number of existing results in
integer programming which are particularly relevant to the field of parameterized complexity. Then, in
Section 3 we have demonstrated how to apply some of these techniques to a particular problem.
Since our overview in Section 2 is quite extensive, naturally we have not used all tools that are
available. It would be interesting to see more examples of applications of these tools. In particular,
we would like to see an instance of a problem that is solved using semidefinite programming in fixed
dimension, and an application of 2-stage stochastic IP.
Regarding specifically the Sum-Total Multicoloring problem there are two natural directions to
explore. First, could we drop the parameterization by the number of different demands? Observe that
then we cannot transform a general instance into a uniform one (without blowing up the neighborhood
diversity), and without that we lose the ordering of colors by sizes; it is not obvious how to even compute
the cost S(x) for a given point x of the essential multicoloring polytope in polynomial time. Second,
could our results be extended to the larger class of graphs of bounded modular-width? While it is possible
for Coloring by combining ILP and dynamic programming [GLO13], the non-linear objective function
of Sum Coloring makes that approach much more difficult.

11

References
[BFN+ 15]

Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon.
Elections with few candidates: Prices, weights, and covering problems. In Proc. ADT 2015,
volume 9346 of Lecture Notes Comput. Sci., pages 414–431, 2015.

[BHK+ 00]

Amotz Bar-Noy, Magnús M. Halldórsson, Guy Kortsarz, Ravit Salman, and Hadas
Shachnai. Sum multicoloring of graphs. J. Algorithms, 37(2):422–450, 2000.

[BIYZ12]

Allan Borodin, Ioana Ivan, Yuli Ye, and Bryce Zimny. On sum coloring and sum multicoloring for restricted families of graphs. Theor. Comput. Sci., 418:1–13, 2012.

[BPT12]

Grigoriy Blekherman, Pablo A. Parrilo, and Rekha R. Thomas. Semidefinite Optimization
and Convex Algebraic Geometry. SIAM, 2012.

[CCHM15]

Rajesh Hemant Chitnis, Marek Cygan, Mohammad Taghi Hajiaghayi, and Dániel Marx.
Directed subset feedback vertex set is fixed-parameter tractable. ACM Trans. Algorithms,
11(4):28:1–28:28, 2015.

[CHKM92]

William J. Cook, Mark Hartmann, Ravi Kannan, and Colin McDiarmid. On integer points
in polyhedra. Combinatorica, 12(1):27–37, 1992.

[Cou90]

Bruno Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite
graphs. Information and Computation, 85:12–75, 1990.

[Dad12]

Daniel Dadush. Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation. PhD thesis, Georgia Institute of Technology, 2012.

[DEG+ 17]

Pavel Dvořák, Eduard Eiben, Robert Ganian, Dušan Knop, and Sebastian Ordyniak. Solving integer linear programs with a small number of global variables and constraints. In
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence,
IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 607–613, 2017.

[DF13]

Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity.
Texts in Computer Science. Springer, 2013.

[DLHKW08] Jesús A De Loera, Raymond Hemmecke, Matthias Köppe, and Robert Weismantel. Fptas
for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension.
Mathematical Programming, 115(2):273–290, 2008.
[DPV11]

Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative Lattice Algorithms in
any Norm Via M-ellipsoid Coverings. In Rafail Ostrovsky, editor, FOCS, page 580–589.
IEEE, 2011.

[DV13]

Daniel Dadush and Santosh S Vempala. Near-optimal deterministic algorithms for volume computation via m-ellipsoids. Proceedings of the National Academy of Sciences,
110(48):19237–19245, 2013.

[EKS90]

Paul Erdös, Ewa Kubicka, and Allen J Schwenk. Graphs that require many colors to
achieve their chromatic sum. Congr. Numer, 71:17–28, 1990.

[FG04]

Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order
logic revisited. Ann. Pure Appl. Logic, 130(1-3):3–31, 2004.

[FLM+ 08]

Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, and Saket
Saurabh. Graph Layout Problems Parameterized by Vertex Cover. In Seok-Hee Hong,
Hiroshi Nagamochi, and Takuro Fukunaga, editors, ISAAC, volume 5369 of Lecture Notes
in Computer Science, page 294–305. Springer, 2008.

[Fre90]

Eugene C. Freuder. Complexity of K-tree structured constraint satisfaction problems. In
Proc. of the 8th National Conference on Artificial Intelligence, pages 4–9, 1990.

12

[FT87]

András Frank and Eva Tardos. An application of simultaneous diophantine approximation
in combinatorial optimization. Combinatorica, 7(1):49–65, 1987.

[Gan12]

Robert Ganian. Using Neighborhood Diversity to Solve Hard Problems.
abs/1201.3091, 2012.

[GLO13]

Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for
modular-width. CoRR, abs/1308.2858, 2013.

[GO16]

Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional
parameters for ilp. In AAAI, pages 710–716, 2016.

[GOR17]

Robert Ganian, Sebastian Ordyniak, and MS Ramanujan. Going beyond primal treewidth
for (m) ilp. In AAAI, pages 815–821, 2017.

[Har89]

Mark Evan Hartmann. Cutting Planes and the Complexity of the Integer Hull. PhD thesis,
Cornell University, Ithaca, NY, USA, 1989. AAI8915096.

[Hei05]

Sebastian Heinz. Complexity of integer quasiconvex polynomial optimization. J. Complexity, 21(4):543–556, 2005.

[HK13]

Robert Hildebrand and Matthias Köppe. A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity 2O(nlogn) . Discrete Optimization,
10(1):69–84, 2013.

[HKLW10]

Raymond Hemmecke, Matthias Köppe, Jon Lee, and Robert Weismantel. Nonlinear integer programming. In Michael Jünger, Thomas M. Liebling, Denis Naddef, George L.
Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A.
Wolsey, editors, 50 Years of Integer Programming, pages 561–618. Springer, 2010.

[HKS03]

Magnús M. Halldórsson, Guy Kortsarz, and Hadas Shachnai. Sum coloring interval and
k-claw free graphs with application to scheduling dependent jobs. Algorithmica, 37(3):187–
209, 2003.

[HOR13]

Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. n-fold integer programming
in cubic time. Math. Program, 137(1-2):325–341, 2013.

[HWZ16]

Robert Hildebrand, Robert Weismantel, and Kevin Zemmer. An fptas for minimizing indefinite quadratic forms over integers in polyhedra. In Proceedings of the Twenty-Seventh
Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1715–1723. Society for Industrial and Applied Mathematics, 2016.

[IL96]

Sandy Irani and Vitus Leung. Scheduling with conflicts, and applications to traffic signal
control. In SODA, volume 96, pages 85–94, 1996.

[JK15]

Bart M. P. Jansen and Stefan Kratsch. A structural approach to kernels for ILPs: Treewidth
and total unimodularity. CoRR, abs/1506.07729, June 25 2015. Comment: Extended
abstract in the Proceedings of the 23rd European Symposium on Algorithms (ESA 2015).

[JSO10]

Klaus Jansen and Roberto Solis-Oba. An opt+ 1 algorithm for the cutting stock problem
with constant number of object lengths. In IPCO, pages 438–449. Springer, 2010.

[Kan87]

Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper.
Res., 12(3):415–440, August 1987.

[KK16]

Dušan Knop and Martin Koutecký. Scheduling meets n-fold integer programming. Technical report, 2016. http://arxiv.org/abs/1603.02611.

[KKM17a]

Dusan Knop, Martin Koutecky, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In Kirk Pruhs and Christian Sohler, editors, 25th Annual
European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:14, Dagstuhl, Germany, 2017. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik.
13

CoRR,

[KKM17b]

Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and bribing in singleexponential time. In Heribert Vollmer and Brigitte Vallée, editors, STACS, volume 66
of LIPIcs, pages 46:1–46:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.

[Kou16]

Martin Koutecký. Graver basis optimization, May 2016.

[KP00]

Leonid Khachiyan and Lorant Porkolab. Integer Optimization on Convex Semialgebraic
Sets. Discrete & Computational Geometry, 23(2):207–224, 2000.

[KS89]

E. Kubicka and A. J. Schwenk. An introduction to chromatic sums. In Proceedings of
the 17th Conference on ACM Annual Computer Science Conference, CSC ’89, pages 39–45,
New York, NY, USA, 1989. ACM.

[Lam12]

Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica,
64(1):19–37, 2012.

[Lam14]

Michael Lampis. Model checking lower bounds for simple graphs. Logical Methods in
Computer Science, 10(1), 2014.

[Len83]

H. W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of
Operations Research, 8(4):538–548, 1983.

[LHK13]

Jesus A. De Loera, Raymond Hemmecke, and Matthias Köppe. Algebraic and Geometric
Ideas in the Theory of Discrete Optimization, volume 14 of MOS-SIAM Series on Optimization. SIAM, 2013.

[Lok09]

Daniel Lokshtanov. New Methods in Parameterized Algorithms and Complexity. PhD
thesis, University of Bergen, 2009.

[Lok15]

Daniel Lokshtanov. Parameterized integer quadratic programming: Variables and coefficients. arXiv preprint arXiv:1511.00310, 2015.

[LORW12]

Jon Lee, Shmuel Onn, Lyubov Romanchuk, and Robert Weismantel. The quadratic
graver cone, quadratic integer minimization, and extensions. Mathematical programming,
136(2):301–323, 2012.

[Mar02]

Dániel Marx. The complexity of tree multicolorings. In Mathematical Foundations of
Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland,
August 26-30, 2002, Proceedings, pages 532–542, 2002.

[Mar05]

D. Marx. A short proof of the NP-completeness of minimum sum interval coloring. Operations Research Letters, 33(4):382–384, 2005.

[MT96]

A. Mehrotra and M. A. Trick. A column generation approach for graph coloring. INFORMS
Journal on Computing, 8:344–354, 1996.

[MW15]

Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Math.
Program., 154(1-2, Ser. B):533–562, 2015.

[Nie04]

Rolf Niedermeier. Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms.
In Jirı́ Fiala, Václav Koubek, and Jan Kratochvı́l, editors, MFCS, volume 3153 of Lecture
Notes in Computer Science, page 84–103. Springer, 2004.

[NSS99]

S. Nicoloso, M. Sarrafzadeh, and X. Song. On the sum coloring problem on interval graphs.
Algorithmica, 23(2):109–126, 1999.

[Onn10]

Shmuel Onn. Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics,
European Mathematical Society, 2010.

[OWW12]

Timm Oertel, Christian Wagner, and Robert Weismantel. Convex integer minimization in
fixed dimension. CoRR, abs/1203.4175, March 19 2012. Comment: submitted.

[OWW14]

Timm Oertel, Christian Wagner, and Robert Weismantel. Integer convex minimization by
mixed integer linear optimization. Oper. Res. Lett, 42(6-7):424–428, 2014.

14

