lemma[theorem]Lemma claim[theorem]Claim Kyushu University, Fukuoka, Japan
hanaka@inf.kyushu-u.ac.jphttps://orcid.org/0000-0001-6943-856XPartially
supported by JSPS KAKENHI Grant Numbers JP21H05852, JP21K17707, JP22H00513,
JP23H04388.University of Leeds, Leeds,
UKscsnk@leeds.ac.ukhttps://orcid.org/0000-0002-1023-6530Partially supported by
ANR project ANR-18-CE40-0025-01 (ASSK). Université Paris-Dauphine, PSL
University, CNRS UMR7243, LAMSADE, Paris,
Francemichail.lampis@lamsade.dauphine.frhttps://orcid.org/0000-0002-5791-0887Supported
by ANR project ANR-21-CE48-0022 (S-EX-AP-PE-AL). Jane Open Access and Joan R.
Public [500]Mathematics of computing$\rightarrow$Graph algorithms [500]Theory
of Computation $\rightarrow$ Design and Analysis of Algorithms $\rightarrow$
Parameterized Complexity and Exact Algorithms John Q. Open and Joan R. Access
2 42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016
December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Core Stability in Additively Separable Hedonic Games of Low Treewidth

Tesshu Hanaka  Noleen Köhler  Michael Lampis

###### Abstract

Additively Separable Hedonic Game (ASHG) are coalition-formation games where
we are given a graph whose vertices represent $n$ selfish agents and the
weight of each edge $uv$ denotes how much agent $u$ gains (or loses) when she
is placed in the same coalition as agent $v$. We revisit the computational
complexity of the well-known notion of core stability of ASHGs, where the goal
is to construct a partition of the agents into coalitions such that no group
of agents would prefer to diverge from the given partition and form a new
(blocking) coalition. Since both finding a core stable partition and verifying
that a given partition is core stable are intractable problems
($\Sigma_{2}^{p}$-complete and coNP-complete respectively) we study their
complexity from the point of view of structural parameterized complexity,
using standard graph-theoretic parameters, such as treewidth.

We begin by presenting several results on Core Stability Verification (CSV)
indicating that this is an unusually intractable problem, even in very
restricted cases: CSV remains coNP-complete on graphs of vertex cover 2; CSV
is coW[1]-hard parameterized by vertex integrity when edge weights are
polynomially bounded; and CSV is coW[1]-hard parameterized by tree-depth even
if all weights are from $\\{-1,1\\}$. We complement these results with
essentially matching algorithms and one of the rare tractability results we
present is that CSV is FPT parameterized by the treewidth ${\mathtt{tw}}$ plus
the maximum degree $\Delta$ (improving a previous algorithm’s dependence from
$2^{O({\mathtt{tw}}\Delta^{2})}$ to $2^{O({\mathtt{tw}}\Delta)}$).

We then move on to study Core Stability (CS), which one would naturally expect
to be even harder than CSV. We confirm this intuition by showing that CS is
$\Sigma_{2}^{p}$-complete even on graphs of bounded vertex cover. On the
positive side, we consider the parameterization by ${\mathtt{tw}}+\Delta$ and
improve the known algorithm (which was based on Courcelle’s theorem) via an
explicit algorithm utilizing a reduction to $\exists\forall$-SAT. The running
time of our algorithm is, unfortunately, double-exponential in
${\mathtt{tw}}+\Delta$. However, we show that this is likely to be optimal, as
the existence of an algorithm with less than double-exponential dependence on
${\mathtt{tw}}$ (even for bounded-degree instances) would contradict the
Exponential Time Hypothesis (ETH).

Finally, we consider another natural parameter for these problems: the size
$k$ of the considered blocking (diverging) coalitions. Fixing $k$ to be
constant does lower the complexities of CSV and CS to P and NP-complete
respectively, since one can then consider all coalitions of size $k$ in
polynomial time. Unfortunately, we show that a more efficient algorithm is
unlikely to exist, as CSV is coW[1]-hard parameterized by $k$ (even on
unweighted graphs), while CS is NP-complete for all $k\geq 3$ (even on graphs
of bounded degree with bounded edge weights).

###### keywords:

Hedonic games, Treewidth, Core stability

###### category:

##  1 Introduction

_Coalition formation games_ model situations where a group of selfish agents
need to be partitioned into teams (coalitions) in such a way that takes into
account their preferences. Because such games capture a vast array of
interesting scenarios, they have been a subject of intense study in
computational social choice and the social sciences at large. One particularly
interesting and natural special case of such games is when the preferences of
each agent only depend on the other agents that she is placed together with in
the same coalition (and not on the placement of agents on other coalitions).
Such games are referred to in the literature as _hedonic games_ and have also
attracted much interest from the computer science perspective ([AloisioFV20,
AzizBBHOP19, BarrotOSY19, BarrotY19, BoehmerE20, 0001BW21, BullingerK21,
FanelliMM21, IgarashiOSY19, OhtaBISY17, SliwinskiZ17]), thanks in part to
their numerous applications in, for example, social network analysis
[Olsen09], scheduling group activities [DarmannEKLSW18], and allocating tasks
to wireless agents [SaadHBDH11]. For more information we refer the reader to
[Cechlarova16] and the relevant chapters of standard computational social
choice texbooks [AzizS16].

Hedonic games are extremely general. Unforunately, this generality renders
them hard to study from the computer science perspective – indeed, even
listing the preferences of all $n$ agents takes space exponential in $n$ as
the naïve approach would give the ordering of each agent over all coalitions.
This motivates the study of natural restrictions of hedonic games. In this
paper we focus on one of the most natural such restrictions: _Additively
Separable Hedonic Games_ (ASHGs), where the input is an edge-weighted graph,
vertices represent the agents, and the weight of the edge $uv$ denotes the
utility that agent $u$ derives from being in the same coalition as $v$. The
utility of an agent $u$ in a coalition $C$ can then be succinctly encoded as
the sum of the weights of edges incident on $u$ with their other endpoint in
$C$.

In any situation where agents behave selfishly, it becomes critical to look
for _stable_ outcomes, that is, outcomes which the agents are likely to
accept, based on their preferences. In the context of ASHGs, the question then
becomes: given an edge-weighted graph $G$ representing the agents’
preferences, can we find a stable partition of the agents into coalitions
(possibly also optimizing some other social welfare goal)? The computational
complexity of such questions has been amply studied ([AzizBS13, Ballester04,
ElkindFF20, FlamminiKMZ21, HanakaKMO19, Olsen09, OlsenBT12, SungD10]) and
several natural notions of stability have been proposed. In this paper we
revisit the computational complexity of one of the most well-studied such
notions, which is called _core stability_. Intuitively, a partition of $n$
agents is called _core stable_ , if it is stable enough to dissuade not only
individual diverging behavior but even divergence by groups of agents. More
formally, given a partition ${\mathcal{P}}$ of the agents, a _blocking
coalition_ is a set of agents $X$ such that all $v\in X$ have strictly higher
utility in $X$ than in the initial partition ${\mathcal{P}}$. Hence, if a
blocking coalition $X$ exists, the initial partition is _unstable_ , because
the agents of $X$ would prefer to form a new coalition. A partition is then
called core stable if no blocking coalition (of any size) exists. Notice that
core stability is a very strong (and hence very desirable) notion of
stability, compared with simpler notions, such as Nash stability (which only
precludes divergence by a single agent).

Attractive though it may be from the game theory point of view, the notion of
core stability presents some serious drawbacks from the point of view of
computational complexity. In particular, deciding if an ASHG admits a core
stable outcome is not just NP-hard, but in fact $\Sigma_{2}^{p}$-complete,
that is, complete for the second level of the polynomial hierarchy
[Woeginger13], even if the input graph is undirected, has bounded degree, and
edge weights are bounded by a constant [Peters17]. Compared to simpler notions
of stability, such as Nash stability (which is “only” NP-complete
[GairingS19]), core stability is therefore highly intractable, and this
strongly motivates the search for a better understanding of what the source of
this intractability is and for ways to deal with it. The focus of this paper
is on using notions of graph structure from parameterized complexity to
achieve a more fine-grained understanding of the complexity of this problem.
Throughout the paper we will concentrate on the case where agent preferences
are _symmetric_ , that is, the given graphs are undirected. Since most of our
results are negative, this (natural) restriction only renders them stronger.

##### Our results

In this paper we present several results that improve and clarify the state of
the art on the complexity of finding core stable outcomes in ASHGs. We study
two closely related problems: Core Stability (CS) and Core Stability
Verification (CSV), which correspond to deciding if a core stable partition
exists and deciding if a given partition is indeed core stable respectively.
Intuitively, the reason CS is complete for the second level of the polynomial
hierarchy (and not just NP-complete) is that CSV is also known to be
intractable (coNP-complete [chen2023hedonic, SungD07]). Our high-level aim is
to understand which parts of the combinatorial structure of the input are
responsible for the complexity of these two problems. In order to quantify the
input structure we will use standard structural tools from the toolbox of
parameterized complexity, such as the notions of treewidth and related
parameters111Throughout the paper we assume the reader is familiar with the
basics of parameterized complexity, as given for example in [CyganFKLMPPS15].

We begin our investigation with CSV and ask the question which restrictions on
the input are likely to render the problem tractable (or conversely, what are
the sources of the problem’s intractability). We identify two possible
culprits: the problem could become easy if we either impose restrictions on
the graph structure, for example by requiring that the input be of low
treewidth or degree, or if we impose restrictions on the allowed edge weights.
Our results indicate that these two sources of intractability interact in non-
trivial ways:

  * •

If we place absolutely no restrictions on the allowed weights, CSV remains
hard even on severely restricted instances, that is, graphs of vertex cover
$2$ (Theorem 3.1). We find this rather surprising, as this class of graphs
(which are essentially stars with one additional vertex) is rarely general
enough to render problems intractable.

  * •

One may be tempted to interpret the previous result as an artifact of the
exponentially large weights we allow in the input. However, we show that even
if we place the restriction that weights are polynomially bounded in the input
size, CSV still remains quite hard from the parameterized perspective, and
more precisely coW[1]-hard parameterized by vertex integrity (Theorem 3.3).
Recall that graphs with small vertex integrity are graphs where there exists a
small separator whose removal breaks down the graph into components of bounded
size, so this parameterization is again rather restrictive and usually easily
renders most problems almost as tractable as parameterizing by vertex cover
[GimaHKKO22, LampisM21].

  * •

Finally, we show that even if we insist on weights only being selected from
the set $\\{-1,1\\}$, CSV is coW[1]-hard parameterized by tree-depth (Theorem
3.5).

Taken together these results show that CSV is an unusually intractable problem
where hardness comes from a combination of two factors: the complexity of
dealing with the edge weights and the complexity of dealing with the graph-
theoretic structure of the input. We complement the above with several
algorithms that paint a clearer picture of the complexity of CSV showing that:
(i) CSV is polynomial-time solvable on trees (Theorem 3.7), hence Theorem 3.1
cannot be extended to graphs of vertex cover $1$ (ii) CSV is FPT parameterized
by vertex integrity plus the maximum edge weight (Theorem 3.11), so the
hardness result of Theorem 3.5 cannot be extended to vertex integrity (iii)
Theorem 3.5 is matched by an XP algorithm parameterized by treewidth with
parameter dependence $(\Delta w_{\max})^{O({\mathtt{tw}})}$, that is, an XP
algorithm when weights are polynomially bounded (Theorem 3.13) (iv) the former
algorithm can be improved to an FPT running time (even for unbounded weights)
if we parameterize by ${\mathtt{tw}}+\Delta$ (this was already observed by
Peters [Peters16a], who gave an algorithm with dependence
$2^{O(\Delta^{2}{\mathtt{tw}})}$, but we improve this complexity to
$2^{O(\Delta{\mathtt{tw}})}$ in Theorem 3.15).

The results above paint a comprehensive and rather negative picture on the
complexity of CSV, which seems to imply that our main problem, that is,
_finding_ core-stable partitions, is likely to be even more intractable. We
confirm this intuition by showing that CS remains $\Sigma_{2}^{p}$-complete
even on graphs of bounded vertex cover (Theorem 4.4). One encouraging piece of
news, however, is that we did manage to obtain an FPT algorithm when CSV is
parameterized by ${\mathtt{tw}}+\Delta$, so this seems like a case worth
considering for CS. Indeed, Peters [Peters16a] already showed that CS is FPT
for this parameterization, without, however, giving an explicit algorithm (his
argument was based on Courcelle’s theorem). We improve upon this by giving an
explicit algorithm whose dependence is _double-exponential_ on
${\mathtt{tw}}+\Delta$, using the technique of reducing to
$\exists\forall$-SAT advocated in [LampisMM18] (Theorem 4.6). Despite fixed-
parameter tractability, it is fair to say that the running time of our
algorithm is quite disappointing. Our main contribution in this part is to
show that this is, unfortunately, likely to be optimal: even for instances of
bounded degree, the existence of an algorithm with better than double-
exponential dependence on treewidth would violate the ETH (Theorem 4.14). This
shows another aspect where core-stability is significantly harder than Nash
stability, which has “just” slightly super-exponential in
${\mathtt{tw}}+\Delta$ [HanakaL22]. Note that the phenomenon that problems
complete for the second level of the polynomial hierarchy tend to have double-
exponential complexity in treewidth has been observed before [abs-2307-08149,
LampisM17, MarxM16]

Finally, we conclude our paper by considering one last relevant parameter: the
size of the allowed blocking coalition. We say that a partition is $k$-core
stable if no blocking coalition of size at most $k$ exists. The concept of
$k$-core stability was first proposed in [FanelliMM21]. For small values of
$k$ this is a natural variation of the problem, which could potentially render
it more tractable – indeed, for $k$ fixed, CSV is trivially in P and CS is
trivially in NP. Unfortunately, we show that not much more is gained from
these parameterizations: CSV is coW[1]-hard parameterized by $k$ (even on
unweighted graphs); while $k$-CS is NP-complete for all fixed $k\geq 3$, even
on graphs of bounded maximum degree and with bounded weights.

##  2 Preliminaries

Throughout the paper we use standard graph-theoretic notation and focus on
undirected graphs. An Additively Separable Hedonic Game (ASHG) is represented
by a graph $G=(V,E)$, where vertices of $V$ represent the agents, and a weight
function $w:E\to\mathbb{Z}$. A partition ${\mathcal{P}}$ of $V$ is a
collection of disjoint subsets of $V$ whose union includes all of $V$. We will
call the sets of such a partition _coalitions_. Slightly abusing notation, we
will write, for $u\in V$, ${\mathcal{P}}(u)$ to denote the set of
${\mathcal{P}}$ that contains $u$. The utility of an agent $u\in X$ in a set
$X\subseteq V$ is defined as ${\tt ut}(X,u)=\sum_{v\in X}w(uv)$, while the
utility of $u$ in a partition ${\mathcal{P}}$ is defined as ${\tt
ut}_{{\mathcal{P}}}(u)={\tt
ut}({\mathcal{P}}(u),u)=\sum_{v\in{\mathcal{P}}(u)}w(uv)$. Even though we
defined $w$ as a function to the integers, we will sometimes allow rational
edge weights, but with denominators sufficiently small that it will always be
easy to obtain an equivalent integer instance by multiplying all weights by an
appropriate integer. We use $w_{\max}$ to denote the maximum _absolute_ weight
of a given ASHG instance. Unless otherwise stated, we assume that $w$ is given
to us encoded in binary (and hence $w_{\max}$ may have value exponential in
the input size).

We are chiefly interested in the following notion of stability.

######  Definition 2.1 (Core stability).

A partition ${\mathcal{P}}$ of an ASHG $(G,w)$ is _core stable_ , if there
exists no $X\subseteq V(G)$ such that for all $u\in X$ we have ${\tt
ut}(X,u)>{\tt ut}_{{\mathcal{P}}}(u)$.

If the set $X$ mentioned Definition 2.1 does exist, then we say that
${\mathcal{P}}$ is unstable and that $X$ is a _blocking coalition_. For fixed
integer values of $k$, we will also study the notion of $k$-Core Stability: a
partition is $k$-core stable if no blocking coalition of size at most $k$
exists.

The two computational problems we are interested in are Core Stability (CS)
and Core Stability Verification (CSV). In the former problem we are given as
input an ASHG and are asked if there exists a core stable partition; in the
latter we also given a specific partition ${\mathcal{P}}$ and are asked if
${\mathcal{P}}$ is core stable.

We say that a partition $\mathcal{P}$ of $V(G)$ is _connected_ if $G[P]$ is
connected for every $P\in\mathcal{P}$. Notice that for both CSV and CS we may
assume that the partition ${\mathcal{P}}$ we seek or we are given is
connected, as replacing a disconnected coalition $P\in{\mathcal{P}}$ with a
coalition for each of its components does not change ${\tt
ut}_{{\mathcal{P}}}(u)$ for any $u\in V$ and hence does not affect stability.

###  2.1 Graph parameters and Parameterized Complexity

We assume the reader is familiar with the basics of parameterized complexity,
such as the classes FPT and W[1], as given for example in [CyganFKLMPPS15].
One particularity is that CSV is a coNP-complete problem, that is, a problem
for which one can easily verify No certificates (blocking coalitions). As a
consequence, some of our results will give coW[1]-hardness (rather than
W[1]-hardness) for CSV, by which we mean that the complement of any problem in
W[1] can be fpt-reduced to the problem at hand. We will say that a problem is
_weakly_ hard for a class, if the reduction we present uses exponentially
large weights (which therefore need to be encoded in binary). Conversely, if
the reduction is valid even when weights are encoded in unary (and are
therefore polynomially bounded) we say that the problem is _strongly_ hard.

We assume that the reader is also familiar with standard structural graph
parameters. The parameters we will focus on are treewidth (${\mathtt{tw}}$),
pathwidth (${\mathtt{pw}}$), tree-depth (${\mathtt{td}}$), vertex integrity
(${\mathtt{vi}}$), and vertex cover (${\mathtt{vc}}$). For the definitions of
treewidth and pathwidth, as well as the corresponding (nice) decompositions we
refer the reader to [CyganFKLMPPS15]. The vertex integrity ${\mathtt{vi}}(G)$
of a graph $G$ is defined as the minimum $k$ such that there exists a set
$S\subseteq V(G)$ (called a ${\mathtt{vi}}(k)$-set) such that the largest
component of $G-S$ has order at most $k-|S|$. The tree-depth of a graph $G$ is
defined inductively as follows: an isolared vertex has tree-depth $1$; the
tree-depth of a disconnected graph is the maximum of the tree-depth of its
components; the tree-depth of a connected graph $G$ is defined as $\min_{v\in
V(G)}{\mathtt{td}}(G-v)+1$. The vertex cover of $G$ is the size of the
smallest set of vertices of $G$ that intersects all edges.

It is well known that for all graphs $G$ we have
${\mathtt{tw}}(G)\leq{\mathtt{pw}}(G)\leq{\mathtt{td}}(G)\leq{\mathtt{vi}}(G)\leq{\mathtt{vc}}(G)+1$.
In terms of parameterized complexity these parameters therefore form a
hierarchy: if a problem is FPT for a smaller parameter, then it is FPT for the
larger ones and conversely if a problem is intractable for a large parameter,
then it is intractable for a smaller one. We therefore say that larger
parameters are more restrictive, with vertex cover being the most restrictive
parameter we consider. We use $\Delta(G)$ to denote the maximum degree of a
graph $G$. We omit $G$ from notation, if it is clear from context.

