Parameterized complexity of fair deletion problems II.∗
Dušan Knop1,3 , Tomáš Masařík1 , and Tomáš Toufar2

arXiv:1803.06878v1 [cs.CC] 19 Mar 2018

1

Department of Applied Mathematics, Charles University, Prague, Czech Republic
{knop, masarik}@kam.mff.cuni.cz
2
Computer Science Institute, Charles University, Prague, Czech Republic
toufi@iuuk.mff.cuni.cz
3
Department of Informatics, University of Bergen, Bergen, Norway

Abstract
Vertex deletion problems are those where given a graph G and a graph property π, the
goal is to find a subset of vertices W such that G \ W satisfies property π. Typically, we want
to minimize size of the deletion set W . Unlike this, in fair vertex deletion problems we change
the objective: we minimize the maximum number of vertices deleted in neighborhood of any
vertex.
When the property π is expressible by an MSO formula we refer to this special case as to
the MSO fair vertex deletion problem. We prove that there is an FPT algorithm for the
MSO fair vertex deletion problem parametrized by the twin cover number.
We study parameterized complexity of the Fair Vertex Cover (FairVC) problem. It
turns out that the FairVC problem is among the simplest problems with respect to the
property π (here π describes an edgeless graph). We prove that the FairVC problem is
W[1]-hard with parameterization by both treedepth and feedback vertex set of the input graph.
On the positive side, we provide an FPT algorithm for the FairVC problem parameterized by
modular width.

1

Introduction

We study computational complexity of fair deletion problems. Deletion problems are standard
reformulation of some classical problems in combinatorial optimization examined by Yannakakis [30].
For a graph property π we formulate a vertex deletion problem. That means, given a graph
G = (V, E), find the smallest possible set of vertices W such that G \ W satisfies property π. Many
classical problems can be formulated in this way such as Minimum Vertex Cover (here the task
is to obtain an edgeless graph) or Minimum Feedback Vertex Set (now the graph has to be
a forest).
Of course, the complexity is determined by the desired property π but most of these problems
are NP-complete [29, 1, 19].
Fair Deletion Problems. Fair deletion problems are such modifications where instead of
minimizing the size of the deleted set we change the objective in the following way (introduced
by Lin and Sahni [23]). The fair vertex deletion problem is defined as following. For a given
graph G = (V, E) and a property π, the task is to find a set W ⊆ V which minimizes the maximum
number of neighbors in the set W over all vertices where the graph G \ W satisfies the property π.
Intuitively, the solution should be spread over the input graph as evenly as possible. In order to
∗ D. Knop and T. Masařík were partly supported by the CE-ITI grant project P202/12/G061 of GA ČR. D.
Knop was partly supperted by the NFR MULTIVAL project. The research was partly supported by the project
SVV–2017–260452 of Charles University.

1

1

INTRODUCTION

2

classify (fair) vertex deletion problems we study the associated decision version. Note that this can
introduce only polynomial slowdown as the value of our objective is bounded by 0 from below and
by the number of vertices of the input graph from above.
The fair cost of a set W ⊆ V is defined as maxv∈V |N (v) ∩ W |. We refer to the function that
assigns each set W ⊆ V its fair cost as the fair objective function. Here we give a formal definition
of a problem when the property π is defined in some logic L. We emphasize here that the formula
ϕ is fixed.
Fair L Vertex Deletion
Input:
An undirected graph G = (V, E) and a positive integer k.
Fixed:
An L sentence ϕ.
Question:
Is there a set W ⊆ V such that G \ W |= ϕ with fair cost at most k?
Fair Evaluation L Vertex Deletion1
Input:
An undirected graph G = (V, E) and a positive integer k.
Fixed:
An L formula ϕ(X) with one free variable.
Question:
Is there a set W ⊆ V such that G |= ϕ(X/W ) having fair cost at most k?
Related Results. Minimizing the fair cost arises naturally in many situations, for example in
defective coloring [7]. A graph is (k, d)-colorable if every vertex can be assigned a color from the set
[k] in such a way that every vertex has at most d neighbors of the same color. This problem can
be reformulated in terms of fair deletion; we aim to find a set of edges of maximum degree d such
that after its removal the graph can be partitioned into k independent sets.
In general, extending the objective function is one of the main direction in graph model checking.
A linear optimization version of Courcelle’s theorem was given by Arnborg, Lagergren and Seese [2].
An extension to further objectives was given by Courcelle and Mosbah [5]. In this direction Masařík
and Toufar [24] studied fair objective cost and thus they provide FPT algorithms for the Fair
Evaluation MSO2 Edge Deletion problem parameterized by vertex cover and for the Fair
Evaluation MSO1 Vertex Deletion problem parameterized by neighbourhood diversity. On
the other hand they provide a W[1]-hardness result for both FO Fair Vertex Deletion and FO
Fair Edge Deletion problem parameterized by pathwidth and feedback vertex set combined.
We notice that their results holds even when parameterized by treedepth and feedback vertex set
combined. There is an XP algorithm for both the Fair Evaluation MSO2 Edge Deletion
and the Fair Evaluation MSO2 Vertex Deletion problems parameterized by treewidth by
Kolman et al. [18].
In the direction of extending the expressive power, many results have been published recently.
Szeider [27] introduced MSO with local cardinality constraints (MSO-LCC) and gave an XP algorithm
deciding it on graphs of bounded treewidth. Ganian and Obdržálek [14] study CardMSO, which is
incomparable with MSO-LCC in its expressive power. They provide an FPT algorithm on graphs
of bounded neighborhood diversity. There are also XP algorithms for extensions of MSO with
additional global and local cardinality constraints on graphs of either bounded neighborhood
diversity or bounded treewidth [17]. Those extensions enlarge before-mentioned results as well as
they cover much more than fair problems. In particular, there is an FPT algorithm parameterized
by neighborhood diversity for MSO1 logic whenever those cardinality constraints are linear.
Since classical Courcelle’s therem [6] have an exponential tower dependence on the quantifier
depth of the MSO formula, it could be interesting to find more efficient algorithm. However,
Frick and Grohe [10] proved that this dependence is unavoidable, unless P = NP. On the other
hand, there are classes where MSO model checking can be done in asymptotically faster time,
e.g. neighborhood diversity admits a single-exponential dependence on the quantifier depth of the
formula [20]. For a recent survey of algorithmic metatheorems consult the article by Grohe and
Kreutzer [15].
1 This problem is called Generalized Fair L Vertex-Deletion in [24]. However, we believe that evaluation is
more suitable expression and coincide with standard terminology in logic.