##  3 Core Stability Verification

In this section we study the complexity of Core Stability Verification (CSV).
What we discover is that this is an unusually intractable problem, even for
quite restricted parameterizations. In particular, we present the three
following hardness results:

  * •

CSV is weakly coNP-complete on graphs of vertex cover number 2. (Theorem 3.1)

  * •

CSV is strongly coW[1]-hard parameterized by vertex integrity. (Theorem 3.3)

  * •

CSV is coW[1]-hard parameterized by tree-depth, even if all weights are in
$\\{-1,1\\}$. (Theorem 3.5)

Our results indicate that, even though some of the problem’s intractability
can be attributed to the edge weights, a large part of its complexity is due
to the graph-theoretic structure of the input, and the problem is intractable
for tree-depth (and hence for pathwidth and treewidth) even for very small
weights. These hardness results are complemented by several algorithms, which
show that the hardness results are essentially tight. In particular:

  * •

In Theorem 3.7 we show that CSV is in P for trees, therefore, Theorem 3.1
cannot apply to graphs of vertex cover 1.

  * •

In Theorem 3.9 we show that CSV is in XP parameterized by vertex cover when
weights are polynomially bounded. This implies that Theorem 3.1 cannot be
improved to give strong coNP-completeness.

  * •

In Theorem 3.11 we show that CSV is FPT parameterized by
${\mathtt{vi}}+w_{\max}$, so Theorem 3.5 cannot be extended to CSV
parameterized by vertex integrity.

  * •

Theorem 3.5 is matched by an XP algorithm parameterized by treewidth with
parameter dependence $(\Delta w_{\max})^{O({\mathtt{tw}})}$, i.e. an XP
algorithm when weights are polynomially bounded (Theorem 3.13).

  * •

The former algorithm can be improved to an FPT running time (even for
unbounded weights) if we parameterize by ${\mathtt{tw}}+\Delta$. This was
already observed by Peters [Peters16a], who gave an algorithm with dependence
$2^{O(\Delta^{2}{\mathtt{tw}})}$, but we improve this complexity to
$2^{O(\Delta{\mathtt{tw}})}$ (Theorem 3.15).

###  3.1 Hardness Results

We first prove the following three hardness results.

######  Theorem 3.1.

Core Stability Verification is weakly coNP-complete on graphs of vertex cover
number 2.

Figure 1: The graph $(G,w)$ constructed in the proof of Theorem 3.9. The
vertex cover is marked by blue squares. The initial partition is given by dot-
dashed boxes, sngletons are omitted.

######  Proof 3.2.

We give a reduction from Partition. Given a set of positive integers
$A=\\{a_{1},\ldots,a_{n}\\}$, the Partition problem asks whether there exists
a subset $A^{\prime}$ of $A$ such that $\sum_{a\in A^{\prime}}a=s/2$ where
$s=\sum_{a\in A}a$. This problem is well-known to be weakly NP-complete
[GareyJ79].

We construct an instance of CSV. First, we create $n$ vertices
$v_{1},\ldots,v_{n}$ corresponding to $a_{1},\ldots,a_{n}\in A$ and three
vertices $x,y,x^{\prime},y^{\prime}$. Then we add edges $v_{i}x$ of weight
$a_{i}+\epsilon$, $v_{i}y$ of weight $-a_{i}$, $xx^{\prime}$ of weight $3s/2$,
$yy^{\prime}$ of weight $s/2$, and $xy$ of weight $s+\epsilon$. Here, without
loss of generality, let $\epsilon$ be an integer sufficiently smaller than
$\min_{i}a_{i}$; this can be achieved for example by multiplying all elements
of $A$ (and $s$) by $n$, and setting $\epsilon=1$. Let $(G,w)$ be the
constructed graph (see Figure 1). A coalition structure ${\mathcal{P}}$ to
verify consists of $\\{x,x^{\prime}\\}$, $\\{y,y^{\prime}\\}$ and singletons
of other vertices. Also note that $\\{x,y\\}$ is a vertex cover of $G$.

If there exists $A^{\prime}\subseteq A$ such that $\sum_{a\in
A^{\prime}}a=s/2$, then the coalition $X=\\{v_{i}:a_{i}\in
A^{\prime}\\}\cup\\{x,y\\}$ blocks ${\mathcal{P}}$. To see this, observe that
the utility of each vertex in $X$ increases by $\epsilon$ and thus $X$ is a
blocking coalition of ${\mathcal{P}}$.

Conversely, suppose that there exists a blocking coalition $X$ of
${\mathcal{P}}$. Clearly, $X$ contains neither $x^{\prime}$ nor $y^{\prime}$.
If $X$ does not contain $x$, no vertex can have positive utility in $X$. Thus,
they also do not join $X$. Consequently, $X=\\{y\\}$ holds, but this
contradicts that $X$ is a blocking coalition. Thus, $X$ must contain $x$. To
increase the utility of $x$, $y$ must be contained in $X$. In particular, if
$y$ was not contained in $X$, then the utility of $x$ would be at most
$s+n\epsilon<3s/2$. Since $y$ must have utility more than $s/2$ in $X$, it
holds that $\sum_{v_{i}\in X}a_{i}\leq s/2$. Finally, as the utility of $x$
must increase by more than $s/2$ and $\epsilon$ is sufficiently smaller than
$\min_{i}a_{i}$, $X$ satisfies that $\sum_{v_{i}\in X}a_{i}=s/2$, which
implies that there exists a subset $A^{\prime}$ of $A$ such that $\sum_{a\in
A^{\prime}}a=s/2$.

We use a similar but more involved construction to reduce Bin Packing to CSV.

######  Theorem 3.3.

Core Stability Verification is coW[1]-hard parameterized by vertex integrity
even if all weights are bounded by a polynomial in the input size.

######  Proof 3.4 (Proof).

Figure 2: The graph $(G,w)$ constructed in the proof of Theorem 3.3. The
coalition structure $\mathcal{P}$ is indicated by the dash-dotted box
(singletons are omitted). Furthermore, the vertices of the deletion set are
represented by blue squares and edges without label have weight $\rho$.

We give a reduction from Bin Packing. Given a set of positive integers
$A=\\{a_{1},\ldots,a_{n}\\}$ and an integer $k$, the Bin Packing problem asks
whether there exists a partition $\mathcal{Q}=(Q_{1},\dots,Q_{k})$ of $A$ such
that $\sum_{a\in Q_{i}}a=s/k$ for every $i\in[k]$ where $s:=\sum_{a\in A}a$.
This problem is known to be W[1]-hard parameterized by $k$, even if all
integers are given in unary (that is, if weights are polynomially bounded in
$n$) [JansenKMS13].

We construct an instance of CSV as follows. First we construct a weighted
graph $(G,w)$. We create a vertex $x$ and two cycles $(y_{1},\dots,y_{k})$ and
$(z_{1},\dots,z_{k})$. Every edge of the cycle $(y_{1},\dots,y_{k})$ has
weight $2s-s/k$ while every edge of the cycle $(z_{1},\dots,z_{k})$ has weight
$-s$. Now, we create an edges $xy_{i}$ of weight $2s+2s/k$ and an edge
$y_{i}z_{i}$ of weight $2s+s/k+\delta$ for every $i\in[k]$ where
$\delta:=\frac{1}{4}$. For every $a_{i}\in A$ we create a clique $A_{i}$
consisting of $k$ vertices $v_{i}^{1},\dots,v_{i}^{k}$ and edges of weight
$\rho$ where $\rho$ is an integer smaller than $-(a_{i}+\epsilon)$. Finally,
we create edges $v_{i}^{j}y_{j}$ of weight $a_{i}+\epsilon$ and edges
$v_{i}^{j}z_{j}$ of weight $-a_{i}$ for every $i\in[n]$, $j\in[k]$ where
$\epsilon:=\frac{1}{2n}$. Note that we can easily make all weights integer by
multiplying all weights by $2n$. The coalition structure $\mathcal{P}$ we want
to verify consists of the set $\\{x,y_{1},\dots,y_{k}\\}$ and singletons for
every vertex $v\in V(G)\setminus\\{x,y_{1},\dots,y_{k}\\}$. We now argue that
$(A,k)$ is a YES-instance of Bin Packing if and only if $((G,w),\mathcal{P})$
is a NO-instance of CSV.

First assume that $(A,k)$ is a YES-instance of Bin Packing and
$\mathcal{Q}=(Q_{1},\dots,Q_{k})$ is a partition such that $\sum_{a\in
Q_{i}}a=s/k$ for every $i\in[k]$. We now claim that the set
$X:=\\{y_{1},\dots,y_{k},z_{1},\dots,z_{k}\\}\cup\bigcup_{j\in[k]}\\{v_{i}^{j}:a_{i}\in
Q_{j}\\}$ is a blocking coalition for $\mathcal{P}$. To verify observe that
the utility of every vertex $v_{i}^{j}\in X$ increases by $\epsilon$.
Furthermore, the utility of $y_{i}$ improved by $\epsilon\cdot|Q_{i}|$ and the
utility of $z_{i}$ by $\delta$ and hence $X$ is a blocking coalition of
$\mathcal{P}$.

Now assume that $(G,\mathcal{P})$ is a NO-instance of CSV and $X$ is a
blocking coalition of $\mathcal{P}$. First note that $x$ cannot be in $X$ as
its utility in $\mathcal{P}$ is maximum. Furthermore, $X$ must contain some
element from $\\{y_{1},\dots,y_{k}\\}$ as every edge weight in the graph
$G[\\{z_{1},\dots,z_{k}\\}\cup\\{v_{i}^{j}:i\in[n],j\in[k]\\}]$ is negative.
Now observe that the utility of $y_{i}$ in the coalition
$V(G)\setminus\\{x\\}$ is $7s-s/k+\delta+\epsilon n<7s-s/k+1$ for every
$i\in[k]$. Since the utility of $y_{i}$ is $6s$ in $\mathcal{P}$ this implies
that if $y_{i}\in X$ then every neighbor $u$ of $y_{i}$ for which
$w(uy_{i})\geq 2s-s/k$ must also be in $X$. Hence, $y_{i}\in X$ implies
$y_{i-1},y_{i+1},z_{i}\in X$ (or $y_{n},y_{2},z_{2}\in X$ in case $i=1$ or
$y_{n-1},y_{1},z_{n}\in X$ in case $i=n$). Combining this with our earlier
argument that $X\cap\\{y_{1},\dots,y_{k}\\}$ cannot be empty we obtain that
$\\{y_{1},\dots,y_{k},z_{1},\dots,z_{k}\\}$ must be a subset of $X$.

We now define $Q_{j}:=\\{a_{i}:v_{i}^{j}\in X\\}$ for every $j\in[k]$. First
observe that $Q_{j}\cap Q_{j^{\prime}}=\emptyset$ for every pair
$j,j^{\prime}\in[k]$ as the edge $v_{i}^{j}v_{i}^{j^{\prime}}$ having weight
$\rho<-(a_{i}+\epsilon)$ prevents the simultaneous containment of $v_{i}^{j}$
and $v_{i}^{j^{\prime}}$ in $X$. We now argue that $|Q_{i}|=s/k$. For this
observe that the utility of $y_{j}$ in the coalition
$\\{y_{1},\dots,y_{k},z_{1},\dots,z_{k}\\}$ is $6s-s/k+\delta$. Hence
$\sum_{i\in[n],\atop{v_{i}^{j}\in X}}a_{i}+|\\{i:v_{i}^{j}\in
X\\}|\epsilon>s/k-\frac{1}{4}$. Since $|\\{i:v_{i}^{j}\in
X\\}|\epsilon\leq\frac{1}{2}$ and the $a_{i}$’s are integer we get that
$\sum_{a_{i}\in Q_{j}}a_{i}=\sum_{i\in n,\atop{v_{i}^{j}\in X}}a_{i}\geq s/k$.
On the other hand, the utility of $z_{j}$ in the coalition
$\\{y_{1},\dots,y_{k},z_{1},\dots,z_{k}\\}$ is $s/k+\delta$. Since all edges
of the form $z_{j}v_{i}^{j}$ have weight $-a_{i}$ this implies that
$\sum_{i\in[n],\atop{v_{i}^{j}\in X}}a_{i}<s/k+\frac{1}{4}$. Since all
$a_{i}$’s are integer this condition is equivalent to $\sum_{a_{i}\in
Q_{j}}a_{i}=\sum_{i\in[n],\atop{v_{i}^{j}\in X}}a_{i}\geq s/k$. Hence we have
argued that $\mathcal{Q}$ is a partition of $A$ into $k$ parts such that
$\sum_{a_{i}\in Q_{j}}a_{i}=s/k$ for every $j\in k$.

Finally, observe that the graph $G$ has vertex integrity $3k$ and cluster
deletion number $2k$ which is witnessed by deletion set
$\\{y_{1},\dots,y_{k},z_{1},\dots,z_{k}\\}$.

We prove the third hardness result by a reduction from Bounded Degree
Deletion.

######  Theorem 3.5.

Core Stability Verification is coW[1]-hard parameterized by tree-depth, even
if all weights are in $\\{-1,1\\}$.

######  Proof 3.6 (Proof ).

We present a reduction from Bounded Degree Deletion, which is known to be
W[1]-hard parameterized by tree-depth [GanianKO21, LampisV23]. In this problem
we are given a graph $G$ and an integer $\Delta^{*}$ and are asked to find the
largest induced subgraph of $G$ that has maximum degree at most $\Delta^{*}$
(equivalently, we seek the smallest set of vertices whose deletion makes the
maximum degree of $G$ at most $\Delta^{*}$).

Let $(G,\Delta^{*},s)$ be an instance of Bounded Degree Deletion and suppose
we want to decide if $G$ contains an induced subgraph of maximum degree at
most $\Delta^{*}$ with at least $s$ vertices. We construct an instance of CSV
as follows: we keep $G$ and we assign every edge of $G$ weight $-1$; we
construct two new vertices $x,x^{\prime}$; we construct $s(\Delta^{*}+1)-1$
new vertices and connect each to both $x$ and $x^{\prime}$ with edges of
weight $1$; for each $u\in V(G)$ we construct $\Delta^{*}+1$ new vertices
$u_{1},\ldots,u_{\Delta^{*}+1}$ and connect them to $x$ and $u$ with edges of
weight $1$; finally we attach to each $u_{i}$, for $u\in
V(G),i\in[\Delta^{*}+1]$ a leaf $u_{i}^{\prime}$ connected to it via an edge
of weight $1$. The initial partition we wish to check for stability places
$x,x^{\prime}$ and their common neighbors together; for each $u\in
V(G),i\in[\Delta^{*}+1]$ $u_{i},u_{i}^{\prime}$ are together; while all other
vertices are singletons.

It is not hard to see that the new graph has essentially the same tree-depth
as $G$, as deleting $x,x^{\prime}$ gives us $G$ with some paths of length $2$
attached to each vertex and some isolated vertices.

For the forward direction, suppose that $G$ does contain a set of vertices $S$
such that $|S|\geq s$ and $G[S]$ has maximum degree at most $\Delta^{*}$. We
claim that if we take $S\cup\\{x\\}$ and add to it all $u_{i}$ such that $u\in
S$, then we obtain a blocking coalition. Indeed, the utility of $x$ in the
initial partition is $s(\Delta^{*}+1)-1$, while in the new coalition it is
$|S|(\Delta^{*}+1)\geq s(\Delta^{*}+1)$. Furthermore, all vertices $u_{i}$ of
the new coalition previously had utility $1$, whereas in the new coalition
they have utility $2$. Finally, each $u\in S$ now has utility
$\Delta^{*}+1-|N(u)\cap S|\geq 1$ while previously $u$ had utility $0$.

For the converse direction, suppose that a blocking coalition $X$ exists.
Then, $x^{\prime}$ cannot belong in such a coalition, as its utility is
already maximum, and neither can the common neighbors of $x$ and $x^{\prime}$.
Similarly, $u_{i}^{\prime}$ cannot be in $X$. If $x$ does not belong in $X$,
then no $u_{i}$ can be in $X$, as the maximum utility she could obtain is $1$,
which is the same as her initial utility. As all remaining vertices only have
negative utilities to each other, this would lead to a contradiction.
Therefore, $x\in X$. However, for $x$ to increase her utility, it must be the
case that $X$ contains at least $s$ vertices of $G$. To see this, observe that
if $u\not\in X$, then $u_{i}\not\in X$ for all $i\in[\Delta^{*}]$. However, we
need the utility of $x$ in $X$ to be at least $s(\Delta^{*}+1)$, and since
from each $u\in S$ we have at most $\Delta^{*}+1$ vertices $u_{i}$ which are
in $X$, we conclude that $|X\cap V(G)|\geq s$. We now argue that $G[X\cap
V(G)]$ has maximum degree at most $\Delta^{*}$. Indeed, if $u\in X\cap V(G)$
has at least $\Delta^{*}+1$ neighbors in $X\cap V(G)$, since each such
neighbor contributes $-1$ to the utility of $u$, $u$ cannot have strictly
positive utility. We therefore have that $X\cap V(G)$ is a valid solution to
the original instance.

###  3.2 Algorithms

In this section, we prove the algorithmic results complementing the hardness
results of the previous section.

######  Theorem 3.7.

Core Stability Verification is polynomial time solvable on trees.

######  Proof 3.8 (Proof).

This can be shown using a simple bottom-up dynamic programming approach. Let
$(T,w)$ be a weighted tree and $\mathcal{P}$ a coalition structure of $(T,w)$.
We arbitrarily pick a root vertex $r\in V(T)$ to define an ancestor/descendant
relationship on $T$. For any $u\in V(T)$ we let $T_{u}$ be the sub-tree of $T$
rooted at $u$. We say that a set $X\subseteq V(T_{u})$ with $u\in X$ is a
downwards blocking coalition if ${\tt ut}(X,v)>{\tt ut}_{\mathcal{P}}(v)$ for
every vertex $v\in X$, $v\not=u$. For any $u\in V(T)$ we define ${\tt
ut}_{\operatorname{below}}(u)$ to be the maximum utility $u$ can achieve in
any downwards blocking coalition $X\subseteq V(T_{u})$ which contains $u$.

First note that ${\tt ut}_{\operatorname{below}}(u)$ of any leaf of $T$ is
$0$. Furthermore, if $u$ is a vertex, $X\subseteq V(T_{u})$ a downwards
blocking coalition with $u\in X$ such that ${\tt ut}(X,u)={\tt
ut}_{\operatorname{below}}(u)$ and $v$ a child of $u$ with $w(uv)<0$ then
$v\notin X$. That is because otherwise $X\setminus V(T_{v})$ will yield a
downwards blocking coalition with larger utility for $u$. Let $u$ be a non-
leaf vertex and $v_{1},\dots,v_{\ell}$ its children. Note that $v_{i}$ can be
contained in a downward blocking coalition $X\subseteq V(T_{u})$ with $u\in X$
if and only if ${\tt ut}_{\operatorname{below}}(v_{i})+w(uv_{i})>{\tt
ut}_{\mathcal{P}}(v_{i})$. Hence,

${\tt ut}_{\operatorname{below}}(u)=\sum_{i\in[\ell]\atop{w(uv_{i})\geq
0\atop{{\tt ut}_{\operatorname{below}}(v_{i})+w(uv_{i})>{\tt
ut}_{\mathcal{P}}(v_{i})}}}w(uv_{i}).$

Now note that a downwards blocking coalition $X\subseteq V(T_{u})$ with $u\in
X$ is a blocking coalition of $\mathcal{P}$ if and only if ${\tt
ut}_{\operatorname{below}}(u)>{\tt ut}_{\mathcal{P}}(u)$. Furthermore, there
is a blocking coalition $X$ of $\mathcal{P}$ if and only if there is $u\in
V(T)$ such that $X\subseteq V(T_{u})$ with $u\in X$ is a downwards blocking
coalition and ${\tt ut}_{\operatorname{below}}(u)>{\tt ut}_{\mathcal{P}}(u)$.
That is as we can assume that any blocking coalition $X$ is connected and
hence $X$ must contain a vertex $u$ which is an ancestor of every vertex $v\in
X$.

Hence, a bottom-up dynamic programming algorithm computing ${\tt
ut}_{\operatorname{below}}(u)$ for every $u\in V(T)$ and then verifying
whether there is $u\in V(T)$ with ${\tt ut}_{\operatorname{below}}(u)>{\tt
ut}_{\mathcal{P}}(u)$ yields a linear time algorithm for CSV.

######  Theorem 3.9.

Core Stability Verification can be solved in time
$({\mathtt{vc}}w_{\max})^{O({\mathtt{vc}})}\Delta^{2}+O({\mathtt{vc}}n)$.

######  Proof 3.10.

Given a graph $(G,w)$ and a partition ${\mathcal{P}}$ of $V(G)$, we check
whether there is a blocking coalition $X\subseteq V(G)$ of ${\mathcal{P}}$. In
the algorithm, we first compute a minimum vertex cover $S$ of size
${\mathtt{vc}}$ in time $O(1.2738^{{\mathtt{vc}}}+{\mathtt{vc}}n)$ [ChenKX10].
Then we guess an intersection of $X$ and $S$. The number of possible
candidates of the intersection is at most $2^{|S|}$. Let $I^{\prime}\subseteq
V(G)\setminus S$ be the set of vertices in $V(G)\setminus S$ such that each
vertex $u\in I^{\prime}$ satisfies $\sum_{v\in N_{G}(u)\cap X\cap
S}w(uv)>{{\tt ut}}_{{\mathcal{P}}}(u)$. These vertices in $I^{\prime}$ could
form a blocking coalition of ${\mathcal{P}}$ by cooperating with the vertices
in $X\cap S$. In order for $X$ to become a blocking coalition, all the
vertices in $X\cap S$ must have larger utility in $X$ than their utility in
${\mathcal{P}}$ after some vertices in $I^{\prime}$ joined $X$. This condition
can be represented in Integer Linear Programming (ILP) as follows:

$\displaystyle\sum_{v\in I^{\prime}}w(uv)x_{v}+\sum_{v\in N_{G}(u)\cap X\cap
S}w(uv)\geq{\tt ut}_{{\mathcal{P}}}(u)+1\ \ \ $ $\displaystyle\forall u\in
X\cap S$ (1) $\displaystyle x_{v}\in\\{0,1\\}\ \ \ $ $\displaystyle\forall
v\in I^{\prime}$ (2)

where the variable $x_{v}$ represents whether vertex $v\in I^{\prime}$ joins
$X$. In the left hand side of (1), $\sum_{v\in N_{G}(u)\cap X\cap S}w(uv)$
represents the contribution of edge weights in $X\cap S$ to the utility of
$u$. Clearly, the ILP is feasible if and only if there is a blocking coalition
$X$ because the utility of each agent in $X$ strictly increases. Note that we
suppose that each edge weight is an integer.

Here, the feasibility check of an ILP $\\{Ax=b,x\geq 0,x\in\mathbb{Z}^{n}\\}$
can be solved in time $(m\cdot\Lambda)^{O(m)}\cdot||b||^{2}_{\infty}$ where
$A\in\mathbb{Z}^{n\times m}$, $b\in\mathbb{Z}^{m}$, and $\Lambda$ is an upper
bound on each absolute value of an entry in $A$ [EisenbrandW20]. Since the
maximum absolute value of coefficients of variables is $w_{\max}$, the range
of ${\tt ut}_{{\mathcal{P}}}(u)$ and $\sum_{v\in N_{G}(u)\cap X\cap S}w(uv)$
is $[-w_{\max}\Delta,w_{\max}\Delta]$, and the number of constraints is at
most $|S|$, the ILP can be solved in time
$({\mathtt{vc}}w_{\max})^{O({\mathtt{vc}})}(w_{\max}\Delta)^{2}=({\mathtt{vc}}w_{\max})^{O({\mathtt{vc}})}\Delta^{2}$.
Thus, the total running time is
$O(1.2738^{{\mathtt{vc}}}+{\mathtt{vc}}n)+2^{{\mathtt{vc}}}({\mathtt{vc}}w_{\max})^{O({\mathtt{vc}})}\Delta^{2}=({\mathtt{vc}}w_{\max})^{O({\mathtt{vc}})}\Delta^{2}+O({\mathtt{vc}}n)$.

######  Theorem 3.11.

Core Stability Verification is FPT parameterized by ${\mathtt{vi}}+w_{\max}$.

######  Proof 3.12 (Proof).

As with Theorem 3.9, given a graph $(G,w)$ and a partition ${\mathcal{P}}$, we
check whether there is a blocking coalition $X\subseteq V(G)$ of
${\mathcal{P}}$. Let $S$ be a ${\mathtt{vi}}(k)$-set $S$ where
$k={\mathtt{vi}}$. One can find a ${\mathtt{vi}}(k)$-set $S$ in time
$O(k^{k+1}n)$ [DrangeDH16]. We define _types_ of components of
$G[V(G)\setminus S]$ with respect to isomorphisms, weights and the partition
$\mathcal{P}$. More precisely, we say that two components $C_{1}$ and $C_{2}$
of $G[V(G)\setminus S]$ have the same type, if there is an isomorphism $\iota$
from $G[C_{1}\cup S]$ to $G[C_{2}\cup S]$ such that $\iota(s)=s$ for every
$s\in S$, corresponding edges have the same weight and for every
$P\in\mathcal{P}$ there is $Q\in\mathcal{P}$ such that $\iota(P\cap
C_{1})=Q\cap C_{2}$. Let $\mathcal{T}$ be a set of representatives of all
component types appearing in $G[V(G)\setminus S]$ and $c_{t}$ the number of
components of $G[V(G)\setminus S]$ of type $t$ for every $t\in\mathcal{T}$. In
addition, we define $\mathcal{X}_{t}$ to be the set of subsets of $V(t)$.

We are ready to design an algorithm for CSV. First, we guess an intersection
of a blocking coalition $X$ and the ${\mathtt{vi}}(k)$-set $S$. The number of
subsets of $S$ is at most $2^{k}$. In the next step, we formulate CSV as an
ILP for each intersection $X\cap S$. First, we define variables
$x_{(t,X_{t})}$ for any type $t$ and any $X_{t}\in\mathcal{X}_{t}$. The
variable $x_{(t,X_{t})}$ represents the number of components of type $t$ in
$G[V(G)\setminus S]$ such that the blocking coalition $X$ intersects the
component in the set $Q_{t}$ corresponding to $X_{t}$ under the isomophism
witnessing the type. Since the number of non-isomorphic components is at most
$(w_{\max})^{O(k^{2})}$, the number of partitions of the vertices of a
component is at most $2^{k^{2}}$ (any partition corresponds to the subsets of
edges incident to vertices in the same part of the partition) and the size of
$\mathcal{X}_{t}$ for a type $t$ is at most $2^{k}$, the number of variables
is at most $(w_{\max})^{O(k^{2})}$. For a vertex $u\in X\cap S$, a type
$t\in\mathcal{T}$, and a set $X_{t}\in\mathcal{X}_{t}$, we denote by
$w_{(t,X_{t},u)}$ the sum of weights of edges incident to $u$ and a vertex in
$X_{t}$. It represents the increase of the utility of $u$ if $X_{t}$ joins the
blocking coalition $X$.

Let $\mathcal{X}^{\prime}_{t}\subseteq\mathcal{X}_{t}$ be the set of subsets
of $V(t)$ such that for every $X_{t}\in\mathcal{X}^{\prime}_{t}$, each vertex
in $X_{t}$ has higher utility in $X_{t}\cup(X\cap S)$ than in the initial
coalition ${\mathcal{P}}$. Moreover, let
$\mathcal{T}^{\prime}\subseteq\mathcal{T}$ be the set of types $t$ satisfying
that $\mathcal{X}^{\prime}_{t}\neq\emptyset$. Then deciding whether there
exists a blocking coalition can be formulated as the following ILP.

$\displaystyle\sum_{X_{t}\in\mathcal{X}^{\prime}_{t}}x_{(t,X_{t})}$
$\displaystyle=c_{t}$ $\displaystyle\forall t\in\mathcal{T}^{\prime},$
$\displaystyle\sum_{t\in\mathcal{T}^{\prime}}\sum_{X_{t}\in\mathcal{X}^{\prime}_{t}}w_{(t,X_{t},u)}x_{(t,X_{t})}+\sum_{v\in
N_{G}(u)\cap X\cap S}w(uv)$ $\displaystyle>{\tt ut}_{{\mathcal{P}}}(u)$
$\displaystyle\forall u\in X\cap S.$

The first equality encodes the constraint that the numbers $X_{(}t,X_{t})$,
$X_{t}\in\mathcal{X}_{t}$ should correspond to the sizes of the parts of a
partition of the $c_{t}$ components of type $t$. The second inequality
represents the constraint that each vertex $u\in X\cap S$ has larger utility
than the utility of $u$ in ${\mathcal{P}}$. It is clear that the ILP is
feasible if and only if there exists a blocking coalition.

For the running time of the algorithm, we first compute a
${\mathtt{vi}}(k)$-set $S$ in time $O(k^{k+1}n)$. For $S$, we guess $2^{k}$
intersections $X\cap S$, determine the type count $c_{t}$ for every type $t$
in time $O(k^{k}n)$ and solve the ILP for each $X\cap S$. Given an
intersection $X\cap S$, we can compute $w_{(t,X_{t},u)}$ and $\sum_{v\in
N_{G}(u)\cap X\cap S}w(vu)$ can be computed in polynomial time. Finally, it is
known that the feasibility of ILP with $p$ variables can be computed in FPT
time parameterized by $p$ [Lenstra83, FrankT87, Kannan87]. Since the number of
variables is at most $(w_{\max})^{O(k^{2})}$, one can solve CSV in time
$f(k+w_{\max})n^{O(1)}$ where $f$ is some computable function.

######  Theorem 3.13.

Core Stability Verification can be computed in time $(\Delta
w_{\max})^{O({\mathtt{tw}})}n^{O(1)}$.

######  Proof 3.14 (Proof).

Our algorithm relies on standard techniques (dynamic programming over tree
decompositions) so we sketch some of the details. We are given as input an
edge-weighted graph $(G,w)$, a nice tree decomposition of $G$, and an initial
partition ${\mathcal{P}}$ of $V(G)$. We are asked if there exists a blocking
coalition $X\subseteq V(G)$ such that all vertices $u\in X$ have a strictly
higher utility in $X$ than in their coalition in ${\mathcal{P}}$. We begin by
calculating for each $u\in V(G)$ the utility $u$ gains in the initial
partition ${\mathcal{P}}$. This can clearly be done in polynomial time in the
size of the input, that is, polynomial in $n+\log w_{\max}$.

Suppose now that the given nice tree decomposition is rooted at some arbitrary
bag and consider a bag $B$. In order to describe the dynamic programming table
that our algorithm needs to maintain for $B$, we define the signature of a
possible blocking coalition $X$ as a pair consisting of (i) the set $X\cap B$
(ii) a function ${\tt ut}:X\cap B\to\mathbb{Z}$ which describes for each
vertex $u$ that belongs in the bag $B$ and the blocking coalition $X$ how much
utility $u$ gains from vertices that appear in bags below $B$ in the tree
decomposition (but not in $B$). The dynamic programming algorithm maintains an
entry for each possible signature that tells us if there exists a coalition
$X$ that matches this signature and is feasible below $B$, that is, satisfying
the criterion that all vertices which appear only below $B$ in the
decomposition and belong in $X$ have strictly higher utility in $X$ than in
their coalition of ${\mathcal{P}}$.

Given the above it is now straightforward to implement the DP algorithm: for
Introduce nodes we consider two cases to produce the signatures of the new bag
(the introduced vertex belongs in $X$ or not); for Join nodes we take all
pairs of signatures that agree on $X\cap B$ and simply add their utility
functions; while for Forget nodes, if we are forgetting vertex $u$ we need to
discard signatures where $u\in X$ but the utility of $X$ is not strictly
higher than in ${\mathcal{P}}$, while for other signatures we adjust the
utilities of the neighbors of $u$ accordingly.

What remains is to estimate the running time of the algorithm. This is
dominated by the number of possible signatures, which is at most
$2^{{\mathtt{tw}}}(2\Delta w_{\max}+1)^{{\mathtt{tw}}}$. Here, the first
factor is for storing a subset of $B$, and the second is for storing the
utility of each vertex, which must necessarily be in the range $[-\Delta
w_{\max},\Delta w_{\max}]$.

######  Theorem 3.15.

Core Stability Verification can be computed in time
$2^{O({\mathtt{tw}}\Delta)}(n+\log w_{\max})^{O(1)}$.

######  Proof 3.16 (Proof).

This is obtained using the same algorithm as in Theorem 3.13 using the
following observation: in the analysis of the algorithm of Theorem 3.13 we
have a DP table which stores for each vertex $u$ of $X\cap B$ the utility that
$u$ gains in the blocking coalition $X$. The range of possible values was then
bounded by $[-\Delta w_{\max},\Delta w_{\max}]$. However, we can also observe
that the set of possible utilities of a vertex $u$ with degree $\Delta$ has
size at most $2^{\Delta}$, since the utility of $u$ is obtained by the subset
of its neighbors which are contained in $X$. As a result, our algorithm may
consider only the $2^{\Delta}$ possible utility values for each vertex of the
bag, giving $2^{\Delta{\mathtt{tw}}}$ possible distinct solution signatures.
The rest of the analysis is identical to that of Theorem 3.13.

##  4 Core Stability

In this section we study the complexity of Core Stability (CS). We first show
that CS remains $\Sigma_{2}^{p}$-complete even on graphs of bounded vertex
cover number (Theorem 4.4).

The second part of this section is dedicated to extending our understanding of
the complexity of CS parameterized by ${\mathtt{tw}}+\Delta$. We give an
algorithm for CS running in time
$2^{2^{\mathcal{O}(\Delta{\mathtt{tw}}^{2})}}n$ (Theorem 4.6) and improving on
the previous algorithm based on Courcelle’s Theorem by Peters [Peters16a]. In
order to avoid having to formulate a tedious dynamic programming algorithm, we
instead obtain our algorithm via a reduction to $\exists\forall$-SAT, which is
known to be solvable in double-exponential time (in treewidth) [Chen04]. We
complement these results by giving an ETH based lower bound of
$2^{2^{o({\mathtt{pw}})}}$ on graphs of bounded degree (Theorem 4.14). This
shows that the double-exponential dependence of our algorithm on treewidth is
in fact inevitable, and confirms a pattern shown by other
$\Sigma_{2}^{p}$-complete problems [LampisM17].

Before we proceed, we describe a gadget that appears in several reductions.

###  4.1 An Auxiliary Gadget

For reductions to CS we use a gadget to control what core stable partitions
(if any exist) have to look like. For this we rely on an example given in
[AzizBS13, Example 1] which shows a small concrete graph $H$ (on six vertices)
that does not admit any core stable partition and is minimal for this
property. The intuitive idea is that we _attach_ copies of $H$ onto various
vertices of our construction with the aim of forcing the vertex onto which $H$
is attached to be in the same partition as some vertex of $H$. Because by
assumption it is impossible to partition $H$ in a stable way, the vertex on
which a copy of $H$ is attached _must_ be placed in the same coalition as some
vertex of $H$. Building on this idea, we also attach a copy of $H$ on a set of
vertices of $G$, forcing at least one of them in the same partition as a
vertex of $H$.

To make this idea formally precise, we will use the following minimally non-
stable graph $(H,w_{\rho})$ where $\rho$ is some sufficiently small integer.
Let $H$ be $K_{6}$ with vertex set $\\{h,h_{1},\dots,h_{5}\\}$. We set
$w_{\rho}(hh_{1})=w_{\rho}(h_{2}h_{3})=w_{\rho}(h_{4}h_{5})=5$,
$w_{\rho}(h_{1}h_{2})=w_{\rho}(h_{3}h_{4})=w_{\rho}(h_{5}h)=4$ and
$w_{\rho}(h_{1}h_{3})=w_{\rho}(h_{3}h_{5})=w_{\rho}(h_{5}h_{1})=3$. We let all
remaining edges have weight $\rho$. Using the same argument as [AzizBS13] we
can show that $(H,w_{\rho})$ is not core stable if $\rho<-15$. We further
observe that for the graph
$(H\setminus\\{h\\},w_{\rho}|_{\\{h_{1},\dots,h_{5}\\}})$ the partition
$(\\{h_{1},h_{2},h_{3}\\},\\{h_{4},h_{5}\\})$ is core stable if $\rho<-15$. We
denote this partition of
$(H\setminus\\{h\\},w_{\rho}|_{\\{h_{1},\dots,h_{5}\\}})$ by
$\mathcal{P}_{(H,w_{\rho})}$.

For a graph $(G,w)$, $S\subseteq V(G)$ an independent set in $G$ and
$\rho,\xi$ integers, we let $(G^{\prime},w^{\prime})$ be the graph obtained in
the following way. The graph $(G^{\prime},w^{\prime})$ consist of the disjoint
union of $(G,w)$ and $(H,w_{\rho})$ to which we add the edges $hs$ of weight
$\xi$ for every $s\in S$ and edges $h_{i}s$ and $ss^{\prime}$ of weight $\rho$
for every $i\in[5]$, $s\not=s^{\prime}\in S$. We say that
$(G^{\prime},w^{\prime})$ is obtained from $G$ by _$\xi$ -attaching
$(H,w_{\rho})$ at $S$_. In the next lemma we show that attaching the gadget
$(H,w_{\rho})$ enforces certain properties for coalitions.

Let $(G,w)$ be a graph, $S\subseteq V(G)$ an independent set in $G$, $\rho$ an
integer smaller than $-\max_{u\in V(G^{\prime})}\sum_{uv\in
E(G^{\prime}),\atop{w^{\prime}(uv)>0}}w(uv)$, $\xi\geq 9$ and
$(G^{\prime},w^{\prime})$ the graph obtained from $(G,w)$ by $\xi$-attaching
$(H,w_{\rho})$ at $S$. The graph $(G^{\prime},w^{\prime})$ has the following
properties.

  1. $(\Pi 1)$

For every connected core stable partition $\mathcal{P}$ of
$(G^{\prime},w^{\prime})$ there is $s\in S$ and $P\in\mathcal{P}$ such that
$\\{s,h\\}\in P$ and $s^{\prime}\notin P$ for every $s^{\prime}\in S$,
$s^{\prime}\not=s$.

  2. $(\Pi 2)$