1

INTRODUCTION

3

cw
tw
fvs

sd

td

nd
vc

1.1

mw
tc

Figure 1: Hierarchy of graph parameters for the
Fair Evaluation L Vertex Deletion problem.
An arrow indicates that a graph parameter upperbounds the other. Thus, hardness results are
implied in direction of arrows and FPT algorithms
are implied in the reverse direction. Green color
indicates FPT results for MSO2 , orange are FPT
for MSO1 , blue is open, and red are hardness
results.

Our Results

We give a metatheorem for graphs having bounded twin cover. Twin cover (introduced by
Ganian [11]) is one possible generalization of vertex cover number. Here we measure the number of
vertices needed to cover all cover all edges that are not twin-edges; an edge {u, v} is a twin-edges
if N (u) \ {v} = N (v) \ {u}. Ganian introduced twin cover in hope that it should be possible to
extend algorithms designed for parameterization by vertex cover number to a broader class of
graphs.
Theorem 1. The Fair Evaluation MSO1 Vertex Deletion problem parameterized by twin
cover number admits an FPT algorithm.
Note that neighborhood diversity (studied in this context by Masařík and Toufar [24]) is
incomparable to twin cover and so are our result. For an overview of the results please refer to
Figure 1. We would like to point out here that in order to obtain this result we have to reprove
the original result of Ganian [12] for MSO1 model checking on graphs of bounded twin cover. For
this we extend arguments given by Lampis [20] in the design of an FPT algorithm MSO1 model
checking for graphs of bounded neighborhood diversity. We do this in order to obtain more insight
to the structure of the graph on which model checking is performed (its size is bounded by a
function the parameter). This is turn allows us to find a solution minimizing the fair cost and
satisfying the fixed MSO1 formula. The result by Ganian in version [11] is based on the fact that
graphs of bounded twin cover have bounded shrubdepth and so MSO1 model checking algorithm
on shrubdepth ([13]) can be used.
When proving hardness results it is convenient to show the hardness result for a concrete
problem that is expressible by an MSO1 formula, yet as simple as possible. Therefore, we introduce
a key problem for Fair Vertex Deletion – the FairVC problem.
Fair Vertex Cover (FairVC)
Input:
An undirected graph G = (V, E), and a positive integer k.
Question:
Is there a set W ⊆ V such that G \ W is an independent set and for every
vertex v of G, it holds that |N (v) ∩ W | ≤ k?
We begin description of our results with hardness result and then we move our attention to positive
results.
Theorem 2. The FairVC problem parameterized by treedepth td(G) and feedback vertex√set fvs(G)
combined is W[1]-hard. Moreover, if there exists an algorithm running in time f (w)no( w) , where
w : = td(G) + fvs(G), then Exponential Time Hypothesis fails.
This simpler problem allows us to derive hardness results with respect to the same parame1/3
terization and improves the lower bound under ETH (previously no(k ) given by Masařík and
Toufar [24]). The hardness result highly relies on the structure of sparse graphs and refutes
existence of a metatheorem for essentially every logic we can find. On the other hand we show that
FairVC can be solved efficiently in dense graph models:

2

METATHEOREM FOR FAIR EVALUATION

4

cw
tw
fvs

sd

td

mw
nd

vc

tc

Figure 2: Hierarchy of graph parameters for the
FairVC problem. An arrow indicates that a
graph parameter upper-bounds the other. Thus,
hardness results are implied in direction of arrows
and FPT algorithms are implied in the reverse
direction. Green color indicates FPT results and
red are hardness results.

Theorem 3. The FairVC problem parameterized by modular width mw(G) admits an FPT
algorithm with running time 2mw(G) mw(G)n3 , where n is the number of vertices in G.
However, this cannot be true for parameterization by shrubdepth of the input graph. This is a
consequence of Theorem 2 and [13, Proposition 3.4].
Corollary 1. The FairVC problem parameterized by shrubdepth is W[1]-hard.
We refer to Figure 2 for an overview of results for the FairVC problem.

1.2

Preliminaries

We denote the set {1, . . . , n} as [n]. We deal with simple undirected graphs, for further standard
notation we refer to monographs: graph theory [25], parameterized complexity [8].
Treedepth of a graph G (td(G)) is the minimum height of a rooted forest whose transitive
closure contains the graph G [26]. Feedback vertex set (fvs(G)) is the number of vertices of a graph
G whose removal leaves a graph without cycles. The modular-width of a graph G (mw(G)), is the
least positive integer r such that G can be obtained from such an algebraic expression of width at
most r. The width of expression A is the maximum number of operands used by any occurrence of
substitution operation A, where A is an algebraic expression that uses the following operations:
1. Create an isolated vertex.
2. The substitution operation with respect to a template graph T with vertex set [r] and
graphs G1 , . . . , Gr created by algebraic expression. The substitution operation, denoted
by T (G1 , . . . , GrS), results in
 the graph on vertex set V = V1 ∪ · · · ∪ Vr and edge set E =
E1 ∪ · · · ∪ Er ∪ {i,j}∈E(T ) {u, v} : u ∈ Vi , v ∈ Vj , where Gi = (Vi , Ei ) for all i ∈ [r].
An algebraic expression of width mw(G) can be computed in linear time [28].

2

Metatheorem for Fair Evaluation

First we show an FPT algorithm for the fair evaluation MSO1 vertex deletion problem
parameterized by the twin cover number as it is stated in Theorem 1. We give a more detailed
statement that implies the promised result straigthforwardly.
We split the proof in the two parts. First we show model checking of MSO1 algorithm
parameterized by twin cover of the graph (Proposition 2). In the second part we prove that we can
compute the fair cost of the smaller graphs (Proposition 3) and so derive the promised result.
Overview of the Algorithm. Fix an MSO1 formula ϕ. The idea behind model checking is that
this enables us to transform a graph G with bounded twin cover into a graph H with bounded size
in terms of twin cover such that G |= ϕ if and only if H |= ϕ. The crucial think is the classification
of cliques into equivalence classes in accordance with model checking which also enables us to
compute the optimal fair cost using ILP techniques.

2

METATHEOREM FOR FAIR EVALUATION