For every connected core stable partition $\mathcal{P}$ of
$(G^{\prime},w^{\prime})$ and every part $P\in\mathcal{P}$ with
$P\cap\\{h_{1},\dots,h_{5}\\}\not=\emptyset$ we have that
$P\subseteq\\{h_{1},\dots,h_{5}\\}$.

  3. $(\Pi 3)$

For every partition $\mathcal{P}$ of $(G^{\prime},w^{\prime})$ with
$\mathcal{P}_{(H,w_{\rho})}\subseteq\mathcal{P}$ and $\\{h,s\\}\subseteq P$
for some $s\in S$ and some $P\in\mathcal{P}$, every blocking coalition $X$ is
disjoint from $V(H)$.

Further, the properties are satisfied even if we add additional edges of
weight $\rho$ to $(G^{\prime},w^{\prime})$.

######  Proof 4.1.

To argue the furthermore part, we assume that we arbitrarily added edges of
weight $\rho$ to $(G^{\prime},w^{\prime})$. Note that we cannot add any edges
between vertices of $V(H)$ as $H$ is complete. Let $\mathcal{P}$ be a
connected core stable partition of $(G^{\prime},w^{\prime})$. First observe
that no two vertices $u,v\in V(G^{\prime})$ with $w(uv)=\rho$ can be contained
in the same part of the partition $\mathcal{P}$ due to the assumption that
$\rho<-\max_{u\in V(G^{\prime})}\sum_{uv\in
E(G^{\prime}),\atop{w^{\prime}(uv)>0}}w(uv)$ and hence the utility of $u$ and
$v$ in $\mathcal{P}$ would be negative. Similarly, no two vertices $u,v\in
V(G^{\prime})$ with $w(uv)=\rho$ can both be contained in a blocking
coalition.

Let $P\in\mathcal{P}$ be the part containing $h$. We first argue that any part
$P^{\prime}\in\mathcal{P}$, $P^{\prime}\not=P$ (and hence $h\notin
P^{\prime}$) containing some $h_{i}$, $i\in[5]$ is a subset of
$\\{h_{1},\dots,h_{5}\\}$. If $P^{\prime}$ is such a part, then $P^{\prime}$
cannot contain any vertex from $N^{\rho}(H)=\\{v\in
V(G):w(\tilde{h}v)=\rho\text{ for some }\tilde{h}\in V(H)\\}$. Since removing
$h$ and $N^{\rho}$ separates the vertices $\\{h_{1},\dots,h_{5}\\}$ from the
rest of the graph and we assumed that $G[P^{\prime}]$ is connected, we
conclude that $P^{\prime}\subseteq\\{h_{1},\dots,h_{5}\\}$. Since
$(H,w_{\rho})$ is not core stable this implies that the part $P$ must contain
some vertex $v\in V(G)$. But since we assumed that $G[P]$ is connected and the
removal of $S$ and $\\{v\in V(G):w(vh)=\rho\\}$ separates the set of vertices
$V(H)$ from the rest of the graph, $P$ must contain some vertex from $S$.
Since $w(ss^{\prime})=\rho$ for any $s,s^{\prime}\in S$, $s\not=s^{\prime}$,
this implies that property $(\Pi 1)$ is true. Additionally, observe that
$P\cap S\not=\emptyset$ imply that $P\cap\\{h_{1},\dots,h_{5}\\}=\emptyset$
and hence property $(\Pi 2)$ follows from our observation that
$P^{\prime}\subseteq\\{h_{1},\dots,h_{5}\\}$ for every part
$P^{\prime}\in\mathcal{P}$, $P^{\prime}\not=P$ containing some $h_{i}$,
$i\in[5]$.

To prove property $(\Pi 3)$ assume that $\mathcal{P}$ is a partition of
$V(G^{\prime})$ with $\\{h_{1},h_{2},h_{3}\\},\\{h_{4},h_{5}\\}\in\mathcal{P}$
and let $P\in\mathcal{P}$ be a part and $s\in S$ be an element such that
$\\{h,s\\}\subseteq P$. Assume $X$ is a blocking coalition. Towards a
contradiction, assume that $h\in X$. First observe that $h$ has utility $\xi$
in $\mathcal{P}$. Furthermore, $h$ is incident to two edges of positive weight
in $H$ and these two weights sum up to $9\leq\xi$. Hence, there has to be some
vertex $u\in V(G)$ which is contained in $X$ and $w(hu)>0$. By construction,
this implies that $u$ has to be a vertex in $S$. But then no other vertex
$v\in S\cup\\{h_{1},h_{5}\\}$ can be contained in $X$ as $w(uv)=\rho$ and
hence the utility of $h$ in $X$ can be at most $\xi$. Therefore, $h\notin X$.
Now observe that $h_{2}$ cannot join $X$ because its utility in $\mathcal{P}$
is the sum of its positive weight edges. But then $h_{1}$ cannot join because
the sum of its positive edges excluding edges incident to $h$ and $h_{2}$ is
$6$ and $h_{2}$ has utility $7$ in $\mathcal{P}$. But then $h_{3}$ cannot join
$X$ as its the sum of its positive edges excluding edges incident to $h_{1}$
and $h_{2}$ is $7$ while $h_{3}$ has utility $8$ in $\mathcal{P}$. Finally,
now $h_{4}$ and $h_{5}$ cannot join $X$ as $\\{h_{4},h_{5}\\}\subseteq X$ and
hence they cannot improve their utility without further vertices from $H$.
This concludes the proof of property $(\Pi 3)$.

We can also use the gadget in a slightly different way. Details are deferred
to the Appendix. For a graph $(G,w)$, $S\subseteq V(G)$ an independent set in
$G$, $\rho<-15$ and $\xi\geq 9$ we say that $(G^{\prime},w^{\prime})$ is
obtained from $(G,w)$ by _$\xi$ -neighborhood attaching $(H,w_{\rho})$ at $S$_
if $(G^{\prime},w^{\prime})$ is obtained from $(G,w)$ by $\xi$-attaching
$(H,w_{\rho})$ at $S$ and adding edges $hv$ of weight $\rho$ for every $v\in
N_{G}(S)\setminus S$.

######  Lemma 4.2.

Let $(G,w)$ be a graph, $S\subseteq V(G)$ an independent set, $\rho$ and
integer smaller than $-\max_{u\in V(G^{\prime})}\sum_{uv\in
E(G^{\prime}),\atop{w^{\prime}(uv)>0}}w(uv)$, $\xi\geq 9$ and
$(G^{\prime},w^{\prime})$ the graph obtained from $(G,w)$ by
$\xi$-neighborhood attaching $(H,w_{\rho})$ at $S$. The graph
$(G^{\prime},w^{\prime})$ has properties $(\Pi 2)$, $(\Pi 3)$ and the
following property.

  1. $(\Pi^{\prime}1)$

For every connected core stable partition $\mathcal{P}$ of
$(G^{\prime},w^{\prime})$ there is $s\in S$ such that
$\\{h,s\\}\in\mathcal{P}$.

######  Proof 4.3.

Since $(G^{\prime},w^{\prime})$ was obtained from $(G,w)$ be $\xi$-attaching
$(H,w_{\rho})$ at $S$ and adding some edges of weight $\rho$ we get that $(\Pi
1)$,$(\Pi 2)$ and $(\Pi 3)$ are satisfied. Assume $\mathcal{P}$ is a connected
core stable partition and $s\in S$ is an element and $P\in\mathcal{P}$ a part
such that $\\{s,h\\}\subseteq P$. Towards a contradiction assume that there is
$u\in P$ such that $u\not=s$, $u\not=h$. By property $(\Pi 1)$ and $(\Pi 2)$
we know that $u\in V(G)\setminus S$. As $h$ has no neighbors in $V(G)\setminus
S$ and $G[P]$ is connected, this implies that $P$ must contain some vertex
$v\in V(G)\setminus S$ which is adjacent to $s$. But this cannot happen as
$w(hv)=\rho$. Therefore, $P=\\{h,s\\}$ proving property $(\Pi^{\prime}1)$.

Observe that if we attach multiple copies of $(H,w_{\rho})$ to some graph $G$,
then the resulting graph does not depend on the order in which we attached
copies of $(H,w_{\rho})$ as long as the sets, at which we attached the copies,
are disjoint.

###  4.2 Core stability on graphs of bounded vertex cover number

In this section we prove the following result.

######  Theorem 4.4.

Core Stability is $\Sigma_{2}^{p}$-complete on graphs of bounded vertex cover
number.

To obtain this result we use a variation of the constructions used to prove
Theorem 3.1 and Theorem 3.3 however reducing from an appropriate variant of
Partition.

######  Proof 4.5.

Figure 3: The graph $(G,w)$ constructed in the proof of Theorem 4.4. Here all
edges without label have weight $\rho$. Vertex cover vertices are depicted by
blue squares.

First observe that CS is in $\Sigma_{2}^{p}$ since for any guessed coalition
structure $\mathcal{P}$ of $(G,w)$ deciding whether $\mathcal{P}$ is core
stable is in coNP. That is, given a blocking coalition $X$ we can verify in
polynomial time (by comparing utilities in $X$ and $\mathcal{P}$) whether
$\mathcal{P}$ is not core stable.

We show $\Sigma_{2}^{p}$-hardness by a reduction from
$\exists\forall$-partition. Given two sets of positive integers
$A=\\{a_{1},\ldots,a_{n}\\}$ and $B=\\{b_{1},\ldots,b_{n}\\}$, the
$\exists\forall$-partition problem asks whether there exists a subset
$A^{\prime}\subseteq A$ such that for every subset $B^{\prime}\subseteq B$ it
holds that $\sum_{c\in A^{\prime}\cup B^{\prime}}c\not=s/2$ where
$s=\sum_{c\in A\cup B}c$. We let $s_{A}=\sum_{a\in A}a$ and $s_{B}=\sum_{b\in
B}b$. Note that a variant of $\exists\forall$-partition was shown to be
$\Sigma_{2}^{p}$-hard [berman1997complexity, Lemma 6.2.] where a target value
$t$ is given additionally and the question is whether there exists
$A^{\prime}\subseteq A$ such that for every $B^{\prime}\subseteq B$ it holds
that $\sum_{c\in A^{\prime}\cup B^{\prime}}c\not=t$. We can reduce this
variant to $\exists\forall$-partition by adding integer $2s-t$ to $A$ and
$s+t$ to $B$ where $s=\sum_{c\in A\cup B}c$.

We construct an instance $(G,w)$ of CS as follows. First we let $\delta>0$ be
an integer smaller than $\min_{i\in[n]}\\{a_{i},b_{i}\\}$ and $\epsilon>0$ be
an integer such that $\epsilon<\delta/n$. We can assume that such integers
exist by picking a suitable positive integer and multiplying all elements in
$A\cup B$ by it. We further set $\rho=-30s$. We introduce vertices
$x,\widehat{x}$ and add edge $x\widehat{x}$ of weight $9.5s$. We further
introduce vertices $u_{i},v_{i}$ for every $i\in[n]$ and add edges $u_{i}x$,
$u_{i}\widehat{x}$ of weight $a_{i}$, $v_{i}x$ of weight $-b_{i}$ and
$v_{i}\widehat{x}$ of weight $b_{i}+\epsilon$. We now take two copies
$(H,w_{\rho})$ on vertex set $\\{h,h_{1},\dots,h_{5}\\}$ and
$(\widehat{H},\widehat{w}_{\rho})$ on vertex set
$\\{\widehat{h},\widehat{h}_{1},\dots,\widehat{h}_{5}\\}$ of the graph
$(H,w_{\rho})$ and $(9s+s_{A}-\delta)$-attach $(H,w_{\rho},h)$ at $\\{x\\}$
and $(10s-\delta)$-attach $(\widehat{H},\widehat{w}_{\rho},\widehat{h})$ at
$\\{\widehat{x}\\}$. Additionally, we add an edge $h\widehat{h}$ of weight
$\rho$ and $v_{i}h$, $v_{i}\widehat{h}$ of weight $\rho$ for every $i\in[n]$.
For an illustration of the construction see Figure 3. Note that $G$ has vertex
cover number $12$ which is witnessed by the vertex cover
$\\{x,\widehat{x},h_{1},h_{2},h_{4},h_{5},h,\widehat{h}_{1},\widehat{h}_{2},\widehat{h}_{4},\widehat{h}_{5},\widehat{h}\\}$.
In the following we argue that $(A,B)$ is a YES-instance of
$\exists\forall$-partition if and only if $(G,w)$ admits a core stable
partition.

First assume that $(A,B)$ is a YES-instance of $\exists\forall$-partition and
let $A^{\prime}\subseteq A$ be a subset such that $\sum_{c\in A^{\prime}\cup
B^{\prime}}c\not=s/2$ for every $B^{\prime}\subseteq B$. We define a partition
$\mathcal{P}$ of $V(G)$ as follows. The partition $\mathcal{P}$ contains
partitions $\mathcal{P}_{(H,w_{\rho})}$ and
$\mathcal{P}_{(\widehat{H},\widehat{w}_{\rho})}$ defined in the previous
section. Furthermore, $\mathcal{P}$ contains the sets
$\\{h,x\\}\cup\\{u_{i}:a_{i}\in A^{\prime}\\}$,
$\\{\widehat{h},\widehat{x}\\}\cup\\{u_{i}:a_{i}\notin A^{\prime}\\}$ and
$\\{v_{i}\\}$ for every $i\in[n]$. We claim that $\mathcal{P}$ is core stable
and argue that there is no blocking coalition.

Towards a contradiction, assume that $X$ is a blocking coalition of
$\mathcal{P}$. By Lemma 4.1 $(\Pi 3)$ we know that
$X\subseteq\\{x,\widehat{x}\\}\cup\\{u_{i},v_{i}:i\in[n]\\}$. We first argue
that $\widehat{x}$ must be in $X$. To this end, observe that if any vertex
$v_{i}\in X$, then $\widehat{x}\in X$ as $v_{i}$ has utility $0$ in
$\mathcal{P}$ and the only edge incident to $v_{i}$ with positive weight is
$\widehat{x}v_{i}$. Additionally, if any vertex $u_{i}\in X$, then
$\widehat{x}\in X$ as $u_{i}$ has utility $a_{i}$ in $\mathcal{P}$ and the
only edges incident to $u_{i}$ of positive weight are $xu_{i}$ and
$\widehat{x}u_{i}$ which both have weight $a_{i}$. Lastly, if $x\in X$, then
$\widehat{x}\in X$ as $x$ has utility at least $9s+s_{A}-\delta$ in
$\mathcal{P}$ and the sum of all positive weights of edges incident to $x$ is
$s$ if we exclude $x\widehat{x}$ and $hx$. Note that $h$ does not join $X$.
Since $X\not=\emptyset$, we conclude that $\widehat{x}\in X$. This implies
that $x\in X$ as $x$ has utility at least $10s-\delta$ in $\mathcal{P}$ and
the sum of all positive weights of edges incident to $x$ if we exclude the
edges $x\widehat{x}$ and $\widehat{h}\widehat{x}$ is $s_{A}$.

We set $B^{\prime}=\\{b_{i}:v_{i}\in X\\}$ and claim that $\sum_{c\in
A^{\prime}\cup B^{\prime}}c=s/2$. First note that $x$ has utility
$9s+s_{A}-\delta+\sum_{a\in A^{\prime}}a$ in $\mathcal{P}$ while $x$ has
utility $9.5s+\sum_{u_{i}\in X}a_{i}-\sum_{b\in B^{\prime}}b$ in $X$. Since
$X$ is a blocking coalition we get that

$9s+s_{A}-\delta+\sum_{a\in A^{\prime}}a<9.5s+\sum_{u_{i}\in
X}a_{i}-\sum_{b\in B^{\prime}}b\leq 9.5s+s_{A}-\sum_{b\in B^{\prime}}b.$

Hence, $s/2\geq\sum_{c\in A^{\prime}\cup B^{\prime}}c$ since
$\delta<\min_{i\in[n]}\\{a_{i},b_{i}\\}$. Furthermore, $\widehat{x}$ has
utility $10s-\delta+\sum_{a\notin A^{\prime}}a$ in $\mathcal{P}$ while
$\widehat{x}$ has utility $9.5s+\sum_{u_{i}\in X}a_{i}+\sum_{b\in
B^{\prime}}(b+\epsilon)$ in $X$. As $X$ is a blocking coalition and
$\sum_{a\notin A^{\prime}}a=s_{A}-\sum_{a\in A^{\prime}}a$ we get that

$10s-\delta+s_{A}-\sum_{a\in A^{\prime}}a<9.5s+\sum_{u_{i}\in
X}a_{i}+\sum_{b\in B^{\prime}}(b+\epsilon)\leq 9.5s+s_{A}+\sum_{b\in
B^{\prime}}b+n\epsilon.$

Hence, $s/2\leq\sum_{c\in A^{\prime}\cup B^{\prime}}c$ since
$\delta<\min_{i\in[n]}\\{a_{i},b_{i}\\}$ and $n\epsilon<\delta$. Combined we
get that $\sum_{c\in A^{\prime}\cup B^{\prime}}c=s/2$ which contradicts the
choice of $A^{\prime}$.

Now assume that $(G,w)$ is a YES-instance of CS and let $\mathcal{P}$ be a
connected, core stable partition of $G$. We use the following. We first argue
that $\\{v_{i}\\}$ is a part in $\mathcal{P}$ for every $i\in[n]$. First
observe that $v_{i}$ cannot be in the same part as $\widehat{x}$ as by Lemma
4.1 $(\Pi 1)$ this part also contains $\widehat{h}$ and
$w(\widehat{h},v_{i})=\rho$. Furthermore, every edge incident to $v_{i}$
excluding $\widehat{x}v_{i}$ has negative weight. Hence, if
$\\{v_{i}\\}\notin\mathcal{P}$ then $\\{v_{i}\\}$ would be a blocking
coalition.

By Lemma 4.1 $(\Pi 1)$ there are parts $P,\widehat{P}$ of $\mathcal{P}$ such
that $\\{h,x\\}\subseteq P$ and
$\\{\widehat{h},\widehat{x}\\}\subseteq\widehat{P}$. Additionally,
$P\not=\widehat{P}$ as $w(h\widehat{h})=\rho$. We set
$A^{\prime}=\\{a_{i}:u_{i}\in P\\}$. In the following we argue that
$\sum_{c\in A^{\prime}\cup B^{\prime}}c\not=s/2$ for every
$B^{\prime}\subseteq B$. Towards a contradiction, assume that there is
$B^{\prime}\subseteq B$ such that $\sum_{c\in A^{\prime}\cup
B^{\prime}}c=s/2$. We define $X$ to be the set of vertices
$\\{x,\widehat{x}\\}\cup\\{u_{i}:i\in[n]\\}\cup\\{v_{i}:b_{i}\in
B^{\prime}\\}$ and claim that this is a blocking coalition. First note that
the utility of every vertex $v_{i}$ is $0$ in $\mathcal{P}$ as
$\\{v_{i}\\}\in\mathcal{P}$. On the other hand, the utility of $v_{i}\in X$ is
$\epsilon>0$ since $x,\widehat{x}\in X$ but $h,\widehat{h}\notin X$.
Similarly, the utility of every $u_{i}$ is at most $a_{i}$ in $\mathcal{P}$ as
$x$ and $\widehat{x}$ are contained in different parts by Section 4.1 $(\Pi
1)$ ($h$ and $\widehat{h}$ are in different part) while it is $2a_{i}$ in $X$
since $x,\widehat{x}\in X$. The utility of $x$ in $\mathcal{P}$ is
$9s+s_{A}-\delta+\sum_{a\in A^{\prime}}a$ which is equal to
$9.5s+s_{A}-\delta-\sum_{b\in B^{\prime}}b$. On the other hand, the utility of
$x$ is $9.5s+s_{A}-\sum_{b\in B^{\prime}}b>9.5s+s_{A}-\delta-\sum_{b\in
B^{\prime}}b$ in $X$. Finally, $\widehat{x}$ has utility at most
$10s-\delta+\sum_{a\notin A^{\prime}}a=10s-\delta+s_{A}-\sum_{a\in
A^{\prime}}a$ in $\mathcal{P}$. Furthermore, the utility of $\widehat{x}$ in
$X$ is $9.5s+s_{A}+\sum_{b\in B^{\prime}}(b+\epsilon)\geq 10s+s_{A}-\sum_{a\in
A^{\prime}}a$ by the assumption that $\sum_{c\in A^{\prime}\cup
B^{\prime}}c=s/2$. We conclude that $X$ is a blocking coalition which
contradicts the choice of $\mathcal{P}$.

###  4.3 Core stability parameterized by maximum degree and treewidth

We first prove the algorithmic result of the section.

######  Theorem 4.6.

Core Stability can be solved in time
$2^{2^{{O}(\Delta{\mathtt{tw}})}}n^{O(1)}$.

Before we prove Theorem 4.6, let us sketch our high-level strategy. Given an
instance of Core Stability, we want to produce an equivalent instance $\phi$
of $\exists\forall$-SAT, such that $\phi$ has treewidth roughly
$\Delta{\mathtt{tw}}$, where $\Delta,{\mathtt{tw}}$ are the maximum degree and
treewidth of the original instance. We could then use the known (double-
exponential) algorithm for $\exists\forall$-SAT ([Chen04]) to solve our
problem. Intuitively, we would then attempt to use the existential part of
$\phi$ to encode the “there exists a partition” part of the problem, and the
universal part to encode the “all blocking coalitions fail” part.

Fundamentally, this strategy is sound and works in a relatively
straightforward way for the universal part: we use a boolean variable for each
vertex (to encode whether it belongs in the blocking coalition) and to check
that a blocking coalition fails for a vertex $v$ we need to place a constraint
on $v$ and all its (at most $\Delta$) neighbors. This means that a tree
decomposition of $\phi$ should be constructible from a tree decomposition of
the square of the original graph, which would have width at most
$\Delta{\mathtt{tw}}$.

Where we run into some more difficulties, however, is in encoding the
existential part. Intuitively, this is because encoding the partition of the
vertices of a bag into coalitions requires a super-linear number of bits,
hence it is not sufficient to define a variable for each vertex. Indeed, to
simplify things, we define a variable for each _pair_ of vertices that appear
together in a bag, encoding whether they are together in a coalition. This
means that the treewidth of the formula $\phi$ we construct is in fact not
$O(\Delta{\mathtt{tw}})$ but actually can only be upper-bounded by
$O({\mathtt{tw}}^{2}+\Delta{\mathtt{tw}})$.

Nevertheless, we insist on obtaining an algorithm that is double-exponential
“only” in $\Delta{\mathtt{tw}}$, and not in ${\mathtt{tw}}^{2}$. In order to
circumvent our difficulty we observe that the term that is super-linear in
treewidth only depends on existentially quantified variables. Thankfully, we
manage to show, via an argument that is more careful than that of [Chen04],
that $\exists\forall$-SAT has a complexity that only needs to be double-
exponential in the number of _universally quantified_ variables of each bag
(Proposition 4.7). Using this, we are able to show that the second exponent of
the running time is “only” $O(\Delta{\mathtt{tw}})$, which as we show later is
optimal, even when $\Delta=O(1)$, under the ETH.

Let us now give some more details. We first recall that $\exists\forall$-SAT
is a variant of the SAT problem where we aim to decide the satisfiability of a
given quantified Boolean formula (QBF) $\phi$ which is of the form $\exists
x_{1}\dots\exists x_{k}\forall y_{1}\dots\forall y_{\ell}\psi$ where $\psi$ is
a DNF formula on variables $x_{1},\dots,x_{k},y_{1},\dots,y_{\ell}$. Two
common ways of associating structure of satisfiability problems is to consider
the primal or incidence graph of the formula. The primal graph of a formula
$\phi$ (in CNF or DNF) is a graph on the set of variables of $\phi$ where two
variables are adjacent if they appear in the same clause. Similarly, the
incidence graph is a bipartite graph on the set of variables and clauses of
$\phi$ where a variable is adjacent to all clauses it appears in. For
convenience, we use a variant of $\exists\forall$-SAT. We say that a QBF
$\phi$ is in $\exists 3\operatorname{CNF}\forall\operatorname{DNF}$ if $\phi$
can be written as

$\phi=\exists x_{1}\dots\exists x_{k}\bigwedge_{i=1}^{k^{\prime}}d_{i}\hskip
8.0pt\forall y_{1}\dots\forall y_{\ell}\bigvee_{i=1}^{\ell^{\prime}}c_{i}$

for some $k,k^{\prime},\ell,\ell^{\prime}\in\mathbb{N}$ where $d_{i}$ are
disjunctive clause over variables $x_{1},\dots,x_{k}$ containing at most $3$
literals per clause and $c_{i}$ are conjunctive clauses over variables
$x_{1},\dots,x_{k},y_{1},\dots,y_{\ell}$. We present an algorithm for $\exists
3\operatorname{CNF}\forall\operatorname{DNF}$ in several steps. First, we give
an algorithm with a more careful running time than that of [Chen04].

######  Proposition 4.7.

There is an algorithm that takes as input an instance of $\exists\forall$-SAT
$\exists x\forall y\phi(x,y)$, where $x,y$ are tuples of boolean variables,
$\phi$ is in 3-DNF, and a tree decomposition of the primal graph of $\phi$
where each bag contains at most $t_{\exists}$ existentially quantified
variables and at most $t_{\forall}$ universally quantified variables and
decides if the input is satisfiable in time
$2^{O(t_{\exists}+2^{t_{\forall}})}|\phi|^{O(1)}$.

######  Proof 4.8 (Proof).

Our strategy is to reduce the problem to CNF satisfiability, which can be
solved in time single-exponential in the primal treewidth. In particular, our
goal is to produce a CNF formula $\psi$ with treewidth
$O(t_{\exists}+2^{t_{\forall}})$, so that deciding if $\psi$ is satisfiable
will be equivalent to the original problem. Since CNF satisfiability on
instances with $n$ variables and primal treewidth $t$ can be solved in
$2^{O(t)}n^{O(1)}$, and since our reduction will run in time
$2^{O(t_{\exists}+t_{\forall})}|\phi|^{O(1)}$, we will obtain an algorithm
with the promised running time.

More precisely, starting from $\phi$, which is a formula in 3-DNF, we would
like to construct a CNF formula $\psi$, using the same existential variables
$x$, as well as some new existential variables $z$, so that the following
holds for each truth assignment to the variables $x$: there exists an
assignment to $z$ such that $\psi(x,z)$ is true if and only if for all
assignments to $y$ we have that $\phi(x,y)$ is true. In symbols: $\forall
x\left(\exists z\psi(x,z)\Leftrightarrow\forall y\phi(x,y)\right)$. It is not
hard to see that if we prove this equivalence for all assignments $x$, then
$\psi$ is satisfiable (i.e. $\exists x\exists z\psi(x,z)$) if and only if
$\exists x\forall y\phi(x,y)$ holds, so the problem reduces to deciding CNF
satisfiability for $\psi$.

The intuitive idea of the transformation of $\phi$ to $\psi$ is that we want
to encode in a CNF formula the execution of an algorithm which, having fixed
the assignment to $x$, decides if there exists an assignment to $y$ to make
$\phi(x,y)$ false. This algorithm would work using the standard DP methodology
for treewidth, meaning it would store in each bag, for each assignment to the
variables of $y$ contained in this bag, a bit of information indicating
whether this assignment can be extended in a way that renders the formula we
have seen so far false.

More precisely, the transformation is the following: for each bag $B$ of the
tree decomposition of the primal graph of $\phi$, for each assignment $\sigma$
to the (at most $t_{\forall}$) universal variables of $B$, we construct two
new variables $z_{B,\sigma}$ and $w_{B,\sigma}$. In order to explain the
intended meaning of these variables, fix an assignment to $x$. Then,
$z_{B,\sigma}$ is meant to be set to true if and only if there is an
assignment to the $y$ variables contained in the sub-tree rooted at $B$,
consistent with $\sigma$, such that every conjunctive clause of $\phi$
contained in this sub-tree is made false by the joint assignment to $x$ and
$y$. Furthermore, $w_{B,\sigma}$ is meant to be true if all conjunctive
clauses of $\phi$ whose variables are fully contained in $B$ are set to false
by the joint assignment to $x$ and the assignment $\sigma$.

Let us now describe the clauses of $\psi$. Assume, to simplify things, that we
are given a nice tree decomposition of the primal graph of $\phi$, such that
the leaves and the root of the decomposition are empty bags. We construct the
following clauses:

  1. 1.

For each bag $B$, each assignment $\sigma_{1}$ to the existential variables of
$B$, and each assignment $\sigma_{2}$ to the universal variables of $B$, we
check if there exists a clause of $\phi$ which is fully contained in $B$ and
which is set to true by the joint assignments $\sigma_{1},\sigma_{2}$. If this
is the case, we add to $\psi$ a clause which is falsified exactly when the
existential variables of $B$ take assignment $\sigma_{1}$, and add to this
clause the literal $\neg w_{B,\sigma_{2}}$. If this is not the case (that is,
all clauses contained in $B$ are set to false by the joint assignment) we add
to $\psi$ a clause falsified when the existential variables take assignment
$\sigma_{1}$, and add to this clause the literal $w_{B,\sigma_{2}}$.

  2. 2.

For each leaf bag $B$, since $B$ is empty, there exists a unique (vacuous)
assignment $\sigma_{\emptyset}$ to its universal variables. We add to $\psi$
the unit clause $(z_{B,\sigma_{\emptyset}})$.

  3. 3.

For each bag $B$ with a single child $B^{\prime}$, for each assignment
$\sigma$ to the universal variables of $B$, if there is a unique assignment
$\sigma^{\prime}$ to the universal variables of $B^{\prime}$, such that
$\sigma,\sigma^{\prime}$ agree on their common variables (this happens if the
universal variables of $B^{\prime}$ are all contained in $B$), we add to
$\psi$ clauses that implement the constraint
$z_{B,\sigma}\leftrightarrow(w_{B,\sigma}\land
z_{B^{\prime},\sigma^{\prime}})$. Otherwise, since the decomposition is nice,
$B^{\prime}$ contains a single universal variable not appearing in $B$ and
there are two assignments $\sigma^{\prime},\sigma^{\prime\prime}$ to universal
variables of $B^{\prime}$ consistent with $\sigma$. We then add to $\psi$
clauses implementing the constraint
$z_{B,\sigma}\leftrightarrow(w_{B,\sigma}\land(z_{B^{\prime},\sigma^{\prime}}\lor
z_{B^{\prime},\sigma^{\prime\prime}}))$.

  4. 4.

Similarly, for each join bag $B$, with children $B^{\prime},B^{\prime\prime}$,
for each assignment $\sigma$ to the universal variables of $B$, we add to
$\psi$ clauses that implement the constraint
$z_{B,\sigma}\leftrightarrow(w_{B,\sigma}\land z_{B^{\prime},\sigma}\land
z_{B^{\prime\prime},\sigma})$.

  5. 5.

In the root bag $B_{r}$, since $B_{r}$ is empty, again there exists a unique
vacuous assignment $\sigma_{\emptyset}$. We add to $\psi$ the unit clause
$(\neg z_{B,\sigma_{\emptyset}})$.

This completes the construction. The intuition behind the construction is
that, if we fix the assignment to the $x$ variables, then in order to satisfy
$\psi$, for each $B,\sigma$, the variable $w_{B,\sigma}$ must correctly encode
whether $B$ contains a clause that is set to true by the assignment to the $x$
variables in conjunction with $\sigma$ (in particular, $w_{B,\sigma}$ is true
if and only if all clauses contained in $B$ are false). The variable
$z_{B,\sigma}$ is meant to check if there exists some assignment to the $y$
variables extending $\sigma$ that makes all clauses of $\phi$ contained in the
sub-tree rooted at $y$ false; this is vacuously true for a leaf bag (as no
clauses are contained in the sub-tree); in other bags this is true if and only
if all clauses contained in $B$ are false (encoded by $w_{B,\sigma}$) and an
assignment consistent with $\sigma$ sets all clauses contained in the sub-
trees rooted at children of $B$ to false. Finally, the given assignment to $x$
has the property that $\forall y.\phi(x,y)$ if and only if in the root it is
not possible to find an assignment to the $y$ variables that makes all clauses
false, hence the last clause of $\psi$. Correctness of the construction can be
argued by induction using the above intuition in a standard way, so we skip
the details.

The construction above can be executed in time
$2^{t_{\exists}+t_{\forall}}|\phi|^{O(1)}$. In order to construct a tree
decomposition of $\psi$ we keep the decomposition of $\phi$ and remove all
universal variables. Then, in each bag $B$ we place all the at most $2\cdot
2^{t_{\forall}}$ variables $z_{B,\sigma},w_{B,\sigma}$ constructed for this
bag. We then add to each bag $B$ all the variables contained in one of its
children. Since the decomposition is nice, so each node has at most two
children, this will at most triple the size of each bag, making all bags
contain at most $3t_{\exists}+6\cdot 2^{t_{\forall}}$ variables. Observe that
now all clauses of $\psi$ are fully contained in some bag. We now have a CNF
formula $\psi$ and a tree decomposition of its primal graph of width
$O(t_{\exists}+2^{t_{\forall}})$ such that deciding if $\psi$ is satisfiable
resolves our original problem. Using a standard DP algorithm now completes the
proof.

######  Proposition 4.9.

There is an algorithm that takes as input an $\exists
3\operatorname{CNF}\forall\operatorname{DNF}$-SAT instance $\phi$ and a tree
decomposition of its incidence graph of width $t$ that contains at most
$t_{\forall}$ universally quantified variables in each bag and at most $2$
clauses in each bag, and decides $\phi$ in time
$2^{O(t2^{t_{\forall}})}|\phi|$.

######  Proof 4.10 (Proof).

We reduce $\exists 3\operatorname{CNF}\forall\operatorname{DNF}$-SAT to
$\exists\forall$-SAT and then use Proposition 4.7. Let $\phi$ be a formula in
$\exists 3\operatorname{CNF}\forall\operatorname{DNF}$. Hence, $\phi$ can be
written as $\phi=\exists x_{1}\dots\exists
x_{k}\bigwedge_{i=1}^{k^{\prime}}d_{i}\hskip 8.0pt\forall y_{1}\dots\forall
y_{\ell}\bigvee_{i=1}^{\ell^{\prime}}c_{i}$ for some
$k,k^{\prime},\ell,\ell^{\prime}\in\mathbb{N}$ where $d_{i}$ are disjunctive
clauses containing at most $3$ literals and $c_{i}$ are conjunctive clauses.
We construct an instance $\psi$ of $\exists\forall$-SAT as follows. The
formula $\psi$ contains existentially quantified variable $x_{1},\dots,x_{k}$
and universally quantified variables
$y_{1},\dots,y_{\ell},y_{d_{1}},\dots,y_{d_{k^{\prime}}},y_{C}$. Furthermore,
$\psi$ contains one clause $(y_{d_{i}},\lambda)$ for every $i\in[k^{\prime}]$
and every literal $\lambda$ contained in the clause $d_{i}$. Additionally,
$\psi$ contains the clause $y_{C}\land c_{i}$ for every $i\in[\ell^{\prime}]$.
Finally, $\psi$ contains the clause $(\lnot y_{d_{1}}\land\dots\land\lnot
y_{d_{k^{\prime}}}\land\lnot y_{C})$. We now argue that $\phi$ is satisfiable
if and only if $\psi$ is satisfiable.

First assume that $\phi$ is satisfiable and let
$\alpha_{X}:\\{x_{1},\dots,x_{k}\\}\rightarrow\\{0,1\\}$ be an assignment
which satisfies $\bigvee_{i=1}^{k^{\prime}}d_{i}$ and for every assignment
$\alpha_{Y}:\\{y_{1},\dots,y_{\ell}\\}\rightarrow\\{0,1\\}$ the formula
$\bigwedge_{i=1}^{\ell^{\prime}}c_{i}$ is satisfied. Let
$\alpha_{Y}:\\{y_{1},\dots,y_{\ell},y_{d_{1}},\dots,y_{d_{k^{\prime}}},y_{C}\\}\rightarrow\\{0,1\\}$
be any assignment.

First assume that $\alpha_{Y}(y_{d_{i}})=1$ for some $i\in[k^{\prime}]$. Since
the disjunctive clause $d_{i}$ is satisfied under the assignment $\alpha_{X}$
by assumption, there is a literal $\lambda$ contained in $d_{i}$ such that
$\lambda$ evaluates to $1$ under assignment $\alpha_{X}$. Hence, the clause
$(y_{d_{i}},\lambda)$ is satisfied under the assignments $\alpha_{X}$ and
$\alpha_{Y}$.

Now assume that $\alpha_{Y}(y_{d_{i}})=0$ for every $i\in[k^{\prime}]$ and
$\alpha_{Y}(y_{C})=0$. In this case the clause $(\lnot
y_{d_{1}}\land\dots\land\lnot y_{d_{k^{\prime}}}\land\lnot y_{C})$ is
satisfied under the assignments $\alpha_{X}$ and $\alpha_{Y}$.

Finally, assume that $\alpha_{Y}(y_{d_{i}})=0$ for every $i\in[k^{\prime}]$
and $\alpha_{Y}(y_{C})=1$. Observe that by assumption
$\bigwedge_{i=1}^{\ell^{\prime}}c_{i}$ is satisfied under assignments
$\alpha_{X}$ and the restriction of $\alpha_{Y}$ to the set
$\\{y_{1},\dots,y_{\ell}\\}$. Let $i\in[\ell^{\prime}]$ be the index of the
satisfied clause. In this case, the clause $y_{C}\land c_{i}$ must be
satisfied under the assignment $\alpha_{X}$ and $\alpha_{Y}$. Hence, we have
argued that $\psi$ is satisfiable.