5

One of the possible proof strategies is to follow the approach of Lampis [21], that is, proving
that a fixed MSO1 formula cannot distinguish between certain graphs. The idea is to take a formula
ϕ and inductively label vertices (sets of vertices) of the graph by labels associated with quantified
variables of ϕ (and thus eliminate the quantifiers). At the end of this process we have a quantifier
free formula and a labeled graph that represents a variable assignment.
Notation. In what follows G is a graph and K is its twin cover of size k. An MSO1 formula ϕ
contains qS set quantifiers and qv element (vertex) quantifiers. Given a twin cover K we define an
exact neighbourhood of a set A ⊆ K as all common neighbors of set A denoted by N (A) such that
N (A) does not have any other neighbor in K. Formally, N (A) : ={v ∈ V \ K | N (v) ∩ K = A}.
Note that N (A) is a disjoint union of cliques.
We say that two cliques have the same type if they have the same size and the same exact
neighbourhood. We define a labeled graph, that is, a graph and a collection of labels on the vertices.
Those labels represent an assignment of a formula. We say that two cliques have the same labeled
type if all of them have the same size, the same exact neighbourhood and the same labels on
vertices.

2.1

Model checking

We give a reformulated combination of Lemma 5 and Theorem 4 by Lampis [20].
Proposition 1 ([20, Lemma 5 and Theorem 4]). Let ϕ be a fixed MSO1 formula and G graph of
neighborhood diversity d then either there is a vertex v such that G |= ϕ if and only if G \ v |= ϕ or
the size of G is bounded by
d2qS qv .
In particular, any clique C where each vertex has exactly the same neighborhood in G the
following holds. Either there is a vertex v ∈ C such that G |= ϕ if and only if G \ v |= ϕ or the size
of C is bounded by
2qS qv .
Proposition 1 bounds the size of a maximum clique in G \ K because we can apply it repeatedly
for each clique that is bigger than the threshold. Now, we need to bound the number of cliques of
each type. For this we establish the following technical lemma.
Lemma 1. Let G be a labeled graph of twin cover K with the size of maximum clique in G \ K
bounded by `, let A ⊆ K, and let ϕ be a fixed MSO1 formula with qv quantified element variables
and qS quantified set variables. If there are strictly more than
qS

α(qS , qv ) = 2` (qv + 1)
cliques of the same labeled type T then there exists a clique C of the labeled type T such that G |= ϕ
if and only if G \ C |= ϕ.
Proof. We prove the lemma by induction on qS + qv . Without loss of generality all the quantifiers
are assumed to be existential.
The base case of the induction is a quantifier free formula. If there is at least one labeled type
with at least two cliques C1 , C2 then the following holds. If G |= ϕ then G \ C1 |= ϕ clearly holds
as well since clique C2 has exactly the same neighborhood and the same labels and a quantifier
free formula can only check the neighborhood of labeled vertices. If (G \ C1 ) |= ϕ and since C1 , C2
have the same labels the same size and the same exact neighborhood so G |= ϕ.
For the induction case we consider the first quantified variable in ϕ and we split the proof
whether it is set or vertex variable. Suppose there is at least one labeled type which contains
strictly more than α(qS , qv ) cliques.
If it is a set variable then we try all possible assignments of the variable to cliques of the chosen
labeled type. There are at most 2` of possible assignments to single clique and so from cliques of

2

METATHEOREM FOR FAIR EVALUATION

6

one labeled type emerge at most 2` different labeled (sub)types of cliques. We can compute that at
least one of them has strictly more than α(qS−1 , qv ):
&
' &
'
1
α(qS , qv ) + 1
`qS −1
≥ 2
(qv + 1) + ` ≥ α(qS−1 , qv ) + 1.
2`
2
So, by the induction assumption we know that there is a clique C in the newly created labeled
(sub)type of the promised properties and so of the larger labeled type.
If it is a vertex variable then only one more different labeled type can be created and importantly
at most one single clique may contain the new label. We can compute:
qS

α(qs , qv ) + 1 − 1 ≥ 2` qv + 2`

qS

≥ α(qs , qv − 1) + 1.

The argument follows from the induction assumption by the same reasoning as in the previous
case.
From this we can derive a model checking algorithm.
Proposition 2 (Model checking on graphs of bounded twin cover). Let G be a graph with twin
cover K of size k and the size of the maximum clique in G \ K bounded by ` and ϕ is an MSO1
sentence then either there exists a clique C ∈ G \ K such that G |= ϕ if and only if G \ C |= ϕ or
the size of G is bounded by
qS
qS
k + (qv + 1)qv2 2k+2qS +(2 qv ) ,
where qS and qv denote the number of set and vertex quantifiers of ϕ, respectively.
. There are k vertices in the cover and 2k ` types of cliques and each of them (by Lemma 1) is
q
repeated at most α(qS , qv ) = 2` S (qv + 1) otherwise one clique of that type cannot be distinguished
by formula ϕ. The maximal size of the clique is ` = 2qS qv from Proposition 1 and this gives us the
desired bound.
qS

k + 2k `2 α(qS , qv ) = k + 2k `2 2` (qv + 1) = k + 2k (2qS qv )2 2(2
qS

= k + (qv + 1)qv2 2k+2qS +(2

qv )qS

qS
qv )qS

(qv + 1) =

.

The following corollary is a useful reformulation of Proposition 2 as it allows us to use one free
set variable and can be used to compute optimal fair cost.
Corollary 2. For a given graph G with twin cover of size k and fixed MSO1 formula ϕ with one
free variable there exists a graph H of bounded size such that it holds G |= ϕ if and only if H |= ϕ.
In particular, graph H has at most
α = 2(2

q +1
qS +1
qv ) S

(qv + 1)