On the other hand, assume that $\psi$ is satisfiable and let
$\alpha:\\{x_{1},\dots,x_{k}\\}\rightarrow\\{0,1\\}$ is an assignment such
that for every assignment
$\alpha_{Y}:\\{y_{1},\dots,y_{\ell},y_{d_{1}},\dots,y_{d_{k^{\prime}}},y_{C}\\}\rightarrow\\{0,1\\}$
either one of clauses $(y_{d_{i}},\lambda)$, $i\in[k^{\prime}]$ and $\lambda$
a literal contained in $d_{i}$ or one of the clauses $y_{C}\land c_{i}$,
$i\in[\ell^{\prime}]$ or the clause $(\lnot y_{d_{1}}\land\dots\land\lnot
y_{d_{k^{\prime}}}\land\lnot y_{C})$ is satisfied under assignment
$\alpha_{X}$ and $\alpha_{Y}$. To argue that $\psi$ is satisfiable, let
$\alpha_{Y}:\\{y_{1},\dots,y_{\ell}\\}\rightarrow\\{0,1\\}$ be any assignment.
We have to argue that every clause $d_{i}$, $i\in[k^{\prime}]$ is satisfied
and at least one clause $d_{i}$, $i\in[\ell^{\prime}]$ is satisfied.

Fix some $i\in[k^{\prime}]$ and define an assignment
$\tilde{\alpha}_{Y}:\\{y_{1},\dots,y_{\ell},y_{d_{1}},\dots,y_{d_{k^{\prime}}},y_{C}\\}\rightarrow\\{0,1\\}$
by $\tilde{\alpha}(y_{j})=\alpha_{Y}(y_{j})$ for $j\in[\ell]$,
$\tilde{\alpha}_{Y}(y_{d_{i}})=1$, $\tilde{\alpha}_{Y}(y_{d_{j}})=0$ for
$j\in[k^{\prime}]$, $j\not=i$ and $\tilde{\alpha}_{Y}(y_{C})=0$. By
construction, the only clauses of $\psi$ that can be satisfied under
assignments $\alpha_{X}$ and $\tilde{\alpha}_{Y}$ are the clauses
$(d_{i}\land\lambda)$ for every literal $\lambda$ in $d_{i}$. Hence, one
literal of $d_{i}$ evaluates to $1$ under assignment $\alpha_{X}$ and
therefore $d_{i}$ is satisfied under assignment $\alpha_{X}$.

Now consider the assignment
$\tilde{\alpha}_{Y}:\\{y_{1},\dots,y_{\ell},y_{d_{1}},\dots,y_{d_{k^{\prime}}},y_{C}\\}\rightarrow\\{0,1\\}$
where $\tilde{\alpha}(y_{j})=\alpha_{Y}(y_{j})$ for $j\in[\ell]$,
$\tilde{\alpha}_{Y}(y_{d_{j}})=0$ for every $j\in[k^{\prime}]$ and
$\tilde{\alpha}_{Y}(y_{C})=1$. Hence, the only clauses of $\psi$ that can be
satisfied under assignments $\alpha_{X}$ and $\tilde{\alpha}_{Y}$ are the
clauses $(y_{C}\land c_{i})$, $i\in[\ell^{\prime}]$. Let $i\in[\ell^{\prime}]$
be the index for which $(y_{C}\land c_{i})$ is satisfied. But in this case the
clause $c_{i}$ is satisfied concluding the argument that $\phi$ is
satisfiable.

We now consider the incidence graph of $\psi$ and construct a tree
decomposition of that graph starting from a decomposition of the incidence
graph of $\phi$. First, we maintain all common variables, and for each
conjunctive clause $c$ in a bag, we replace it with the clause $(y_{C}\land
c)$ which has replaced it in $\psi$; we add $y_{C}$ and the clause $(\neg
y_{d_{1}}\land\ldots\land y_{d_{k^{\prime}}\land\neg y_{C}})$ to all bags; for
each disjunctive clause $d$ appearing in a bag we add the three new clauses
$(y_{d}\land\lambda)$, where $\lambda$ is a literal of $d$, to the bag.
Observe that we have a valid decomposition of the new incidence graph, with
width $t^{\prime}=O(t)$, such that each bag contains at most $7$ clauses, and
at most $t_{\forall}+1$ universal variables.

We are now almost done, except that we need to obtain a decomposition of the
primal graph of $\psi$ to invoke Proposition 4.7 and also to convert $\psi$
into 3-DNF. This, however, can be done using an algorithm of [LampisMM18]. In
particular, we convert $\psi$ to 3-DNF in the standard way: as long as there
exists a clause that contains at least $4$ literals, say
$(\lambda_{1}\land\lambda_{2}\land\ldots\land\lambda_{r})$, we introduce a new
universally quantified variable $z$ and replace it with the two clauses
$(\lambda_{1}\land\lambda_{2}\land z)$ and $(\neg
z\land\lambda_{3}\land\ldots\land\lambda_{r})$. The difference, however, is
that we select the two literals to place in the new clause in a way that keeps
the treewidth of the new formula under control. In particular, we find the
lowest bag $B$ in the decomposition that contains the current clause such that
the sub-tree rooted at $B$ contains two variables of the clause and set
$\lambda_{1},\lambda_{2}$ to be the literals involving these two variables. It
is now not hard to see that if we execute this exhaustively, the new
decomposition we construct will have $O(1)$ clauses per bag,
$t_{\forall}+O(1)$ universally quantified variables, and width $O(t)$. Now,
replace each clause in the decomposition by the (at most $3$) variables it
contains, and we get a decomposition of the primal graph, on which we can
invoke Proposition 4.7.

######  Proof 4.11 (Proof of Theorem 4.6).

We prove Theorem 4.6 by a reduction to $\exists
3\operatorname{CNF}\forall\operatorname{DNF}$-SAT. Let $(G,w)$ be an instance
of CS and $(T,\beta)$ be a rooted tree decomposition of $G$. Here, we denote
the bag of a node $t\in T$ by $\beta(t)$. First we let
$(G^{\prime},w^{\prime})$ be the graph obtained from $(G,w)$ by adding edges
$uv$ of weight $0$ for every pair of vertices $u,v$ appearing in a bag
together. It is straightforward to see that $(G,w)$ is a YES-instance of CS if
and only if $(G^{\prime},w^{\prime})$ is a YES-instance of CS. Additionally,
$G^{\prime}$ is chordal and $(T,\beta)$ is a tree decomposition of
$G^{\prime}$.

We construct an instance $\phi$ of $\exists
3\operatorname{CNF}\forall\operatorname{DNF}$-SAT. We introduce a variable
$x_{e}$ for every $e\in E(G^{\prime})$ and a variable $y_{u}$ for every vertex
$u\in V(G^{\prime})$. An assignment $\alpha_{X}:\\{x_{e}:e\in
E(G^{\prime})\\}\rightarrow\\{0,1\\}$ represents a subset of $E(G^{\prime})$
and an assignment $\alpha_{Y}:\\{y_{u}:u\in
V(G^{\prime})\\}\rightarrow\\{0,1\\}$ represents a subset of $V(G^{\prime})$.
Intuitively, a partition of $V(G^{\prime})$ corresponds to a set of edges,
i.e. by including all edges that are incident to vertices from the same part.
For every $t\in V(T)$ we define a formula $\phi_{t}$, which we use to enforce
sufficient criteria for the set of edges represented by an assignment
$\alpha_{X}:\\{x_{e}:e\in E(G^{\prime})\\}\rightarrow\\{0,1\\}$ to correspond
to a partition of $V(G^{\prime})$. Let

$\displaystyle\phi_{t}=$
$\displaystyle\bigwedge_{u_{1},u_{2},u_{3}\in\beta(t)}\big{(}x_{u_{1}u_{2}}\land
x_{u_{2}u_{3}}\big{)}\rightarrow
x_{u_{1}u_{3}}=\bigwedge_{u_{1},u_{2},u_{3}\in\beta(t)}\Big{(}\lnot
x_{u_{1}u_{2}}\lor\lnot x_{u_{2}u_{3}}\lor x_{u_{1}u_{3}}\Big{)}.$

For a fixed partition $\mathcal{P}$ represented by some assignment
$\alpha_{X}:\\{x_{e}:e\in E(G^{\prime})\\}\rightarrow\\{0,1\\}$ our formula
needs to ensure that no blocking coalitions exist. This is realized by
guaranteeing that for each assignment $\alpha_{Y}:\\{y_{u}:u\in
V(G^{\prime})\\}\rightarrow\\{0,1\\}$ the set corresponding to $\alpha_{Y}$ is
not blocking. Intuitively, the formula $\phi_{u}$ defined below ensures that
the utility of vertex $u$ in $\mathcal{P}$ is at least as large as the utility
of $u$ in the coalition represented by $\alpha_{Y}$. For $u\in V(G^{\prime})$
let

$\phi_{u}=\bigvee_{N,\tilde{N}\subseteq N_{G^{\prime}}(u),\atop{\sum_{v\in
N}w(uv)\leq\sum_{v\in\tilde{N}}w(uv)}}\bigg{(}\bigwedge_{v\in
N}y_{v}\land\bigwedge_{v\in N_{G^{\prime}}(u)\setminus N}\lnot
y_{v}\land\bigwedge_{v\in\tilde{N}}x_{uv}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus\tilde{N}}\lnot x_{uv}\bigg{)}.$

We now define the formula $\phi$ to be

$\phi=\exists x_{e_{1}}\dots\exists x_{e_{m}}\bigwedge_{t\in
V(T)}\phi_{t}\hskip 10.0pt\forall y_{v_{1}}\dots\forall y_{v_{n}}\big{(}\lnot
y_{1}\land\dots\land\lnot y_{n}\big{)}\lor\bigvee_{u\in
V(G^{\prime})}\phi_{u}.$

Observe that $\phi$ is in $\exists
3\operatorname{CNF}\forall\operatorname{DNF}$. In the following we prove that
$(G^{\prime},w^{\prime})$ is a YES-instance of CS if and only if $\phi$ is
satisfiable.

First assume that $\mathcal{P}$ is a core stable partition of $V(G^{\prime})$.
We define an assignment $\alpha_{X}:\\{x_{e}:e\in
E(G^{\prime})\\}\rightarrow\\{0,1\\}$ by setting $\alpha_{X}(x_{e})=1$ if $e$
is incident to two vertices residing in the same part of $\mathcal{P}$ and
$\alpha_{X}(x_{e})=0$ otherwise. This assignment satisfies $\phi_{t}$ for
every $t\in V(T)$ as for any three vertices $u_{1},u_{2},u_{3}\in\beta(t)$ it
holds that if $\alpha_{X}(x_{u_{1}u_{2}})=1$ and
$\alpha_{X}(x_{u_{2}u_{3}})=1$, then $u_{1},u_{2}$ and $u_{3}$ must reside in
the same part of $\mathcal{P}$ and hence $\alpha_{X}(x_{u_{1}u_{3}})=1$.
Furthermore, consider any assignment $\alpha_{Y}:\\{y_{u}:u\in
V(G^{\prime})\\}\rightarrow\\{0,1\\}$ and let $X=\\{u\in
V(G^{\prime}):\alpha_{Y}(y_{u})=1\\}$. We have to argue that the formula
$\big{(}\lnot y_{1}\land\dots\land\lnot y_{n}\big{)}\lor\bigvee_{u\in
V(G^{\prime})}\phi_{u}$ is satisfied under the assignments $\alpha_{X}$ and
$\alpha_{Y}$. In case that $X=\emptyset$, the clause $\big{(}\lnot
y_{1}\land\dots\land\lnot y_{n}\big{)}$ is satisfied. On the other hand, if
$X\not=\emptyset$, then there must be a vertex $u\in X$ whose utility in
$\mathcal{P}$ is at least as large as its utility in $X$ as the set $X$ cannot
be a blocking coalition. Hence, for the sets $N=N_{G^{\prime}}(u)\cap X$ and
$\tilde{N}=N_{G^{\prime}}(u)\cap P$, where $P\in\mathcal{P}$ is the part
containing $u$, we have that $\sum_{v\in
N}w(uv)\leq\sum_{v\in\tilde{N}}w(uv)$. Therefore, $\phi_{u}$ contains the
clause $\big{(}\bigwedge_{v\in N}y_{v}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus N}\lnot
y_{v}\land\bigwedge_{v\in\tilde{N}}x_{uv}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus\tilde{N}}\lnot x_{uv}\big{)}$ and this clause is
satisfied under the assignment $\alpha_{X}$ and $\alpha_{Y}$ by choice of $N$
and $\tilde{N}$. This shows that $\phi$ is satisfiable.

On the other hand, assume that $\phi$ is satisfiable and let
$\alpha_{X}:\\{x_{e}:e\in E(G^{\prime})\\}\rightarrow\\{0,1\\}$ be an
assignment such that $\bigwedge_{t\in V(T)}\phi_{t}$ as well as $\forall
y_{v_{1}}\dots\forall y_{v_{n}}\big{(}\lnot y_{1}\land\dots\land\lnot
y_{n}\big{)}\lor\bigvee_{u\in V(G^{\prime})}\phi_{u}$ is satisfied under
$\alpha_{X}$. We let $E_{X}=\\{e\in E(G^{\prime}):\alpha_{X}(x_{e})=1\\}$ and
define a partition $\mathcal{P}$ by letting every part of $\mathcal{P}$
correspond to the vertices of a connected component of the graph
$(V(G^{\prime}),E_{X})$. To show that the partition $\mathcal{P}$ is core
stable we use the following claim.

######  Claim 1.

For every edge $uv\in E(G^{\prime})$ it holds that $uv\in E_{X}$ if and only
if $u$ and $v$ are contained in the same part of $\mathcal{P}$.

######  Proof 4.12 (Proof).

Since the forward direction holds by definition of $\mathcal{P}$, assume
towards a contradiction that $uv\in E(G^{\prime})$ with $u$ and $v$ being
contained in the same part of $\mathcal{P}$ but $uv\notin E_{X}$. By
definition of $\mathcal{P}$, $u$ and $v$ being contained in the same part
implies that there is a path from $u$ to $v$ in the graph
$(V(G^{\prime}),E_{X})$. Let $Q=(q_{1},\dots,q_{\ell})$ be a shortest such
path. We aim to find an inconsistent triangle, i.e. three vertices
$v_{1},v_{2},v_{3}$ such that $v_{1}v_{2},v_{2}v_{3}\in E_{X}$ but
$v_{1}v_{3}\notin E_{X}$. Assume that $k\leq 2$ is the minimum number such
that there is an index $i\in[\ell-k]$ for which $q_{i}q_{i+k}\in
E(G^{\prime})$. As $G^{\prime}$ is chordal, we picked $k$ minimum $k=2$.
Furthermore, $q_{i}q_{i+2}\notin E_{X}$ as otherwise, the path
$(q_{1},\dots,q_{i},q_{i+2},\dots q_{\ell})$ is a path in
$(V(G^{\prime}),E_{X})$ from $u$ to $v$ which is shorter than $Q$. Hence,
$q_{i},q_{i+1},q_{i+2}$ forms an inconsistent triangle. We now claim that
there is a node $t\in V(T)$ such that $q_{i},q_{i+1},q_{i+2}\in\beta(t)$. As
$q_{i}q_{i+1},q_{i+1}q_{i+2},q_{i}q_{i+2}\in E(G^{\prime})$ we know that there
are nodes $t_{1},t_{2},t_{3}\in V(T)$ such that
$\\{q_{i},q_{i+1}\\}\subseteq\beta(b_{1}),\\{q_{i+1},q_{i+2}\\}\subseteq\beta(t_{2})$
and $\\{q_{i},q_{i+2}\\}\subseteq\beta(t_{3})$. Let $t$ be the lowest common
ancestor of $t_{1},t_{2}$ and $t_{3}$ in $T$. As the nodes of $T$ containing a
particular vertex of $G^{\prime}$ in their bags form a subtree of $T$, we
directly obtain that $q_{i},q_{i+1},q_{i+2}\in\beta(t)$. Hence,
$\big{(}x_{q_{i}q_{i+1}}\land x_{q_{i+1}q_{i+2}}\big{)}\rightarrow
x_{q_{i}q_{i+3}}\big{)}$ is a clause in $\bigwedge_{t\in V(T)}\phi_{t}$.
Hence, $\big{(}x_{q_{i}q_{i+1}}\land x_{q_{i+1}q_{i+2}}\big{)}\rightarrow
x_{q_{i}q_{i+2}}\big{)}$ must be satisfied under the assignment $\alpha_{X}$
which contradicts $q_{i}q_{i+2}$ not being contained in $E_{X}$ proving the
claim.

Towards a contradiction assume that $\mathcal{P}$ is not core stable and let
$X$ be a blocking coalition. We define an assignment $\alpha_{Y}:\\{y_{u}:u\in
V(G^{\prime})\\}\rightarrow\\{0,1\\}$ by setting $\alpha_{Y}(y_{u})=1$ if
$u\in X$ and $\alpha_{Y}(y_{u})=0$ otherwise. By assumption, the DNF formula
$\big{(}\lnot y_{1}\land\dots\land\lnot y_{n}\big{)}\lor\bigvee_{u\in
V(G^{\prime})}\phi_{u}$ is satisfied under assignment $\alpha_{X}$ and
$\alpha_{Y}$. As $X$ cannot be empty there is at least one $u\in
V(G^{\prime})$ such that $\alpha_{Y}(y_{u})=1$ and hence the clause
$\big{(}\lnot y_{1}\land\dots\land\lnot y_{n}\big{)}$ cannot be satisfied
under the assignment $\alpha_{Y}$ which implies that some clause in
$\bigvee_{u\in V(G^{\prime})}\phi_{u}$ must be satisfied. Let $u\in
V(G^{\prime})$ and $N,\tilde{N}\subseteq N_{G^{\prime}}(u)$ with $\sum_{v\in
N}w(uv)\leq\sum_{v\in\tilde{N}}w(uv)$ such that the clause
$\big{(}\bigwedge_{v\in N}y_{v}\land\bigwedge_{v\in N_{G^{\prime}}(u)\setminus
N}\lnot y_{v}\land\bigwedge_{v\in\tilde{N}}x_{uv}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus\tilde{N}}\lnot x_{uv}\big{)}$ is satisfied under
assignments $\alpha_{X}$ and $\alpha_{Y}$. This implies that
$N=N_{G^{\prime}}(u)\cap X$ and $\tilde{N}=\\{v\in V(G^{\prime}):uv\in
E_{X}\\}$. Since by Claim 1, $\\{v\in V(G^{\prime}):uv\in
E_{X}\\}=N_{G^{\prime}}(u)\cap P$, where $P$ is the part of $\mathcal{P}$
containing $u$, this implies that the utility of $u$ in $X$ is less or equal
to the utility of $u$ in $\mathcal{P}$. As this contradict our assumption that
$X$ is a blocking coalition it follows that $\mathcal{P}$ is core stable.

######  Claim 2.

The formula $\phi$ has incidence treewidth at most
$\Delta(G^{\prime}){\mathtt{tw}}(G^{\prime})+{\mathtt{tw}}(G^{\prime})^{2}+2$.
Furthermore, we can construct a decomposition of that width which contains at
most $2$ clauses per bag and at most
$(\Delta(G^{\prime})+1){\mathtt{tw}}(G^{\prime})$ universally quantified
variables per bag.

######  Proof 4.13 (Proof).

Let $G^{\phi}$ be the incidence graph of $\phi$. For $t\in V(T)$ we denote the
subtree of $T$ rooted at $t$ by $T_{t}$. For every $u\in V(G^{\prime})$ we let
$\operatorname{lca}(u)$ be the node $t$ such that $u\in\beta(t)$ and $T_{t}$
contains every node $t^{\prime}\in V(T)$ for which $u\in\beta(t^{\prime})$. In
other words $\operatorname{lca}(u)$ is the lowest common ancestor of all nodes
whose bag contain $u$. We now construct a tree decomposition
$(T^{\phi},\beta^{\phi})$ of $G^{\phi}$. We obtain $T_{\phi}$ from $T$ by the
following steps.

  1. 1.

For every $t\in V(T)$ and every triple $(u_{1},u_{2},u_{3})\in\beta(t)^{3}$ we
introduce a new node $t_{(u_{1},u_{2},u_{3})}$.

  2. 2.

For every vertex $u\in V(G)$ and every two sets $N,\tilde{N}\subseteq
N_{G^{\prime}}(u)$ for which $\sum_{v\in N}w(uv)\leq\sum_{v\in\tilde{N}}w(uv)$
we introduce a node $\operatorname{lca}(u)_{(N,\tilde{N})}$.

  3. 3.

For the root $r$ of $T$ we attach a path to $r$ containing all nodes
$r_{(u_{1},u_{2},u_{3})}$ and all nodes $t_{(N,\tilde{N})}$ in an arbitrary
order.

  4. 4.

For every node $t\in V(T)$ apart from the root $r$, we subdivide the edge from
$t$ to its ancestor by the nodes $t_{(u_{1},u_{2},u_{3})}$ and the nodes
$t_{(N,\tilde{N})}$.

We define $\beta^{\phi}$ in the following way. We set
$\beta^{\phi}(t)=\\{y_{u}:u\in
N_{G^{\prime}}(\beta(t))\cup\beta(t)\\}\cup\\{x_{uv}:u,v\in\beta(t)\\}\cup\\{c_{\lnot}\\}$
for every node $t\in V(T)$ where $c_{\lnot}$ is the clause $(\lnot
y_{1}\land\dots\land\lnot y_{n})$. Further, we set
$\beta^{\phi}(t_{(u_{1},u_{2},u_{3})})=\\{c_{(u_{1},u_{2},u_{3})}\\}\cup\beta^{\phi}(t)$
where $c_{(u_{1},u_{2},u_{3})}$ is the clause $(\lnot x_{u_{1}u_{2}}\lor\lnot
x_{u_{2}u_{3}}\lor x_{u_{1}u_{3}})$. Similarly, we set
$\beta^{\phi}(t_{(N,\tilde{N})})=\\{c_{(N,\tilde{N})}\\}\cup\beta^{\phi}(t)$
where $c_{(N,\tilde{N})}$ is the clause $(\bigwedge_{v\in
N}y_{v}\land\bigwedge_{v\in N_{G^{\prime}}(u)\setminus N}\lnot
y_{v}\land\bigwedge_{v\in\tilde{N}}x_{uv}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus\tilde{N}}\lnot x_{uv})$.

We now argue that the pair $(T^{\phi},\beta^{\phi})$ is a tree decomposition
of $G^{\phi}$. First observe that that every vertex of $G^{\phi}$ is contained
in the bag of some node of $T^{\phi}$. Next we argue that the two vertices
incident to any edge appear in a bag together in $(T^{\phi},\beta^{\phi})$.
Observe that any edge incident to the clause $(\lnot y_{1}\land\dots\land\lnot
y_{n})$ must be contained in some bag as $(\lnot y_{1}\land\dots\land\lnot
y_{n})$ is contained in every bag. Furthermore, any bag
$\beta^{\phi}(t_{(u_{1},u_{2},u_{3})}$ contains both
$y_{u_{1}},y_{u_{2}},y_{u_{3}}$ and $(\lnot x_{u_{1}u_{2}}\lor\lnot
x_{u_{2}u_{3}}\lor x_{u_{1}u_{3}})$ and hence every edge incident to $(\lnot
x_{u_{1}u_{2}}\lor\lnot x_{u_{2}u_{3}}\lor x_{u_{1}u_{3}})$ is contained in
some bag. Lastly, any bag $\beta(\operatorname{lca}(u)_{N,\tilde{N}})$
contains $y_{u}$, $y_{v}$ for every neighbor $v\in N_{G^{\prime}}(u)$ and the
clause $(\bigwedge_{v\in N}y_{v}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus N}\lnot
y_{v}\land\bigwedge_{v\in\tilde{N}}x_{uv}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus\tilde{N}}\lnot x_{uv})$ which implies that every
edge incident to $(\bigwedge_{v\in N}y_{v}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus N}\lnot
y_{v}\land\bigwedge_{v\in\tilde{N}}x_{uv}\land\bigwedge_{v\in
N_{G^{\prime}}(u)\setminus\tilde{N}}\lnot x_{uv})$ is contained in some bag.

Finally, we argue that the subtree induced by nodes containing a fixed vertex
$v$ in their bag, is connected for every vertex $v\in V(G^{\phi})$. First note
that for any clause $c$ of $\phi$ the set $\\{t\in
V(T^{\phi}):c\in\beta(t)\\}$ trivially induces a subtree of $T$ as any clause
is either contained in the bags of all nodes of $T^{\phi}$ or in the bag of
only one node.

Next, fix $e=uv\in E(G^{\prime})$ and consider the set $S_{e}=\\{t\in
V(T^{\phi}):x_{e}\in\beta^{\phi}(t)\\}$. Observe, that for any node $t\in
V(T)$ by construction $t\in S_{e}$ if and only if $u,v\in\beta(t)$. Hence, the
set $S_{e}\cap V(T)$ induces a subtree on $T$ as it is the intersection of two
sets $\\{t\in V(T):u\in\beta(t)\\}$ and $\\{t\in V(T):v\in\beta(t)\\}$ which
induce a subtree on $T$. As the graph induced by $S_{e}$ on $T$ can be
obtained from the subtree of $T$ induced by $S_{e}\cap V(T)$ by subdividing
every edge and attaching a path at the root, we obtain that $S_{e}$ must
induce a tree.

Finally, fix $u\in V(G)$ and consider the set $S_{u}=\\{t\in
V(T):y_{u}\in\beta^{\phi}(t)\\}$. By construction, a node $t\in V(T)$ is
contained in $S_{u}$ if and only if either $u$ or some neighbor $v\in
N_{G^{\prime}}(u)$ is contained in $\beta(t)$. Hence, the graph induces by
$S_{u}\cap V(T)$ is the union of the trees $G^{\prime}[\\{t\in
V(T):v\in\beta(t)\\}]$ for all neighbors $v\in N_{G^{\prime}}(u)\cup\\{u\\}$.
As $\\{t\in V(T):v\in\beta(t)\\}$ must intersect the set $\\{t\in
V(T):u\in\beta(t)\\}$ (as $(T,\beta)$ is a tree decomposition of $G^{\prime}$
and $uv\in E(G^{\prime})$) the graph induced by $S_{u}\cap V(T)$ on $T$ is a
subtree of $T$. Similarly to the previous case, this implies that $S_{u}$
induces a subtree of $T^{\phi}$.

To argue about the width of $(T^{\phi},\beta^{\phi})$ first observe that every
bag contains at most two clauses. Excluding clauses, every bag of
$(T^{\phi},\beta^{\phi})$ consists of the set $\\{y_{u}:u\in
N_{G^{\prime}}(\beta(t))\cup\beta(t)\\}$ of size
$\Delta(G^{\prime}){\mathtt{tw}}(G^{\prime})+{\mathtt{tw}}(G^{\prime})$ and
$\\{x_{uv}:u,v\in\beta(t)\\}$ of size
${\mathtt{tw}}(G^{\prime})\cdot({\mathtt{tw}}(G^{\prime})-1)$ and hence
$(T^{\phi},\beta^{\phi})$ has width
$\Delta(G^{\prime}){\mathtt{tw}}(G^{\prime})+{\mathtt{tw}}(G^{\prime})^{2}+2$.

As $(T,\beta)$, $G^{\prime}$ and the formula $\phi$ can be computed in time
$\mathcal{O}({\mathtt{tw}}(G^{\prime})^{2}n)$, combining the reduction with
the algorithm from Proposition 4.9 yields a
$2^{2^{\mathcal{O}(\Delta{\mathtt{tw}})}}n^{O(1)}$ time algorithm.

Finally, we prove our ETH based lower bound.

######  Theorem 4.14.

Unless the ETH fails, there is no algorithm for Core stability running in time
$2^{2^{o({\mathtt{pw}})}}n$ even if $G$ has bounded degree and weights are
constant.

We give an overview of our construction. Given an instance $\phi$ of
$(3,3)$-SAT (each variable appears at most 3 times) we construct a graph
$(G,w)$ and show that $\phi$ is satisfyable if and only if $(G,w)$ is core
stable. First we tweak the auxiliary gadget from Section 4.1 slightly such
that if we attach $(H,w_{\rho})$ at a set of vertices $S$ then
$\\{h,s\\}\in\mathcal{P}$ for some $s\in S$ for every core stable partition
$\mathcal{P}$ (details are given in the Appendix).

We now describe the construction and certain partitions of $V(G)$ which we
refer to as candidate partition. Every variable $x_{i}$, $i\in[n]$ of $\phi$
is represented by two vertices $y_{i}$ and $\lnot y_{i}$ and we attach an
auxiliary gadget at $\\{y_{i},\lnot y_{i}\\}$. Any candidate partition
$\mathcal{P}$ has to contain either $\\{h,y_{i}\\}$ or $\\{h,\lnot y_{i}\\}$
(but not both) where $h$ is a vertex of the attached gadget. For any other
vertex $v$ without an attached auxiliary gadget (excluding vertices of
auxiliary gadgets) $\\{v\\}$ has to be in any candidate partition. For any
vertex $v$ with attached copy $(H,w_{\rho})$ the set $\\{v,h\\}$ has to be in
any candidate partition. Using the properties of the auxiliary gadget, we
obtain that any core stable partition has to be a candidate partition. By
construction, there is a correspondence between assignments and candidate
partitions, i.e. $\alpha(x_{i})=1$ if and only if
$\\{h,y_{i}\\}\in\mathcal{P}$ for candidate partition $\mathcal{P}$ and the
corresponding assignment $\alpha$.

Any blocking coalition of a candidate partition allows us to find a clause
which is not satisfied under the assignment which corresponds to the candidate
partition and vise versa. This is realized as follows. We take $2m+1$ cycles
$U^{1},\dots,U^{m},V^{1},\dots,V^{m},Z$ of length approximately $3n$ where
$2^{m}\leq 3n$ is the number of clauses of $\phi$. By choosing suitable edge
weights, we enforce that any blocking coalition of any candidate partition
contains $Z$ and either $U^{k}$ or $V^{k}$ (but not both) for every $k\in[m]$.
For now, we call any set containing $Z$, $U^{k}$ or $V^{k}$ (but not both) for
every $k\in[m]$ (and some other vertices we neglect here) a candidate blocking
coalition. We number the clauses of $\phi$ in such a way that each candidate
blocking coalition corresponds to a clause, i.e. the $j$-th clause corresponds
to the candidate blocking coalition $X$ in which $U^{k}\in X$ if and only if
the $k$-th bit of $j$ in binary is $0$.

Each vertex in $Z$ corresponds to the appearance of a variable. Assume $z\in
Z$ corresponds to the appearance of variable $x_{i}$ in clause $c_{j}$. We
connected $z$ to either $y_{i}$ or $\lnot y_{i}$ dependent on whether $x_{i}$
appears negated in $c_{j}$. We connect $z$ to either $U^{k}$ or $V^{k}$ for
every $k\in[m]$ using a special gadget dependent on whether the $k$-th bit of
$j$ in binary is $0$ or $1$. The gadget enforces that $z$ obtains a $+1$
towards its total utility in $X$ if and only if the candidate blocking
coalition $X$ does not encodes the clause $c_{j}$. By choice of edge weights,
we ensure that vertex $z$ can only be convinced to join a blocking coalition
if it either gets $+1$ from its clause selection gadget or $+1$ from $y_{i}$
(or $\lnot y_{i}$, resp.). On the other hand, $y_{i}$ ($\lnot y_{i}$, resp.)
can only be convinced to join a blocking coalition if it appears as a
singleton in the the partition we are trying to block and hence the
corresponding literal is false. In conclusion, for any candidate partition
$\mathcal{P}$ there is a blocking coalition $X$ if and only if for the clause
corresponding to $X$ each literal is false. Hence, $(G,w)$ is core stable if
and only if $\phi$ is satisfiable.

######  Proof 4.15 (Proof of Theorem 4.14).

We give a reduction from $(3,3)$-SAT which is the variant of $3$-SAT in which
every variable is restricted to appear at most $3$ times. Let $\phi$ be an
instance of $(3,3)$-SAT on variables $x_{1},\dots,x_{n}$ (and hence $\phi$
contains at most $3n$ clauses). Without loss of generality, we can assume that
no clause contains both $x_{i}$ and $\lnot x_{i}$ (because then $\phi$ is
trivially satisfiable) and that $x_{i}$ as well as $\lnot x_{i}$ appears in
$\phi$ for every $i\in[n]$ (as otherwise we can set the literal that appears
to be true). For each $i\in[n]$ we let $b_{i}\in\\{2,3\\}$ be the number of
appearances of $x_{i}$ in $\phi$. We denote the clauses of $\phi$ by
$c_{1},\dots c_{2^{m}}$, $2^{m}\leq 3n$. Here we assumed for easier notation
that the number of clauses is a power of $2$.

In the following we construct an instance $(G,w)$ of CS of bounded degree $20$
and path-width in $\mathcal{O}(\log n)$. The graph $(G,w)$ can be constructed
in polynomial time. We show that $(G,w)$ admits a core stable partition if and
only if $\phi$ is satisfyable. Hence, if we could decide CS in time
$2^{2^{o({\mathtt{pw}}(G))}}$, then we can solve $(3,3)$-SAT in time
$2^{o(n)}$ contradicting the ETH.

We first describe the construction of $(G,w)$. For this, we set $\rho=-20-2m$.

#### Variable gadget

For each $i\in[n]$ we introduce vertices $y_{i},\lnot
y_{i},z_{i,1},\dots,z_{i,b_{i}}$. For each $j\in[b_{i}]$ we add edge
$y_{i}z_{i,j}$ of weight $1$ if the $j$st clause in which $x_{i}$ appears
contains the literal $x_{i}$ and we add edge $\lnot y_{i}z_{i,j}$ of weight
$1$ if the $j$st clause in which $x_{i}$ appears contains the literal $\lnot
x_{i}$.

For every $i\in[n]$, $j\in[b_{i}-1]$ we add the edge $z_{i,j}z_{i,j+1}$ of
weight $5$. For every $i\in[n-1]$ we add the edge $z_{i,b_{i}}z_{i+1,1}$ of
weight $5$. Hence all $z_{i,j}$’s are contained in a path in which every edge
has weight $5$. Gor an illustration of this gadget see Figure 4(c).

#### Clause containment gadget

For each $i\in[n]$, $j\in[b_{i}]$, $k\in[0,m+1]$ we introduce a vertex
$s_{i,j}^{k}$. Additionally, for each $i\in[n]$, $j\in[b_{i}]$, $k\in[0,m]$ we
add a vertex $\overline{s}_{i,j}^{k}$. For each $i\in[n]$, $j\in[b_{i}]$,
$k\in[0,m]$ we add edge $s_{i,j}^{k}\overline{s}_{i,j}^{k}$ of weight 10,
$\overline{s}_{i,j}^{k}s_{i,j}^{k+1}$ of weight $9$ and we add edge
$s_{i,j}^{m+1}z_{i,j}$ of weight $1$. Furthermore, for every $i\in[n]$,
$j\in[b_{i}]$, $k\in[0,m]$ we introduce vertices $t_{i,j}^{k},u_{i,j}^{k}$,
$v_{i,j}^{k}$ and add edge $s_{i,j}^{k}t_{i,j}^{k}$ of weight $-1$.

For every $i\in[n]$, $j\in[b_{i}-1]$ $k\in[0,m]$ we add edges
$u_{i,j}^{k}u_{i,j+1}^{k}$ and $v_{i,j}^{k}v_{i,j+1}^{k}$ of weight $5$. For
every $i\in[n-1]$, $k\in[0,m]$ we add edges $u_{i,b_{i}}^{k}u_{i+1,1}^{k}$ and
$v_{i,b_{i}}^{k}v_{i+1,1}^{k}$ of weight $5$. Hence for every fixed $k$ all
$u_{i,j}^{k}$’s are contained in a path in which every edge has weight $5$ and
equally for the $v_{i,j}^{k}$’s.

Fix $i\in[n]$ and $j\in[b_{i}]$ and assume $c_{\ell}$ is the clause containing
the $j$th appearance of $x_{i}$. Let $\sum_{k=0}^{m}a_{i,j}^{k}2^{k}$ where
$a_{i,j}^{k}\in\\{0,1\\}$ be the binary representation of $\ell$. For every
$k\in[0,m]$ we add edge $t_{i,j}^{k}u_{i,j}^{k}$ of weight $2$ if
$a_{i,j}^{k}=0$ and edge $t_{i,j}^{k}v_{i,j}^{k}$ of weight $2$ if
$a_{i,j}^{k}=1$. For an illustration see Figure 4(a).

(a) A clause containment gadget encoding that variable $x_{1}$ is contained in
the second clause.

(b) The clause selection gadget.

(c) Example of a variable gadget of $x_{1}$ where $x_{1}$ appears twice in
$\phi$ and $\lnot x_{1}$ appears once.

Figure 4: The gadgets from the construction in the proof of Theorem 4.14. Here
auxiliary gadgets are depicted my blue hexagons, there attachment at set $S$
is signified by a squiggly edge and red edges without weight are the edges of
weight $\rho$.

#### Clause selection gadget

For every $k\in[0,m]$ we introduce three vertices $p^{k},q^{k},r^{k}$ and add
edges $p^{k}q^{k}$ and $p^{k}r^{k}$ of weight $1$ and $q^{k}r^{k}$ of weight
$\rho$.

We add edges $z_{n,b_{n}}p^{0}$, $p^{m}z_{1,1}$ of weight $5$. Additionally,
for every $k\in[0,m-1]$ we add edges $p^{k}p^{k+1}$ of weight $5$. Hence all
$z_{i,j}$’s and all $p^{k}$’s are contained in a cycle.

For every $k\in[0,m]$ we add edges $u_{n,b_{n}}^{k}q^{k}$, $q^{k}u_{1,1}^{k}$
of weight $5$. Additionally, for every $k\in[0,m]$ we add edges
$v_{n,b_{n}}^{k}r^{k}$, $r^{k}v_{1,1}^{k}$ of weight $5$. Hence for each
$k\in[0,m]$ the $u_{i,j}^{k}$’s together with $q^{k}$ form a cycle and the
$v_{i,j}^{k}$’s together with $r^{k}$ form a cycle. For an illustration see
Figure 4(b).

#### Auxiliary gadgets

For every $i\in[n]$ we take one copy $(H_{i},w_{\rho})$ of $(H,w_{\rho})$ and
let $h^{i}$ be the vertex $h$ in the copy $H_{i}$. We $9$-neighbourhood attach
$(H_{i},w_{\rho})$ at $\\{y_{i},\lnot y_{i}\\}$.