cliques of the size bounded by
` = 2qS +1 qv .

2.2

Finding Fair Solution

A similar model checking to above was used for graphs with bounded neighborhood diversity [20].
In the following proof we follow the ideas of Masařík and Toufar [24]. They for a given formula
ϕ(X) define a so called shape of X in G. The idea behind a shape is that in order to do the model
checking we have deleted some vertices from G that cannot change the outcome of ϕ(X), however,
we have to derive a solution of minimal cost in whole graph G. Thus shape characterizes the set X
(leading to ϕ(X) being true) and we have to be able to find a set T ⊆ V (G) for which ϕ(X/T )
holds and T has the minimal fair cost.

2

METATHEOREM FOR FAIR EVALUATION

7

number of vertices outside X
1

2

3

4

5

≥6

0

1

2

3

4

5

≥6

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

2

2

2

2

2

2

2

2

3

3

3

3

3

3

3

3

4

4

4

4

4

4

4

4

5

5

5

5

5

5

5

5

≥6

?

?

?

?

?

?

6

number of vertices in X

number of vertices in X

0

number of vertices outside X

2
3
4
5
≥6

Figure 3: Example of a 6 × 6 A-shape. All
cliques of size 3 will be assigned to yellow
(light gray) fields, while cliques of size 8 will
be assigned to orange (darker gray) fields.

Figure 4: An example of uncertainty in computation of objective function. The value
in the last row depends on the size of the
clique we are assigning to those cells. The
value in the cell is how much we pay for any
compatible clique assigned to this cell.

Shape. Let G = (V, E) be a graph, ϕ(X) an MSO formula, K ⊆ V twin cover of G, A ⊆ K, and
let ` and α be set as above. Let C be the collection of all cliques in G in the exact neighborhood of
A.
We define an A-shape for each exact neighbourhood. An A-shape of size ` is a two dimensional
table SA of of dimension (` + 1) × (` + 1) indexed by [0, 1, . . . ` + 1] × [0, 1, . . . , ` + 1]. Each entry
S(i, j) ∈ [0, . . . , α + 1]. The interpretation of SA (i, j) is the following:
• if 0 ≤ i, j ≤ ` then
– SA (i, j) ≤ α means that in T exactly SA (i, j) cliques from C of size i + j have i vertices
in T and j vertices outside T ,
– SA (i, j) = α + 1 means that in T at least α cliques from C of size i + j have i vertices in
T and j vertices outside T ,
• if i = ` + 1 and 0 ≤ j ≤ ` (and similarly in the symmetric case) then
– SA (i, j) ≤ α means that in T exactly SA (i, j) cliques from C of size at least ` + 1 + j
have j vertices outside T (and the rest is in T ),
– SA (i, j) = α + 1 means that in T at least α cliques from C of size at least ` + 1 + j have
j vertices outside T (and the rest of vertices in T ), and
• (at least) SA (` + 1, ` + 1) cliques having at least 2` + 2 vertices have at least ` + 1 vertices in
T and at least ` + 1 vertices not in T .
Finally the shape of X in G is a union of A-shapes for all A ⊆ K.
A solution in the exact neighborhood of A can formally be described as a function sol : C → N×N,
where C is the collection of all cliques in the exact neighborhood of A. The solution sol is valid
if for every C ∈ C with sol(C) = (i, j) either i + j = |C| or |C| ≥ `, i = ` + 1 (or equivalently
j = ` + 1), and i + j < |C|. For illustration of a valid assignment please refer to Figure 3. We say
that a valid solution sol is compatible with the shape SA if S(i, j) = sol−1 , whenever S(i, j) < α
and sol−1 ≥ α otherwise. The A-shape SA is said to be valid if there exists a valid solution for
SA . Note that such a solution does not exists if the shape specifies too many (or too few) cliques
of certain sizes. The shape S is valid if all its A-shapes are valid.
The following lemma computes a solution of minimal cost for an A-shape. We do this by
reducing the task to integer linear programming (ILP) while using non-linear objective.

2

METATHEOREM FOR FAIR EVALUATION

8

Theorem 4 (Khachian and Porkolab [16] – simplified). Integer linear programming with objective
minimization of a quasiconvex function in dimension p is FPT with respect to p and space exponential
in L the length of encoding of the ILP instance.
Lemma 2. Let G = (V, E) be a graph, K be a twin-cover of G, and ∅ 6= A ⊆ K. There is an
algorithm that given an A-shape SA of size ` computes a valid solution for SA of minimal cost in
time f (|K|, `) · |G|O(1) or reports that SA is not valid.
Proof. Let C be the collection of all cliques in the exact neighborhood of A. We split the task
of finding a minimal solution to SA into two independent parts depending on the size of cliques
assigned in the phase.
The first phase is for cliques in C with sizes at most `. Observe that these can be assigned
deterministically in a greedy way. This is because no cell of SA is shared by two sizes and we can
see that if there are more cells with value α on the corresponding diagonal we can always prefer the
top one as this minimizes the cost (see Figure 4). However, this is not possible for larger cliques as
they may in general share some cells of SA and thus we defer them to the second phase.
Now observe that the most important vertices for computing the cost are the vertices constituting
the set A. To see this just note that all other vertices see only A and their neighborhood (a clique)
which is at least as large as for the vertices in A. It follows that we should only care about the
number of selected vertices in the (exact) neighborhood of A. Thus if the size of all cliques in C is
bounded in terms of k we are done. Alas, this is not the case.
We split the set C into sets C1 , . . . , C2` , and Cmax . A clique C ∈ C belongs to C|C| if 1 ≤ |C| ≤ 2`
and belongs to Cmax otherwise. Note that cliques from Cmax may be assigned only to cells having
at least one index ` + 1. As mentioned we are about to design an ILP with a non-linear objective
function. This ILP has variables xqi,j that express the number of cliques from the set Cq assigned
to the cell (i, j) of SA (that is 1 ≤ i, j ≤ ` + 1 and q ∈ Q = {1, . . . , 2`} ∪ {max}). The obvious
conditions are the following (the D symbol translates to = if S(i, j) < α while it translates to ≥ if
S(i, j) = α).
X q
xi,j D SA (i, j)
∀1 ≤ i, j ≤ ` + 1
q∈Q

X

xqi,j = |Cq |

∀q ∈ Q

1≤i,j≤`+1

xqi,j ≥ 0