Furthermore, for every vertex
$u\in\\{\overline{s}_{i,j}^{k},u_{i,j}^{k},v_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$
we introduce one copy $(H_{u},w_{\rho})$ of $(H,w_{\rho})$ and let $h_{u}$ be
the vertex $h$ in the copy $H_{u}$. We $10$-neighborhood attach
$(H_{u},w_{\rho})$ at $\\{u\\}$ for every
$u\in\\{\overline{s}_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$.
Additionally, if $a_{i,j}^{k}=0$ we $10$-neighborhood attach
$(H_{u},w_{\rho})$ at $\\{u\\}$ for every
$u\in\\{u_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$ and we $9$-neighborhood
attach $(H_{u},w_{\rho})$ at $\\{u\\}$ for every
$u\in\\{v_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$. Otherwise, if
$a_{i,j}^{k}=1$ we $9$-neighborhood attach $(H_{u},w_{\rho})$ at $\\{u\\}$ for
every $u\in\\{u_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$ and we
$10$-neighborhood attach $(H_{u},w_{\rho})$ at $\\{u\\}$ for every
$u\in\\{v_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$.

Additionally, for every vertex
$u\in\\{p^{k},q_{k},r_{k},z_{i,j}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$ we
introduce one copy $(H_{u},w_{\rho})$ of $(H,w_{\rho})$ and let $h_{u}$ be the
vertex $h$ in the copy $H_{u}$. We $10$-neighborhood attach $(H_{u},w_{\rho})$
at $\\{u\\}$.

Finally, for every vertex
$u\in\\{s_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m+1]\\}$ we introduce one copy
$(H_{u},w_{\rho})$ of $(H,w_{\rho})$ and let $h_{u}$ be the vertex $h$ in the
copy $H_{u}$. We $9$-neighborhood attach $(H_{u},w_{\rho})$ at $\\{u\\}$ for
$u=s_{i,j}^{k}$. For an illustration of where the auxiliary gadgets are
attached see Figure 4.

This concludes the construction of graph $(G,w)$. First observe that the
degree of $G$ is at most $20$. To see this, observe that in
$G\Big{[}\\{s_{i,j}^{k}:j\in[b_{i}],k\in[0,m+1]\\}\cup\\{p_{k},q_{k},r_{k},\overline{s}_{i,j}^{k},t_{i,j}^{k},u_{i,j}^{k},v_{i,j}^{k},y_{i},\lnot
y_{i},z_{i,j}:i\in[n],j\in[b_{i}],k\in[0,m]\\}\Big{]}$ every vertex has degree
at most $4$ except $y_{i},\lnot y_{i}$ who have degree at most $2$. Attaching
a copy of $(H,w_{\rho})$ at a single vertex increases the degree of that
vertex by $6$ (attaching $(H,w_{\rho})$ at two vertices increases the degree
by $7$) and the degree of all its neighbours by $1$, yielding a degree bound
of $14$ for vertices in
$\\{s_{i,j}^{k}:j\in[b_{i}],k\in[0,m+1]\\}\cup\\{p_{k},q_{k},\overline{s}_{i,j}^{k},r_{k},t_{i,j}^{k},u_{i,j}^{k},v_{i,j}^{k},y_{i},\lnot
y_{i},z_{i,j}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$. On the other hand, the degree
of vertices within any copy of $(H,w_{\rho})$ which was attach is at most $6$
plus the number of neighbours of the vertex at which the copy of
$(H,w_{\rho})$ was attached. Also observe, that $\rho<-\max_{u\in
V(G)}\sum_{uv\in E(G),\atop{w(uv)>0}}w(uv)$ and hence we can use Lemma 4.2.

We first argue that $G$ has path-width in $\mathcal{O}(\log n)$. To this end,
define

$B_{0}=\\{p^{k},q^{k},r^{k}:k\in[0,m]\\}\cup\bigcup_{u\in\\{p^{k},q^{k},r^{k}:k\in[0,m]\\}}V(H_{u})$

and for every $i\in[n]$ define

$\displaystyle B_{i}=$
$\displaystyle\\{s_{i,j}^{k}:j\in[b_{i}],k\in[0,m+1]\\}\cup\\{\overline{s}_{i,j}^{k},t_{i,j}^{k},u_{i,j}^{k},v_{i,j}^{k},y_{i},\lnot
y_{i},z_{i,j}:j\in[b_{i}],k\in[0,m]\\}$ $\displaystyle\cup
V(H_{i})\cup\bigcup_{u\in\\{s_{i,j}^{k}:j\in[b_{i}],k\in[0,m+1]\\}\atop{\cup\\{\overline{s}_{i,j}^{k},u_{i,j}^{k},v_{i,j}^{k},z_{i,j}:j\in[b_{i}],k\in[0,m]\\}}}V(H_{u}).$

We observe that $B_{0}$ has size $21+21m$ while $B_{i}$ has size at most
$125+87m$. By construction there is no edges between $B_{i}$ and $B_{j}$ if
$|i-j|>1$. Hence we get a path-decomposition of $G$ of width at most
$271+195m$ by placing all vertices of $B_{0},B_{i},B_{i+1}$ in the bag of the
$i$th vertex of the path. We now argue that $(G,w)$ is core stable if and only
if $\phi$ is satisfiable.

First assume that $(G,w)$ is core stable and let $\mathcal{P}$ be a core
stable partition of $V(G)$. Without loss of generality we can assume that
$\mathcal{P}$ is connected. By Lemma 4.2 property $(\Pi^{\prime}1)$, we know
that $\\{u,h_{u}\\}\in\mathcal{P}$ for every
$u\in\\{s_{i,j}^{k}:j\in[b_{i}],k\in[0,m+1]\\}\cup\\{p^{k},q^{k},r^{k},\overline{s}_{i,j}^{k},u_{i,j}^{k},v_{i,j}^{k},z_{i,j}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$
and either $\\{h^{i},y_{i}\\}\in\mathcal{P}$ or $\\{h^{i}\lnot
y_{i}\\}\in\mathcal{P}$ for every $i\in[n]$. Additionally, by Lemma 4.2
property $(\Pi 2)$ we know that

$P\subseteq\bigcup_{i\in[n]}V(H_{i})\setminus\\{h^{i}\\}\cup\bigcup_{u\in\\{s_{i,j}^{k}:j\in[b_{i}],k\in[0,m+1]\\}\atop{\cup\\{p^{k},q^{k},r^{k},t_{i,j}^{k},u_{i,j}^{k},v_{i,j}^{k},z_{i,j}:i\in[n],j\in[b_{i}],k\in[0,m]\\}}}V(H_{u})\setminus\\{h_{u}\\}$

if $P\in\mathcal{P}$ contains any vertex from this union of auxiliary gadgets.
As $G[\\{t_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m]\\}]$ contains only
singletons and we assumed that $\mathcal{P}$ is connected, we further know
that $\\{t_{i,j}^{k}\\}\in\mathcal{P}$ for every $i\in[n]$, $j\in[b_{i}]$,
$k\in[0,m]$.

We define an assignment $\alpha:\\{x_{1},\dots,x_{n}\\}\rightarrow\\{0,1\\}$
in the following way. If $\\{h^{i},y_{i}\\}\in\mathcal{P}$, then we set
$\alpha(x_{i})=1$ and if $\\{h^{i}\lnot y_{i}\\}\in\mathcal{P}$, then we set
$\alpha(x_{i})=0$. We claim that $\alpha$ is a satisfying assignment for
$\phi$. Towards a contradiction assume that this is not the case and assume
that $c_{\ell}$ is a clause which does not evaluate to $1$ under the
assignment $\alpha$. Let $\ell=\sum_{k=0}^{m}a_{k}2^{k}$ be the binary
representation of $\ell$. Define a set $X$ as follows.

$\displaystyle X=$
$\displaystyle\Big{\\{}p^{k}:k\in[0,m]\Big{\\}}\cup\Big{\\{}q^{k}:k\in[0,m],a_{k}=0\Big{\\}}\cup\Big{\\{}r^{k}:k\in[0,m],a_{k}=1\Big{\\}}$
$\displaystyle\cup$
$\displaystyle\Big{\\{}u_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m],a_{k}=0\Big{\\}}$
$\displaystyle\cup$
$\displaystyle\Big{\\{}v_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m],a_{k}=1\Big{\\}}$
$\displaystyle\cup$
$\displaystyle\Big{\\{}t_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m],a_{i,j}^{k}=a_{k}\Big{\\}}$
$\displaystyle\cup$
$\displaystyle\Big{\\{}s_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m+1],k\geq\min\big{(}\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}\cup\\{m+2\\}\big{)}\Big{\\}}$
$\displaystyle\cup$
$\displaystyle\Big{\\{}\overline{s}_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m],k\geq\min\big{(}\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}\cup\\{m+2\\}\big{)}\Big{\\}}$
$\displaystyle\cup$
$\displaystyle\Big{\\{}y_{i}:i\in[n],\\{y_{i},h^{i}\\}\notin\mathcal{P}\Big{\\}}\cup\Big{\\{}\lnot
y_{i}:i\in[n],\\{\lnot
y_{i},h^{i}\\}\notin\mathcal{P}\Big{\\}}\cup\Big{\\{}z_{i,j}:i\in[n],j\in[b_{i}]\Big{\\}}.$

In the following we argue that $X$ is a blocking coalition of $\mathcal{P}$
which yields a contradiction. First observe that no two vertices in $X$ are
connected by an edge of weight $\rho$. Furthermore, all edges in $G[X]$ have
positive weight, apart from edges $s_{i,j}^{k}t_{i,j}^{k}$. Hence, it is
sufficient to only consider positive weight edges and edges of the form
$s_{i,j}^{k}t_{i,j}^{k}$. Let $i\in[n]$, $j\in[b_{i}]$, $k\in[0,m]$ be
arbitrary but fixed.

First note that $p^{k}$ has utility $10$ in $\mathcal{P}$ as
$\\{p^{k},h_{p^{k}}\\}\in\mathcal{P}$. As both $p^{k-1}\in X$ ($z_{n,b_{n}}\in
X$ if $k=0$) and $p^{k+1}\in X$ ($z^{1,1}\in X$ if $k=m$) and additionally
either $q^{k}\in X$ or $r^{k}\in X$, we conclude that $p^{k}$ has improved its
utility from $10$ to $11$ by joining $X$.

Next observe that both $q^{k}$ and $r^{k}$ have utility $10$ in $\mathcal{P}$.
If $a_{k}=0$ then $q^{k}\in X$ ($r^{k}\notin X$) and so are $p^{k}$ as well as
both $u_{n,b_{n}}^{k}$ and $u_{1,1}^{k}$. Hence, $q^{k}$ has utility $11>10$
in $X$. The same argument shows that $r^{k}$ has utility $11>10$ in $X$ in the
case that $a_{k}=1$.

Furthermore, $u_{i,j}^{k}$ has utility $10$ if $a_{i,j}^{k}=0$ and $9$
otherwise. Assume that $a_{k}=0$ and hence $u_{i,j}^{k}\in X$ (and
$v_{i,j}^{k}\notin X$). In the case that $a_{i,j}^{k}=0$, by construction
$t_{i,j}^{k}\in X$ and $u_{i,j}^{k}t_{i,j}^{k}\in E(G)$ and hence
$u_{i,j}^{k}$ has utility $11$ in $X$. On the other hand, if $a_{i,j}^{k}=1$,
then $u_{i,j}^{k}$ has utility $10$ in $X$. In both cases $u_{i,j}^{k}$
improves its utility by joining $X$. An analogous argument shows that, if
$a_{k}=1$ and hence $v_{i,j}^{k}\in X$, then $v_{i,j}^{k}$ improves its
utility by joining $X$.

As $\\{t_{i,j}^{k}\\}\in\mathcal{P}$, $t_{i,j}^{k}$ has utility $0$ in
$\mathcal{P}$. In case $a_{i,j}^{k}=a_{k}$ and $t_{i,j}^{k}\in X$ we need to
consider two cases. If $a_{i,j}^{k}=a_{k}=0$ then $t_{i,j}^{k}$ is adjacent to
$u_{i,j}^{k}$, $w(t_{i,j}^{k}u_{i,j}^{k})=2$ and $u_{i,j}\in X$. Even if
$t_{i,j}^{k}$’s other neighbour $s_{i,j}^{k}\in X$, $t_{i,j}^{k}$ still has
utility $1$ in $X$. Equivalently, if $a_{i,j}^{k}=a_{k}=1$, then $t_{i,j}^{k}$
has utility at least $1$ in $X$.

Consider $\overline{s}_{i,j}^{k}$ and assume that $\overline{s}_{i,j}^{k}\in
X$. By definition, this implies that
$k\leq\min\big{(}\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}\cup\\{m+2\\}\big{)}$
and hence both $s_{i,j}^{k}\in X$ and $s_{i,j}^{k+1}\in X$. Hence,
$\overline{s}_{i,j}^{k}$ has utility $19$ in $X$ while
$\overline{s}_{i,j}^{k}$ has utility $10$ in $\mathcal{P}$.

Next consider $s_{i,j}^{m+1}$ and assume that $s_{i,j}^{m+1}\in X$. Hence,
$m+1\geq\min\big{(}\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}\cup\\{m+2\\}\big{)}$.
As $m+1$ cannot be equal to
$\min\big{(}\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}\cup\\{m+2\\}\big{)}$
we know that $\overline{s}_{i,j}^{m}\in X$. Hence the utility of
$s_{i,j}^{m+1}$ in $X$ is $10$ (as $z_{i,j}$ is also in $X$) while the utility
of $s_{i,j}^{m+1}$ is $9$ in $\mathcal{P}$. Next consider $s_{i,j}^{k}$,
$k\leq m$ and assume that $s_{i,j}^{k}\in X$ and hence
$k\geq\min\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}$.
First consider the case that
$k=\min\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}$. As
$a_{i,j}^{k}\not=a_{k}$, we know that $t_{i,j}^{k}\notin X$. As by
construction $\overline{s}_{i,j}^{k}\in X$ and
$w(s_{i,j}^{k}\overline{s}_{i,j}^{k})=10$ we know that $s_{i,j}^{k}$ has
utility $10$ in $X$ while its utility is $9$ in $\mathcal{P}$. On the other
hand, if
$k>\min\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}$ then
both $\overline{s}_{i,j}^{k-1}\in X$ and $\overline{s}_{i,j}^{k}\in X$ and
hence $s_{i,j}^{k}$ has utility at least $18$ (even if $t_{i,j}^{k}\in X$).

Now consider $y_{i}$ and observe that if $y_{i}\in X$, then $y_{i}$ has
utility $0$ in $\mathcal{P}$. As $y_{i}$ has at least one neighbor in the set
$\\{z_{i,j}:i\in[n],j\in[b_{i}]\\}$ (by our assumption that both literals
$x_{i},\lnot x_{i}$ appear in $\phi$) and the corresponding edge has positive
weight, $y_{i}$ improves its utility by joining $X$. Equivalently, for $\lnot
y_{i}$.

Finally, consider the vertex $z_{i,j}$ and observe that its utility in
$\mathcal{P}$ is $10$. First assume that $s_{i,j}^{m+1}\in X$. In this case
$z_{i,j}$ has utility $11$ in $X$ as
$\\{p^{1},p^{m}\\}\cup\\{z_{i,j}:i\in[n],j\in[b_{i}]\\}\subseteq X$. On the
other hand, if $s_{i,j}^{m+1}\notin X$ then
$\min\big{(}\\{k^{\prime}\in[0,m]:a_{i,j}^{k^{\prime}}\not=a_{k^{\prime}}\\}\cup\\{m+2\\}\big{)}=m+2$
by construction of $X$. Hence, $a_{i,j}^{k^{\prime}}=a_{k^{\prime}}$ for every
$k^{\prime}\in[0,m]$ which implies that
$\sum_{k^{\prime}=0}^{m}a_{i,j}^{k^{\prime}}2^{k^{\prime}}=\ell$. By
construction this means that $x_{i}$ appears in $c_{\ell}$. Assume that the
literal $x_{i}$ is contained in $c_{\ell}$ (the case that the literal $\lnot
x_{i}$ is contained in $c_{\ell}$ is analogous). As $x_{i}$ appears in
$c_{\ell}$ and $c_{\ell}$ evaluates to $0$ under the assignment $\alpha$, we
know that $\alpha(x_{i})=0$. By definition of $\alpha$ this means that
$\\{h^{i},\lnot y_{i}\\}\in\mathcal{P}$ and hence $y_{i}\in X$. Therefore,
$z_{i,j}$ has utility $11$ in $X$. As $z_{i,j}$ improves its utility in both
cases we have argued that $X$ is a blocking coalition contradicting our
assumption that $\mathcal{P}$ is core stable. Hence, $\alpha$ is a satisfying
assignment for $\phi$.

On the other hand, assume that $\phi$ is satisfiable and let
$\alpha:\\{x_{1},\dots,x_{n}\\}\rightarrow\\{0,1\\}$ be a satisfying
assignment of $\phi$. We define a partition $\mathcal{P}$ of $V(G)$ as
follows. For $i\in[n]$ we include sets $\\{h^{i},y_{i}\\}$ as well as
$\\{\lnot y_{i}\\}$ in $\mathcal{P}$ if $\alpha(x_{i})=1$ and we include sets
$\\{h^{i},\lnot y_{i}\\}$ as well as $\\{y_{i}\\}$ in $\mathcal{P}$ if
$\alpha(x_{i})=0$. We further include the core stable partition of
$H_{i}\setminus\\{h^{i}\\}$ defined in Section 4.1 in $\mathcal{P}$. For each
vertex
$u\in\\{s_{i,j}^{k}:j\in[b_{i}],k\in[0,m+1]\\}\cup\\{p_{k},q_{k},\overline{s}_{i,j}^{k},r_{k},u_{i,j}^{k},v_{i,j}^{k},z_{i,j}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$
we include the set $\\{u,h_{u}\\}$ in $\mathcal{P}$ and the core stable
partition $\mathcal{P}_{(H_{u},w_{\rho})}$ of $H_{u}\setminus\\{h_{u}\\}$
defined in Section 4.1. Finally, for every
$u\in\\{t_{i,j}^{k}:i\in[n],j\in[b_{i}],k\in[0,m]\\}$ we include the singleton
$\\{u\\}$ in $\mathcal{P}$. Towards a contradiction, assume that $\mathcal{P}$
is not a core stable partition and $X$ is a blocking coalition. In the
following, we show that $X$ must have a particular structure, i.e. $X$ must be
of the form as the blocking coalition in the previous direction of the proof.
The property of the coalition $X$ being blocking can then be translated into
an argument that $\alpha$ is not a satisfying assignment yielding the desired
contradiction.

We define $Z=\\{p^{k},z_{i,j}:i\in[n],j\in[b_{i}],k\in[0,m]\\}\subseteq X$ and
for every $k\in[0,m]$ we define
$U^{k}=\\{q^{k},u_{i,j}^{k}:i\in[n],j\in[b_{i}]\\}$,
$V^{k}=\\{r^{k},v_{i,j}^{k}:i\in[n],j\in[b_{i}]\\}$,
$T^{k}_{0}=\\{t_{i,j}^{k}:i\in[n],j\in[b_{i}],a_{i,j}^{k}=0\\}$ and
$T_{1}^{k}=\\{t_{i,j}^{k}:i\in[n],j\in[b_{i}],a_{i,j}^{k}=1\\}$. The following
three claims describe precisely which compositions of vertices are valid for
$X$.