∀1 ≤ i, j ≤ ` + 1, ∀q ∈ Q

We are about to minimize the following objective
X
X

max
max
j · xqi,j + (` + 1)xmax
`+1,`+1 + f x`+1,1 , . . . , x`+1,` ,
1≤i,j≤`+1 1≤q≤2`

where f is a function that has access to sizes of all cliques in Cmax and computes the minimum
possible assignment. We now claim that the function f is a separable convex function in variables
max
xmax
`+1,1 , . . . , x`+1,` . The claimed result then follows from Theorem 4 as the number of integral
variables is O(`2 ).



max
To see this observe that the value of f xmax
`+1,1 , . . . , x`+1,` is equal to sum of sizes of cliques
P`
“assigned to the last row” minus i=1 xmax
to their size,
`+1,i . We order cliques in Cmax according


max
that is, |C1 | ≤ |C2 | ≤ · · · ≤ |Ct |, where t denotes the size of Cmax . Now f x`+1,1 , . . . , xmax
`+1,` =
P
 P
`
`
max
max
0
f0
i=1 x`+1,i −
i=1 x`+1,i . This finishes the proof as f is a convex function.

Now we are ready to prove the main result of this section. It essentially follows by exhaustive
search among all possible shapes and application of Corollary 2 and Lemma 2.
Proposition 3. Let G = (V, E) be a graph with twin cover K of size k. For a fixed MSO1 formula
ϕ(X) with one free variable that represents the set to be deleted it is possible to find a set W ⊆ V
such that

3

THE FAIRVC PROBLEM

9

• ϕ(X/W ) is valid in G and
• cost of W is minimized among all subset of V satisfying ϕ(X)
in time f (k, |ϕ|)|V |O(1) for some computable function f .
Proof of Proposition 3. We proceed as follows. For every possible selection of K ∩ X we generate
all possible shapes and check whether ϕ(·) evaluates to true under shape S and if so, we compute
X for S having the minimal fair-cost. Finally, we return the set X minimizing the cost.
We stress that Proposition 2 applies only in cases where the exact neighborhood of the cliques
at hand is not empty. Thus, these cliques are exceptional and we have to handle them separately.
Note that in this case the objective is different – we want to minimize the maximum number of
selected vertices in any clique. It is not hard, however, to do this via standard tricks.
In order to summarize the running time we have
• at most 2k possible selections for W ∩ K and
• at most 2k · (α + 1)(`+1) possible shapes (for each such selection).
For every shape S we apply Proposition 2 to resolve whether ϕ(X) evaluates to true under S. If
ϕ(X) was evaluated to true, then using Lemma 2 on every exact neighborhood A we obtain a
set WA minimizing the cost for vertices in A and put W = ∪A⊆K WA . Observe that this union
gives optimal cost for the selected shape S. Finally we return the set W minimizing the cost for
any true evaluated shape. Clearly this routine runs in FPT time with respect to k and |ϕ| as
parameters.
2.2.1

Polynomial Space Version of Proposition 3

We now argue that it is possible to implement Lemma 2 in polynomial space via reducing it to
integer linear programming. We note that similar application of this technique is recently presented
by Bredereck et al. [3].
Theorem 5 (Lenstra & Frank, Tardós [22, 9]). There is an algorithm that given an ILP with p
variables finds an optimal solution to it using O(p2.5p poly(L)) arithmetic operations and space
polynomial in L, where L is the bitsize of the ILP.
Remark 1. Let G = (V, E) be a graph, K be a twin-cover of G, and A ⊆ K. There is an algorithm
that given an A-shape SA of size ` computes a valid solution for SA of minimal cost in time
f (|K|, `) · |G|O(1) and space polynomial in |G| or reports that SA is not valid.
max
Proof. Here the only difference is that we have to rewrite the function f (xmax
`+1,1 , . . . , x`+1,` ) it using
new variable y (representing its value) into constraints of ILP and thus obtain a linear objective.
P`
We do this by adding a variable y ≥ 0 with constraint y = j=1 xmax
`+1,j and work with univariate
function f (y) instead. We order cliques in Cmax according to their size, that is, |C1 | ≤ |C2 | ≤ · · · ≤
Pi
|Ct |, where t denotes the size of Cmax . By ci we denote the sum j=1 |Ci | and note that f (y) = cy .
Finally we introduce a variable fy representing the value of f (y) and add constraints

fy ≥ (y − i)ci

∀1 ≤ i ≤ t .

Our result then follows as t ≤ |V | and thus we add at most |V | new constraints.

3
3.1

The FairVC problem
Hardness for Treedepth and Feedback Vertec Set

We begin with several simple observations about the fair objective value k in the FairVC problem.

3

THE FAIRVC PROBLEM

10

i

n−i

E{a,b}

..
.

1
2
3
4
q
..
.

i

m

lower
a-upper

Va
guard
n−1

1
2
i
..
.

c1ab
n−i
c2ab

n

guard
m−1

n
..
.

a-lower
upper

n−j
j

Figure 5: An overview of the reduction in the proof of Theorem 2. The gray vertices are enforced to
be a part the fair vertex cover. If a vertex fair objective was lowered, then the resulting threshold
is beneath the vertex (group of vertices).
Observation 1. Let G = (V, E) be a graph and U ⊆ V be a vertex cover of G with fair objective
k, that is, ∀v ∈ V it holds that |N (v) ∩ U | ≤ k. If v ∈ V has deg(v) ≥ k, then v ∈ U .
Note that we can use Observation 1 to enforce a vertex v to be a part of the fair vertex cover
by attaching k + 1 degree 1 vertices to v. Observe further that we may adjust (lower) the global
budget k for individual vertex v by attaching vertices to v and then attaching k new leaves to the
newly added vertices. To this end if the above operations are applied to a graph G resulting in a
graph G0 , then td(G0 ) ≤ td(G) + 2 and fvs(G0 ) = fvs(G).
We observe substantial connection between FairVC and Target Set Selection (TSS)
problems. As a result, our reduction given here is, in certain sense, dual to the one given by Chopin
et al. [4] for the TSS problem. The archetypal W[1]-hard problem is the `-Multicolored Clique
problem [8]:
`-Multicolored Clique
Parameter: `
Input:
`-partite graph G = (V1 ∪ · · · ∪ V` , E), where Vc is an independent set for
every c ∈ [`] and they are pairwise disjoint.
Question:
Is there a clique of the size ` in G?
Proof of Theorem 2. Let G = (V1 ∪ · · · ∪ V` , E) be an instance of the `-Multicolored Clique
problem and let n = |Vi | for all i ∈ [`]. We denote by E{a,b} the set of edges between Va and Vb and
by m = |E{a,b} |. We will describe graph H = (W, F ) that together with k = max(m − 1, 2n) will
form an equivalent instance of the FairVC problem. The reduction has the following properties:
• |W | = poly(n, k) and |F | = poly(m, k),
• k = O(`2 ), td(H) = O(`2 ), and fvs(H) = O(`2 ).
For an overview of the reduction please refer to Figure 5. There are three types of gadgets in our
reduction, namely the vertex selection gadget, the edge selection gadget, and the incidence check
gadget. We start by enumerating the vertices in each color class by numbers from [n] and edges by
numbers in [m]. Throughout the proof a, b are distinct numbers from [`].
The Va selection gadget consists of n choice vertices (representing the color class Va ), a special
vertex called guard, and a group of n2 enumeration vertices. The guard vertex is connected to all

3

THE FAIRVC PROBLEM

11

choice vertices, it is enforced to be a part of the fair vertex cover, and its budget is lowered so that
at most n − 1 choice vertices can be in any fair vertex cover. The i-th choice vertex is connected to
n enumeration vertices. For each choice vertex there are n such vertices and so these are private
for vertex i. We further divide these vertices into two parts – the lower part consists of i vertices
and the upper part consists of n − i vertices.
The E{a,b} selection gadget consists of m choice vertices, a special vertex called guard, and a
group of 2nm enumeration vertices and is constructed analogously to the vertex selection gadget. If
the q-th edge of E{a,b} connects i-th vertex in Va and j-th vertex in Vb , then 2n numeration vertices.
These are split into four groups – lower a-part consisting of i vertices, upper a-part consisting of
n − i vertices, and similarly lower and upper b-parts.
The ab-incidence check gadget consist of two vertices c1ab and c2ab . Both c1ab and c2ab are enforced
to be a part of the solution and with lowered budget in a way that at most n vertices in the
neighborhood of each of them can be part of any fair vertex cover. The vertex c1ab is connected
to every lower part vertex in the selection gadget for Va and to every upper a-part vertex in the
selection gadget for E{a,b} . The vertex c2ab is connected to every upper part vertex in the selection
gadget for Va and to every lower a-part vertex in the selection gadget for E{a,b} .
This finishes the construction of H. Now observe that if we remove vertices c1ab , c2ab from H,
then each component of the resulting graph is a tree (rooted in its guard vertex) of depth at most
3. It follows that td(H) = O(`2 ) and fvs(G) = O(`2 ), as so is the size of the removed set of vertices.
We finish the proof by showing that the two instances are equivalent.
Suppose (G, `) is a yes-instance which is witnessed by a set K ⊆ V1 × · · · × V` . We now construct
a vertex cover CK of H having |N (w) ∩ CK | ≤ k for all w ∈ W . The set CK contains the following:
• all enforced vertices (including all guard and check vertices),
• if v ∈ Va ∩ K is the i-th vertex of Va , then all selection vertices of Va but the vertex i are in
CK and lower and upper enumeration vertices of i are in CK ,
• if v ∈ Va ∩ K and u ∈ Vb ∩ K are adjacent through q-th edge of E{a,b} , then all selection
vertices of E{a,b} but the vertex q are in CK and q’s enumeration vertices are in CK .
For the other direction we prove that a vertex cover C in H fulfils |N (w) ∩ C| ≤ k for all
w ∈ W if it corresponds to a clique in G. For the other direction suppose that there is a vertex
cover C in H such that |N (w) ∩ C| ≤ k for all w ∈ W . Recall that C has to contain all enforced
vertices. This implies that at least 1 choice vertex for Va is not in U ; we will show that exactly 1
such choice vertex is in U . The same holds for the edge choice vertices. To see this suppose for
contradiction that 2 choice vertices for Va (vertex i and j) are not in U . Because U is a vertex cover
of H it follows that their enumeration vertices must belong to U . But now take vertices c1ab , c2ab .
In their neighborhood U have at least 3n vertices (2n from the Va ’s numeration part and n from
the a-numeration part of E{a,b} ). This is absurd as these vertices (due to the lowered budget) can
have at most 2n vertices in their neighborhood and thus at least one of them exceeds its budget.
Thus the selection gadgets actually encode some selection of vertices va and edges ea,b . To finish
the proof we have to observe that both c1ab and c2ab have at most (in fact, exactly) n neighbors in
U if and only if the vertex va is incident to the edge ea,b . If this holds for all possible combinations
of a, b, then we have selected a clique in the graph G.

3.2

FPT algorithm for Modular Width

Since the algebraic expression A of width mw(G) can be computed in linear time [28], we can
assume that we have A on the input. We construct the rooted ordered tree T corresponding to A.
Each node t ∈ T is assigned a graph Gt ⊆ G that is the graph constructed by the subexpression of
A rooted at t. That is, Suppose we are performing substitution operation at node t with respect to
template graph T and graphs G1 , . . . , Gr . Denote the resulting graph Gt and denote by ni the size
of V (Gi ).

3

THE FAIRVC PROBLEM

12

. The edges in Gt between two vertices of Gi will be referred to as old edges, the edges between Gi
and Gj for i 6= j (i.e., edges introduced by the template operation) will be referred to as new edges.
The computation will be carried out recursively from the bottom of the tree T .
We first describe the structure of all vertex covers C in Gt . First observe that if ij ∈ E(T )
then at least one of V (Gi ), V (Gj ) must be a subset of C; otherwise there would be a new edge
not covered by C. From this we can see that the set CT = {i : V (Gi ) ⊆ C} is a vertex cover of
the template graph T . We call the CT the type of the vertex cover C. Furthermore, every set
C ∩ V (Gi ) must be a vertex cover of Gi (otherwise there would be an old edge uncovered by C).
We now describe the fair cost of the cover C in terms of fair costs and sizes of the sets C ∩ V (Gi ).
Denote by ci the size |C ∩ V (Gi )| and by fi the fair cost of C ∩ V (Gi ) in Gi . The fair cost of C in
W ⊆ V (G)
P is defined as maxv∈W |C ∩ N (v)|. For i ∈ [r] the fair cost of C in V (Gi ) can be written
as fi + j:ij∈E(T ) cj . Clearly, fair cost of C is the maximum of the last expression over i ∈ [r].
If we know the type CT of the cover C this can be simplified based on whether i lies in CT .
If i ∈ CT then fi is ∆(Gi ) (the maximal degree of Gi ). If on the other hand i ∈
/ CT then all its
neighbors j are in CT and in this case cj = nj . Combining those observations, we have
(
P
P
i ∈ CT ,
∆(Gi ) + j ∈C
/ T :ij∈E(T ) cj +
j∈CT :ij∈E(T ) nj
fair cost of C in Gi =
P
fi + j:ij∈E(T ) nj
i∈
/ CT .
For each node t of the tree T we keep an |V (Gt )| table Tabt of integer values from [n] ∪ ∞.
The value at position Tabt [p] is the least size of a cover in Gt of fair cost p or ∞ if such cover do
not exists.
The computation of Tab in leaves of T is trivial. We describe how to compute value Tabt [p]
given that we know Tabi in all children of t. It is enough to determine whether there exists a vertex
cover C of Gt of fixed type; we can simply iterate over all types as there are at most 2r of them.
Fix a type CT . The cover C of type CT and fair cost at most p and Tabt [p] 6= ∞ exists if and
only if for every i ∈
/ CT there is a vertex cover Ci of Gi of fair cost pi such that Tabi [pi ] 6= ∞.
Moreover, we require that the values pi satisfy the following inequalities:
X
X
p ≥ ∆(Gi ) +
Tabj [pi ] +
nj
∀i ∈ CT ,
(1)
j ∈C
/ T :ij∈E(T )

p ≥ pi +

X

j∈CT :ij∈E(T )

∀i ∈
/ CT ,

nj

(2)

j:ij∈E(T )

Tabt [p] ≥

X
j ∈C
/ T

Tabj [pi ] +

X

nj .

(3)

j∈CT

First, for every iP
∈
/ CT we set pi to the highest possible value without violating the inequality (2),
that is pi := p − j:ij∈E(T ) nj . Note that this is always a safe choice; pi does not appear anywhere
else in the constraints and choosing the highest possible value give us greatest freedom due to the
monotonicity of the table. Clearly, if any such pi is negative we know that given constraints cannot
be satisfied and there is no vertex cover C of given type and fair cost.
If for any i Tabi [pi ] = ∞, then there is no vertex cover Ci in Gi of fair cost pi . This means
that we cannot find cover C of given type and fair cost so we set Tabi [p1 ] = ∞. We check whether
inequalities (1) holds. If not, set Tabi [p1 ] = ∞. Otherwise we set Tabt [p] be equal to the expression
in (3) on theSright side. We S
claim that there is a vertex cover C of given type and fair cost; we
can set C = i∈CT V (Gi ) ∪ i∈C
/ T Ci , where Ci is any vertex cover of Gi of fair cost pi and size
Tabi [pi ] (this is guaranteed to exist because Tabi [pi ] was not ∞. It is straightforward to check that
C has required properties. Moreover, from our choice of values pi it follows that a vertex cover of
type CT , fair cost p and size Tabt [p] exists if and only if the described procedure finds values of pi .
By iterating over all types CT we can fill the value Tab[p] as required.
To complete the description of the algorithm, it is enough to look whether there is not ∞ value
in Tabroot [k], where k was the desired fair cost.
The running time is n for the induction over expression A times 2r different type of covers
in any single node times filling the table of size at most n times nr for determining the correct

4

CONCLUSIONS

13

values pi and checking other inequalities for every i ∈ [r]. This altogether yields a 2r rn3 time
algorithm.

4

Conclusions

One can define edge deletion problems in a similar way as vertex deletion problems. Recall that in
dense graph classes one cannot obtain an MSO2 model checking algorithm running in FPT-time.
Fair MSO1 edge deletion
Input:
An undirected graph G = (V, E), an MSO1 sentence ϕ, and a positive
integer k.
Question:
Is there a set F ⊆ E such that G \ F |= ϕ and for every vertex v of G, it
holds that |{e ∈ F : e 3 v}| ≤ k?
The crucial open problem is to resolve parameterized complexity of the fair MSO1 edge
deletion problems for parameterization by neighborhood diversity and twin cover. There is a
big difference between vertex and edge deletion problems – in our hardness reduction we used a
deletion to an edgeless graph but a fair edge cost in this case equals to the maximum degree of the
former graph (an thus is computable in polynomial time). So the first step should be to find a
non-trivial edge deletion problem.
Another open problem is to resolve parameterized complexity of the Fair Evaluation MSO1
Vertex Deletion problems with respect to graph parameters generalizing neighborhood diversity
or twin cover (e.g. modular width or cluster vertex deletion number). Finally, we would like to
ask whether there is an NP-hard fair vertex deletion problem that admits an FPT algorithm for
parameterization by treedepth (and feedback vertex set) of the input graph.
Cluster Vertex Deletion Number. A parameter closely related to twin cover is the cluster
vertex deletion number, that is the least number of vertices one has to delete from a graph in order
to get a collection of (disjoint) cliques. It seems that a more careful analysis of the model-checking
algorithm may yield (again) sufficient insight into the structure of the fair solution and thus lead
to an FPT algorithm for this wider class of graphs. Though, it remains open whether this is
possible and there is an FPT algorithm for Fair Evaluation MSO Vertex Deletion for this
parameterization or not.
MSO with Local Linear Constraints. Previously, an FPT algorithm for evaluation of a fair
objective was given for parameter neighborhood diversity [24]. That algorithm was extended [17]
to a so called local linear constraints again for a fixed formula ϕ(·) with one free variable that is
defined as follows. Every vertex v ∈ V (G) is accompanied with two positive integers `(v), u(v),
the lower and the upper bound, and the task is to find a set X that not only G |= ϕ(X) but for
each v ∈ V (G) it holds that `(v) ≤ |N (v) ∩ X| ≤ u(v). Note that this is a generalization as fair
objective of value t can be tested in this framework by setting `(v) = 0 and u(v) = t for every
v ∈ V (G). Is this extension possible for parameterization by the twin cover number?
To support this question we note that in the proof of Lemma 2 the minimal size of the
neighborhood of B for a shape in exact neighborhood of B is computed. It is not hard to see that
by a similar argument we can compute the maximal size of the neighborhood of B for a shape in
exact neighborhood of B. Furthermore, lower and upper bounds for vertices in a clique can be
assumed to be nearly the same – each differ by at most 1 [17]. Thus, Lemma 2 gives only that if at
least one of the computed bounds for a vertex v in the twin cover is within `(v) and u(v), then
there is a solution with desired properties. However, if on the other hand it happens that both
`(v), u(v) are in between the computed values, we do not know whether or not any of the desired
values is attainable. To see that not all values in the thus computed range are attainable one can
construct a formula that for twin cliques up to a certain size checks that the number of selected

REFERENCES

14

vertices is even. Then, if the input graph contains only cliques up to this size no twin cover vertex
has odd number of neighbors in the set X (provided the cover vertices form an independent set).

References
[1] Tadashi Ae, Akira Nakamura, and Toshimasa Watanabe. On the NP-hardness of edgedeletion and -contraction problems. Discrete Applied Mathematics, 6(1):63–78, 1983. doi:
10.1016/0166-218X(83)90101-4.
[2] Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs.
Journal of Algorithms, 12(2):308–340, June 1991. doi:10.1016/0196-6774(91)90006-k.
[3] Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon.
Mixed integer programming with convex/concave constraints: Fixed-parameter tractability
and applications to multicovering and voting. arXiv preprint, 2017. arXiv:1709.02850.
[4] Morgan Chopin, André Nichterlein, Rolf Niedermeier, and Mathias Weller. Constant thresholds
can make target set selection tractable. Theory Comput. Syst., 55(1):61–83, 2014. doi:
10.1007/s00224-013-9499-3.
[5] B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs.
Theor. Comput. Sci., 109(1&2):49–82, 1993. doi:10.1016/0304-3975(93)90064-z.
[6] Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs.
Inf. Comput., 85(1):12–75, March 1990. doi:10.1016/0890-5401(90)90043-h.
[7] Lenore J. Cowen, Robert Cowen, and Douglas R. Woodall. Defective colorings of graphs in
surfaces: Partitions into subgraphs of bounded valency. Journal of Graph Theory, 10(2):187–
195, 1986. doi:10.1002/jgt.3190100207.
[8] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin
Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
doi:10.1007/978-3-319-21275-3.
[9] András Frank and Eva Tardos. An application of simultaneous diophantine approximation in
combinatorial optimization. Combinatorica, 7(1):49–65, 1987. doi:10.1007/BF02579200.
[10] 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. doi:10.1016/j.apal.2004.01.007.
[11] Robert Ganian. Twin-cover: Beyond vertex cover in parameterized algorithmics. In International Symposium on Parameterized and Exact Computation, pages 259–271. Springer, 2011.
doi:10.1007/978-3-642-28050-4_21.
[12] Robert Ganian. Twin-cover: Beyond vertex cover in parameterized algorithmics. In Dániel
Marx and Peter Rossmanith, editors, Parameterized and Exact Computation - 6th International
Symposium IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers,
volume 7112 of Lecture Notes in Computer Science, pages 259–271. Springer, 2011. doi:
10.1007/978-3-642-28050-4_21.
[13] Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, Patrice Ossona de Mendez,
and Reshma Ramadurai. When trees grow low: Shrubs and fast MSO1. In Branislav Rovan,
Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer
Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31,
2012. Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 419–430. Springer,
2012. doi:10.1007/978-3-642-32589-2_38.

REFERENCES

15

[14] Robert Ganian and Jan Obdržálek. Expanding the expressive power of monadic secondorder logic on restricted graph classes. In Thierry Lecroq and Laurent Mouchard, editors,
IWOCA, volume 8288 of Lecture Notes in Computer Science, pages 164–177. Springer, 2013.
doi:10.1007/978-3-642-45278-9_15.
[15] Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. pages 181–205,
2011. doi:10.1090/conm/558/11051.
[16] Leonid Khachiyan and Lorant Porkolab. Integer Optimization on Convex Semialgebraic Sets.
Discrete & Computational Geometry, 23(2):207–224, 2000. doi:10.1007/pl00009496.
[17] Dušan Knop, Martin Koutecký, Tomáš Masařík, and Tomáš Toufar. Simplified algorithmic
metatheorems beyond MSO: Treewidth and neighborhood diversity. In Hans L. Bodlaender
and Gerhard J. Woeginger, editors, Graph-Theoretic Concepts in Computer Science: 43rd
International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised
Selected Papers, pages 344–357, Cham, 2017. Springer International Publishing. doi:10.1007/
978-3-319-68705-6_26.
[18] Petr Kolman, Bernard Lidický, and Jean-Sébastien Sereni. Fair edge deletion problems on
treedecomposable graphs and improper colorings, 2010. URL: http://orion.math.iastate.
edu/lidicky/pub/kls10.pdf.
[19] Mukkai S. Krishnamoorthy and Narsingh Deo. Node-deletion np-complete problems. SIAM
Journal on Computing, 8(4):619–625, 1979. doi:10.1137/0208049.
[20] Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica,
64(1):19–37, 2012. doi:10.1007/s00453-011-9554-x.
[21] Michael Lampis. Model checking lower bounds for simple graphs. Logical Methods in Computer
Science, 10(1), 2014. doi:10.2168/LMCS-10(1:18)2014.
[22] H. W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of
Operations Research, 8(4):538–548, 1983. doi:10.1287/moor.8.4.538.
[23] Li-Shin Lin and Sartaj Sahni. Fair edge deletion problems. IEEE Trans. Comput., 38(5):756–
761, 1989. doi:10.1109/12.24280.
[24] Tomáš Masařík and Tomáš Toufar. Parameterized complexity of fair deletion problems.
In Theory and Applications of Models of Computation - 14th Annual Conference, TAMC
2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pages 628–642, 2017. doi:10.1007/
978-3-319-55911-7_45.
[25] Jiří Matoušek and Jaroslav Nešetřil. Invitation to Discrete Mathematics (2. ed.). Oxford
University Press, 2009.
[26] Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms,
volume 28. Springer Science & Business Media, 2012. doi:10.1007/978-3-642-27875-4.
[27] Stefan Szeider. Monadic second order logic on graphs with local cardinality constraints. ACM
Trans. Comput. Log, 12(2):1–21, 2011. doi:10.1145/1877714.1877718.
[28] Marc Tedder, Dereck G. Corneil, Michel Habib, and Christophe Paul. Simpler linear-time
modular decomposition via recursive factorizing permutations. In ICALP 2008, pages 634–645,
2008. doi:10.1007/978-3-540-70575-8_52.
[29] Mihalis Yannakakis. Node- and edge-deletion NP-complete problems. In Proceedings of the
10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California,
USA, pages 253–264, 1978. doi:10.1145/800133.804355.
[30] Mihalis Yannakakis. Edge-deletion problems. SIAM J. Comput., 10(2):297–309, 1981. doi:
10.1137/0210021.

