# defensive_alliances_in_signed_networks__e25a4248.pdf

Journal of Artificial Intelligence Research 82 (2025) 2189-2232 Submitted 09/2024; published 04/2025

Defensive Alliances in Signed Networks

Emmanuel Arrighi emmanuel@arrighi.eu Ens L, UCBL, CNRS, Inria, LIP UMR 5668, 69007, Lyon, France

Zhidan Feng zhidanfeng@mail.sdu.edu.cn Shandong University, School of Mathematics and Statistics 264209 Weihai, China Universit at Trier, Fachbereich 4 Abteilung Informatikwissenschaften 54286 Trier, Germany

Henning Fernau fernau@uni-trier.de Kevin Mann mann@uni-trier.de Universit at Trier, Fachbereich 4 Abteilung Informatikwissenschaften 54286 Trier, Germany

Xingqin Qi qixingqin@sdu.edu.cn Shandong University, School of Mathematics and Statistics 264209 Weihai, China

Petra Wolf mail@wolfp.net Universit e de Bordeaux, CNRS, Bordeaux INP, La BRI UMR 5800, 33400, Talence, France

The analysis of social networks and community detection is a central theme in Artificial Intelligence. One line of research deals with finding groups of agents that could work together to achieve a certain goal. To this end, different notions of so-called clusters or communities have been introduced in the literature of graphs and networks. Among these, a defensive alliance is a kind of quantitative group structure. However, all studies on alliances so far have ignored one aspect that is central to the formation of alliances on a very intuitive level, assuming that the agents are preconditioned concerning their attitude towards other agents: they prefer to be in some group (or in an alliance) together with the agents they like, so that they are happy to help each other towards their common aim, possibly then working against the agents outside of their group that they dislike. Signed networks were introduced in the psychology literature to model liking and disliking between agents, generalizing graphs in a natural way. Hence, we propose the novel notion of a defensive alliance in the context of signed networks. We then investigate several natural algorithmic questions related to this notion. These, and also combinatorial findings, connect our notion to that of correlation clustering, which is a well-established idea of finding groups of agents within a signed network. Also, we introduce a new structural parameter for signed graphs, the signed neighborhood diversity snd, and exhibit a snd-parameterized algorithm that finds one of the smallest defensive alliances in a signed graph.

2025 The Authors. Published by AI Access Foundation under Creative Commons Attribution License CC BY 4.0.

Arrighi, Feng, Fernau, Mann, Qi & Wolf

1. Introduction and Motivation

Graphs or networks (we use these terms interchangeably) are one of the most important data structures, which can represent complex relations between objects. Mining graph data has become a hot research field in recent years. Some traditional data mining algorithms have been gradually extended to graph data, such as clustering, classification and frequent pattern mining (Fortunato, 2010; Cheng et al., 2010). However, in the context of graph data, when the nodes of a network may represent persons or groups of persons, up to political entities like countries, one should also consider categories that express, e.g., that two persons like or dislike each other. This has led to the concept of signed graphs, introduced in (Heider, 1946; Harary, 1953). Positive edges model trust, friendship, or similarity, while negative edges express distrust, opposition (enmity, hostility), or antagonism. This model originated from psychology; there, it continued to flourish over decades; see (De Soto et al., 1968; Mohazab & Feger, 1985; Crandall et al., 2007; Brusco & Steinley, 2010; Brashears & Brashears, 2016; Zorn et al., 2022). The notion of signed graphs has become one of the main modeling tools in modern network science, with significant applications; e.g., link prediction, as in (Ye et al., 2013; Song & Meyer, 2015), social system reasoning, as in (Tang et al., 2016), clustering and community detection, see, e.g., (Chiang et al., 2014; Cadena et al., 2016; Li et al., 2021) and the following discussion.

1.1 Clustering in Unsigned Networks

In classical unsigned graph models of agent interaction, where edges between vertices describe links between these agents, the simplest form of a perfect group of agents corresponds to a clique. Consequently, one line of community detection involves finding (potentially large) cliques, which is a well-researched area, being equivalent to finding large independent sets or small vertex covers. The corresponding research stretches over decades; see (Bron & Kerbosch, 1973; Eppstein et al., 2013). Hao et al. (2014) adapted the notion of a clique (and hence that of a community) to signed graphs by requiring a positive edge between any two community members. By way of contrast, Li et al. (2021) suggested a notion of a signed clique that allows a certain fraction of negative connections within a clique, concretely, they required that every vertex in the clique has at most k negative neighbors and at least αk (α 1) positive neighbors. A bit more relaxed, Yang et al. (2007) described a community in a signed network as a dense positive subgraph such that, assuming that the graph has been partitioned into such groups, the negative inter-group relations are also dense. Put to the extreme case of denseness, where all edges within groups are positive while all edges between groups are negative, we arrive at the notion of weakly balanced signed graphs discussed below. This idea was also used to find antagonistic communities in (Chu et al., 2016; Gao et al., 2016), which aim to find pairs of antagonistic sub-communities such that vertices of the same sub-community share positive relationships while vertices between a pair of antagonistic sub-communities have negative relationships. Moreover, Sun et al. (2022) discussed a more stable community (stable k-core), which relaxed the clique condition into positive degree larger than k, but also satisfies the balance condition which we also explained below formally.

Defensive Alliances in Signed Graphs

1.2 Defensive Alliances in Unsigned Networks

We will follow the approach of detecting communities defined by structural properties as exemplified above in this paper, lifting notions from unsigned to signed networks, as opposed to approaches based on spectral methods (Kunegis et al., 2009) or inspired by physical statistics (Palla et al., 2005; Yang et al., 2007; Pons & Latapy, 2006; Yang et al., 2007), and other modularity-based methods, like (Amelio & Pizzuti, 2013). Clustering on graph data is also called community detection. Then, for unsigned graph, the main purpose is to partition the graph into many clusters such that edges within each cluster are dense while edges between clusters are sparse. To quantitatively measure the relative density of a cluster, one can assume each node v in a cluster S has more neighbors in S than outside. Such vertex set S is also called a defensive alliance , a concept that was first studied in (Fricke et al., 2003; Kim et al., 2005; Kristiansen et al., 2004; Szab o & Cz ar an, 2001; Shafique, 2004). Up to now, hundreds of papers have been published on alliances in graphs and related notions, as also certified by surveys and book chapters; see, in chronological ordering, (Fernau & Rodr ıguez-Vel azquez, 2014; Yero & Rodr ıguez Vel azquez, 2017; Ouazine et al., 2018; Haynes et al., 2021). An overview on the wide variety of applications for alliances in graphs is given in (Ouazine et al., 2018), including community-detection problems as described in (Seba et al., 2012). More formally, a vertex set S = of an unsigned graph G is a defensive alliance if, for each v S, |N(v) S| + 1 |N(v) \ S|, with N(v) denoting the open neighborhood of v. Hence, another interpretation or intuition behind a defensive alliance is that each member of the alliance can be protected by the alliance from any attack outside. As a more general variation, k-defensive alliances are sets S satisfying the condition |N(v) S| |N(v) \ S| + k for each v S. In this model with unsigned graphs, edges indicate close geographic distances, so that an attack is indeed possible, as well as a defense. The world is often not that simple, as between different countries, there might be more or less friendly bonds for historical or many other reasons. Thus, it makes sense to qualify the edges modelling geographic vicinity as friend or foe relationships. This is why we propose to adapt the notion of a defensive alliance towards signed graphs, which naturally capture these aspects. We rather expect attacks from enemies than from friends, while we expect our friends within our alliance to help us and possible enemies within our alliance at least to stay neutral. Moreover, the cited previous work on antagonistic communities does not care about the quantitative relationship between different types edges and neglected the aspect of defensiveness, which is more accurate in depicting international relationships, see (Doreian & Mrvar, 2015), or social opinion networks, refer to (Kunegis et al., 2009), etc.

1.3 Clusters in Signed Networks

Classical concepts of clusters, as (Cartwright & Harary, 1956), in signed networks allow only positive edges between cluster members. However, this need not reflect real-world situations. Here, we relatively often find entities with well-established negative relationships within one alliance. We will give a concrete example from ethnology below. Even though in more formalized political context, alliance members mostly promise to help each other (irrespectively of possible negative preconditions), it might well be that some alliance members will be quicker to help than others; at least for an immediate response to a threat,

Arrighi, Feng, Fernau, Mann, Qi & Wolf

members with positive preconditions will be far more reliable. Our proposed definition of a defensive alliance takes this into account: it rules out too many frictions within an alliance by requiring that each member has less negative neighbors in the alliance than positive ones, but it also requires that each member should face less negative neighbors outside the alliance than positive neighbors within to enable defense. The formal definition will follow in a later section. We would also like to mention that group structures similar to the notion of defensive alliances defined in our paper have been considered before in the AI and ML literature. For instance, (Tzeng et al., 2020) describes procedures to discover conflicting groups within a signed network; these groups should satisfy certain properties. The first one is that within a group, the edges are mostly positive, and the edges between two groups are mostly negative. If the groups form defensive alliances according to our definition given formally below (in Definition 3), then this property is satisfied. Even more relaxed than this is the notion of k-oppositive cohesive groups from (Chu et al., 2016) where only a large intra-group cohesion and a larger inter-group opposition is required. From an algorithmic viewpoint, let us stress that the properties of the groups of vertices that we look for are quite explicit, while most approaches to detecting communities in (signed) networks are based on spectral methods, confer (Cucuringu et al., 2019, 2021; Mercado et al., 2016, 2019; Wang et al., 2022). Our approach is of a purely combinatorial nature. Yet, it would be interesting to contrast this with spectral approaches. We hope that this can inspire some future research. We will now give a number of applications.

1.4 Echo Chambers

With the rise of social networks, some emergent behavior has been studied. The one we are interested in is called echo chambers (Sunstein, 2001; Bessi et al., 2015; Del Vicario et al., 2016). An echo chamber (often also called a bubble) is an environment that brings like-minded people together, with the effect of reinforcing existing beliefs and shielding them from opposing opinions. Even though the existence of echo chambers at a large scale has been questioned and the role that social media plays in those is not fully understood (Ross Arguedas et al., 2022), studies found that on both ends of the political spectrum, small echo chambers exist (Ross Arguedas et al., 2022; Jiang et al., 2021). Echo chambers raise two problems. First, combined with group polarization, this can lead to more extreme beliefs, and can induce a shift from word to action as has been reported in the case of the Incel phenomenon (Saloj arvi et al., 2020). Secondly, those groups are more prone to spreading fake news and are harder to reach. For instance, in the context of diseases like COVID-19, this can be a matter of public health (Jiang et al., 2021). Echo chambers can be described as a group of people that (mostly) share the same beliefs (positive edges) but are hardly exposed to opposing ideas (negative edges) which basically corresponds to our Definition 3 of defensive alliances in signed networks. Hence, automatically detecting (small) echo chambers (alliances) in signed networks, a task that we study in this paper, can be seen as a first step towards solving the problematic consequences observed in this context. Related problems occur in filter bubbles (Amrollahi, 2021; Chen, 2023; Spohr, 2017) and hence our algorithms could be also useful in that context.

Defensive Alliances in Signed Graphs

1. Gaveve 2. Kotuni 3. Ove 4. Alikadzuha 5. Nagamiza 6. Gahuku 7. Masilakidzuha 8. Ukudzuha 9. Notohana 10. Kohika 11. Gehamo 12. Asarodzuha 13. Uheto 14. Seu ve 15. Nagamidzuha 16. Gama

Figure 1: The structure of relationships between different sub-tribes in some mountain area in Papua New Guinea; dashed lines indicate hostility and solid lines friendship. Restricted to the graph consisting of red and blue vertices, these form even (1, 2)- and ( 1, 4)-defensive alliances, respectively. Other stronger alliances, like {7, 8}, have not been observed, possibly, as also {7} or {8} is already a good alliance, so that these sub-tribes do not participate in alliances with others; in contrast, {3, 4} might be more interested in building an alliance together.

1.5 Ethnology

We are now explaining an example from the social science (ethnographic) literature. (Read, 1954) has described the (sub)-tribal structures of some regions in the central highlands of New Guinea. In particular, Figure 1 (adapted from that paper) is derived from two kinds of physical (geographical) connections between these 16 tribes: hina (signalling friendship) and rova (meaning enmity or opposition). Read mentioned that four tribes, among which the Uheto (vertex 13), often form an alliance against four other tribes, among which there are the Gama (16).Both alliances, the one with the Uheto and the one with the Gama, form a defensive alliance as defined in Definition 3 below. They are shown in different colors in Figure 1. More precisely, the Uheto ally with the Notohana, the Kohika and the Seu ve, while the Gama form an alliance with the Nagamidzuha, the Gehamo, and the Gahuku. The Uheto have friendly relationships with all three allies, while (for geographical reasons) the Seu ve only have friendly relationships with the Uheto. The Gama coalition looks weaker in a sense, for instance, the Gama have hina bonds with the Nagamidzuha but rova bonds with both the Gehamo and the Gahuku. A similar situation is found with the Nagamidzuha, only having one enmity relation less. Similarly, the Gehamo and the Gahuku pair up in friendship, while the Gehamo have rova bonds with the other two and the Gahuku only with the Gama for some geographical reasons. Hage and Harary (1983) also looked at this data and found that the graph can be partitioned into three sets that nearly verify being 3-balanced . All these alliances are different from the ones observed by Read and discussed above. Rather, it seems to be that in real life , only smaller alliances are formed, possibly due to difficulties that stone-age cultures faced in highland terrain. These aspects cannot be

Arrighi, Feng, Fernau, Mann, Qi & Wolf

covered by the notions of clusters as proposed and investigated in (Hage & Harary, 1983), as we find negative edges between tribes in one group. Our definition tolerates some frictions within an alliance; this is the key to a formal understanding of such groupings found in real-world social network situations. Read reported that these alliances were stable over time. It would be interesting to detect such social structures not only with hindsight, after studying these groups and their behavior over a long period of time, but to be able to even predict these alliances based on knowledge about the mutual relationships of these tribes. Can we do this algorithmically?

1.6 Politics

Let us underline again that edges in a signed network to be analyzed concerning its alliance structure often reflects some geographic or mental aspects of vicinity. In particular, this models the assumption that allies can only help each other (immediately) when they are neighbored. In modern times, with the advent of rockets, edges can reflect the willingness to help or to attack. Doreian and Mrvar (2015) empirically analyzed the Correlates of War data in the period from 1946 to 1999, based on a signed networks of countries. They showed that the occurrence of negative relationships in international alliances is even unavoidable. The expected trend of network evolution towards a complete balanced state as expressed in (Harary, 1961) is not convincing, even worse, the imbalance dramatically increases over time. Hence, defensive alliance theory appears to be more reasonable as it gives a good explanation on the persistent (and even increasing) existence of negative edges between allies. It could provide a new perspective on how to understand the formation of alliances as appearing in the real world.

The idea of defensive alliances (as formalized above) can be also found in another example from military history. Healy and Stein (1973) looked at several propositions of the multipolar world faced in the European context of the five powers between 1870 and 1881. This expression summarized the leading military powers of that time, which were (in alphabetical order) Austria (the Habsburg Empire), France, Germany, Russia and the United Kingdom. The German Chancellor Bismarck was said to have expressed the political strategic idea that a power would be safe if it was allied with at least two among the other four main powers.1 Notice that this is very much the basic condition of a defensive alliance. Given the fact that Germany had one fixed enemy over that time period (namely, France, after the French-Prussian war), both France and Germany tried to find partners among the other powers. First, Germany managed to build up the 3-emperors-coalition with Austria and Russia, and there were quite some tensions between France and the UK because of their colonies in Africa. After Bismarck left office, the picture gradually changed towards the alliances seen at the beginning of the Great War. This example is also discussed in Chapter 5 of (Easley & Kleinberg, 2010), taking also Italy into account, apart from Austria, France, Germany, Great Britain and Russia. Apart from being a (small) example from history, this also shows a potential application of our algorithmic solutions: namely, that of finding strategic decisions for building alliances. This does not apply only to a military

1. More historical background information is provided in https://de.wikipedia.org/wiki/Bndnispolitik

Otto von Bismarcks.

Defensive Alliances in Signed Graphs

context, but could be also useful, for instance, in the context of companies. We will describe such a scenario in the following paragraph.

1.7 Economics

We can also apply our theory in market economy. Apart from implementing ideas of trust and distrust directly, as suggested by Guha et al. (2004), we can also think of the following scenario, going beyond purely cohesive groups as in (Hiller, 2017). Here, the vertices of a graph represent different companies and positive edges could express tight relations between the companies, often reflected in mutual investments, up to the point where shares are exchanged, while negative edges exist between competitors on a certain market segment, or when companies show a hostile behavior by forcing others into unfavorable contracts. No edges between two companies means that they do not work on the same market segment. Your life as a company is very hard if you are surrounded by many competitors. A survival strategy could be (if money permits) to buy some of the competitors (or, to come to some agreements with them) to alleviate the burden of competition. This explains the interest of companies in some form of alliance building. Such alliances have then not only a defensive character, but can be viewed as monopolies that should, in the first place, be groups that have positive connections (if any). On the other side, consumers and possible (groups of) nations are interested in a working market segment with several competitors. Hence, they are interested in detecting monopolies. In this context, allowing negative edges within a monopoly can also be seen as a way of tolerating misinterpretations on the side of the antitrust regulation authorities, as some links between companies might have been misqualified as hostile. For instance, some buying activities can be a friendly act (supporting another company, or simply strengthening ties) or also an unfriendly act (trying to get a competitor out of the way). If the edge signs are derived by observing these or similar activities of companies, then these could be easily misinterpreted. Applying our model in this context, the hardness results can be interpreted in a way that it is not that easy to find monopolies, in particular in the real world of economy, with many holdings and other interwoven company structures that are hard to analyze.

2. Main Contributions

Our main conceptual contribution is the introduction of a notion of defensive alliance for signed graphs, which has been only defined for unsigned graphs so far. Based on our definition, we investigate several algorithmic questions.

Alliability: Given a signed graph, does there exist a defensive alliance in this graph? Possibly one that contains a prescribed vertex v? While this question has a trivial yes-answer on unsigned graphs, we can prove that even this basic question becomes NP-complete for signed graphs. We complement our finding by exhibiting polynomialtime algorithms for Defensive Alliability on several graph classes.

Defensive Alliance Building: In view of the described hardness, one might wonder if one can turn a given vertex set into a defensive alliance by converting as few enemy relations into friendships as possible. Interestingly, this Defensive Alliance Building problem can be solved in polynomial time.

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Finding Small Alliances: As we show this question to be NP-complete, we investigate aspects of parameterized complexity. We prove that the task of finding smallest alliances remains hard (technically speaking, W[1]-hard) when parameterizing by the solution-size parameter (the intended size of the alliance) or by the treewidth of the underlying graph, but it becomes tractable when parameterized by combined parameters, e.g., treewidth and solution size or treewidth and maximum degree. More importantly, we explain an FPT result when parameterized by signed neighborhood diversity, which is a new structural parameter that we introduce in this paper and that we believe to be useful also for other problems on signed graphs.

Small Alliances in Special Signed Graphs: The hardness results motivate us to study smallest defensive alliances in several classes of signed graphs, where we can get a good combinatorial understanding. Particularly interesting are balanced graphs, as they relate to important network analysis questions like correlation clustering.

From a practical perspective, these questions can be well motivated, for instance as follows: Having understood the positive or negative relationships in a network of tribes, it would be interesting to know if one can expect to find alliances among these tribes, leading to the question of Defensive Alliability. Related to this is the question to find a small group of tribes (possibly including a chosen tribe) that forms an alliance. If no alliance can be found, then it might be an idea to ask for diplomatic activities that might change the positive or negative preconditions so that a certain group can form an alliance (Defensive Alliance Building). To give an example on a larger scale, without building up the German-French friendship in Europe after WW2, the formation of the European Union would be hardly imaginable. In the following, we will first present the necessary concepts formally. Then, we exhibit some combinatorial studies of these concepts, before introducing some algorithmic problems formally and finally discussing their complexity.

3. Formal Concept Definitions

We assume some basic knowledge in classical graph theory on the side of the reader. An (unsigned) graph G can be specified as a tuple (V, E), where V is the vertex set and E the edge set of G. More formally, E V 2 , i.e., each edge is a two-element subset of V . G = (V , E ) is a subgraph of G = (V, E) if and only if V V and E E; it is an induced subgraph, also denoted as G[V ], if E = E V 2 . Here, we give a list of basic concepts from classical graph theory which are used in our paper. A graph is said to be embeddable in the plane, or planar, if it can be drawn in the plane such that its edges, represented as continuous curves in the plane, intersect only at their endpoints. A graph G is chordal if it has a chord for every cycle of length no less than four. A clique of a graph G is a complete induced subgraph of G. A vertex cover C of a graph G is a subset of vertices of G such that every edge of G has at least one endpoint in C. The vertex cover number of G is the size of the smallest vertex cover for G. An Independent Set of a graph G is a subset of vertices such that no two vertices in the subset are adjacent. Clearly, the complementary set of a vertex cover set is an independent set.

Defensive Alliances in Signed Graphs

Definition 1. A tree decomposition of a graph G is a pair T = (T, {Xt}t V (T)), where T is a tree whose node t is assigned a vertex subset Xt V (G), called a bag, satisfying the following:

1) S t V (T) Xt = V (G);

2) for each edge uv E(G), there is some node t of T such that u Xt, v Xt;

3) for each u V (G), the set Tu = {t V (T) | u Xt} induces a subtree of T.

The width of tree decomposition T is given by maxt V (T) |Xt| 1. The treewidth of a graph G is the minimum width over all tree decompositions of G. For the sake of designing algorithms, it is convenient to work with nice tree decompositions. A nice tree decomposition can easily be obtained from a given tree decomposition with the same width and a linear number of vertices (Cygan et al., 2015).

Definition 2. A nice tree decomposition T = (T, {Xt}t V (T)) is a tree decomposition if each node t V (T) falls into one of the following categories:

1) Leaf node: t is a leaf node of T and Xt = ;

2) Introduce node: t has exactly one child t such that Xt = Xt {v} for some v / Xt ;

3) Forget node: t has exactly one child t such that Xt = Xt \ {v} for some v Xt ;

4) Join node: t has exactly two children t and t such that Xt = Xt = Xt .

A signed network is a triple G = (V, E+, E ), where V is a finite set of vertices and E+ V 2 is the positive edge set and E V 2 , with E+ E = , is the negative edge set. We call G0 = (V, E+ E ) the underlying (unsigned) graph of G. For v V , the set N+(v) = {u V | uv E+} collects the positive neighbors and N (v) = {u V | uv E } collects the negative neighbors of v. Accordingly, deg+(v) = |N+(v)| and deg (v) = |N (v)| denote the positive and negative degree of vertex v, respectively. We use subscripts to restrict the considered neighborhood to a subset of vertices. For instance, if X V , then N+ X(v) = N+(v) X and deg+ X(v) = |N+ X(v)|. Similarly to the unsigned case, we use δ (G) (or δ+(G)) to denote the smallest negative (respectively, positive) degree in G. If X V , then we denote by X = V \ X the complement of X with respect to V . As in the unsigned case, we also define the induced signed graph G[X] := (X, {uv E+ | u, v X}, {uv E | u, v X}). We distinguish between friend and enemy relationships and define a (k1, k2)-defensive alliance of a signed network as follows.

Definition 3. Let k1, k2 be integers. A non-empty set S of vertices of a signed network G = (V, E+, E ) is called a (k1, k2)-defensive alliance if and only if :

1. v S : deg+ S (v) deg S (v) + k1 and

2. v S : deg+ S (v) deg

S (v) + k2.

Arrighi, Feng, Fernau, Mann, Qi & Wolf

(a) Unsigned graph: {v5, v6} is a minimum ( 1)-defensive alliance of size 2; {v1, v2, v3} is a ( 1)-defensive alliance of size 3.

(b) Signed graph: {v6} is a minimum ( 1, 1)- defensive alliance; {v1, v3} is a ( 1, 1)- defensive alliance of size 2; {v1, v2, v3} is no longer a ( 1, 1)-defensive alliance.

Figure 2: Defensive alliances on unsigned versus signed graphs, where dashed or solid lines mean negative or positive edges, respectively.

The first condition expresses that, within an alliance, there should be more friends than natural enemies for each member of the alliance. This models a certain level of alliance stability, where k1 offers some flexibility of this model: a larger k1 prevents an alliance from being over-stretched by internal conflicts and rather makes sure that solidarity within the alliance is strong enough so that natural enemies within an alliance are at least staying neutral in case of an external attack. The second condition is taken over from the traditional model of k-defensive alliance in an unsigned graph. It expresses that each member of an alliance should have more defenders from within the alliance than it has enemies outside the alliance and the parameter k2 allows to tune the level of defensiveness of the alliance. Notice that natural friends outside the alliance are considered harmless and will not participate in attacks, or more explicitly, they are not counted in and are expected to stay neutral, as (if the first condition is met) also natural enemies within the alliance are expected to stay neutral. Both conditions together can also be interpreted as a signed analogue to the idea to maximize the minimum degree within a community, as proposed (e.g.) in (Sozio & Gionis, 2010). We illustrate these concepts in Figure 1. For simplicity and without ambiguity, we refer to it simply as defensive alliances, or DA for short, a concept that is illustrated in the simple example in Figure 2. Following the notation introduced for unsigned graphs in (Kristiansen et al., 2004; Shafique, 2004), we will denote the size of the smallest defensive alliance in G by asd(G). The index sd reminds us that we work on signed graphs and consider defensive alliances. We will also look into special classes of signed graphs. Often, these are defined via properties of the underlying unsigned graph, for instance, the classes of signed paths, cycles, subcubic, or complete graphs. But there are also very interesting classes of signed graphs that have no counterpart from the unsigned perspective. Cartwright and Harary (1956) defined that a signed graph is balanced if each of its cycles contains an even number of negative edges. Davis (1967) extended this notion; he called a signed graph a clustering or weakly balanced if there are no cycles in the graph with exactly one negative edge. He presented the following characterization: a signed graph is weakly balanced if and only if its vertices can be split into k 1 groups (clusters) such that edges connecting vertices within groups are positive and edges connecting vertices of different groups are negative. Such a signed graph is also called k-balanced. In other words, in a k-balanced signed graph G = (V, E+, E ),

Defensive Alliances in Signed Graphs

the positive graph G+ = (V, E+) contains at least k k connected components C1, . . . , Ck (that are not necessarily cliques), while the negative graph G = (V, E ) is k-colorable, such that each of the k color classes can be formed by the union of some of the vertex sets C1, . . . , Ck . These color classes correspond to the groups of the k-balanced partition of G. Davis also showed that a complete signed graph is weakly balanced if and only if none of its triangles has exactly one negative edge. How to partition a complete signed graph best possible to a clustering partitioning has been investigated extensively since the publication of the ground-breaking paper on Correlation Clustering by Bansal et al. (2004), being equivalent to Cluster Editing on unsigned graphs, but clearly extendible towards non-complete signed graphs.

4. Combinatorial Prelude

In the remainder of the paper, mostly to avoid too clumsy notation, we focus on the case of ( 1, 1)-defensive alliances. We begin by discussing some observations on the size of a smallest defensive alliance asd before we continue with more algorithmic results, as this also shows some structural insights. By the definitions and a chain of inequalities, we obtain our first result:

Lemma 1. If a vertex v is in a defensive alliance, then deg+(v) + 1 l deg (v)

Proof. For any vertex v S,

deg+(v) + 1 deg+ S (v) + 1

max{deg S (v), deg

This simple lemma already has a nice consequence for finding alliances of size at most k.

Corollary 2. If there is a vertex v with deg (v) k+1 in a signed graph G, then v cannot be in any defensive alliance of size at most k in G.

Next, we give characterizations of small defensive alliance numbers for signed graphs. For the unsigned case, Propositions 1 and 3 in (Kristiansen et al., 2004) describe similar characterizations.

Theorem 3. Let G be a signed graph. Then,

1) asd(G) = 1 if and only if v V (G) : deg (v) 1.

2) asd(G) = 2 if and only if δ (G) 2 and there exist two adjacent vertices v, u V (G) : deg (v) = deg (u) = 2.

Proof. ad 1) Obviously, a vertex v can defend itself if and only if deg (v) 1. ad 2) Except for the case of asd(G) = 1, we know the minimum negative degree of G is at least 2. Assume

Arrighi, Feng, Fernau, Mann, Qi & Wolf

that we have a defensive alliance S consisting of two vertices v, u V (G). Case one is that v, u are connected positively, then for each vertex, there are at most two negative connections outside of S; Case two is that v, u are connected negatively, then for each vertex, there is at most one negative connection outside of S. Combined with δ (G) 2, we conclude that the negative degree of v, u is exactly 2, regardless of whether they are positively or negatively connected. For the converse direction, if δ (G) 2, then from 1) we know asd(G) 2. We can verify that any two adjacent vertices v, u V (G) with deg (v) = deg (u) = 2 can form a defensive alliance, so that asd(G) = 2.

From these combinatorial results, we can conclude the following for signed trees, paths and cycles, keeping in mind that any leaf in a tree forms a minimum defensive alliance.

Corollary 4. For any signed tree graph T, in particular for paths, asd(T) = 1.

Corollary 5. For any signed cycle graph C, if there exists a positive edge, then asd(C) = 1; otherwise, asd(C) = 2.

Corollary 4 clearly also extends to forests, but more interestingly, we can also extend Corollary 5. Recall that a graph is unicyclic if it contains exactly one cycle as a subgraph.

Corollary 6. Let G be a unicyclic signed graph. Then, asd(G) 2. Moreover, asd(G) = 2 if and only if G is a cycle without a positive edge.

Proof. If G is unicyclic but δ(G) = 1, then any vertex of degree one forms a defensive alliance. If G is unicyclic but δ(G) > 1, then G must be a cycle, so that the previous corollary applies.

Signed graph with maximum degree at most three are called signed subcubic graphs.

Theorem 7. There is a polynomial-time algorithm that decides alliability of any signed subcubic graph G and if so, it determines asd(G).

We formulate this theorem in an algorithmic fashion, but its proof mainly gives combinatorial insights.

Proof. Let G = (V, E+, E ) be a signed subcubic graph. First, we can see if any single vertex forms a defensive alliance on its own. This is the case in particular if G contains a vertex of degree one, but the general condition is stated in Theorem 3. Similarly, we can check if two adjacent vertices form a defensive alliance, as also specified in Theorem 3 as a combinatorial condition. Now, two cases remain. If δ (G) = 3, this means that the graph is 3-regular and all its edges are negative, i.e., +(G) = 0. Then, G does not possess a defensive alliance by Lemma 1. If δ (G) = 2, we know by assuming asd(G) > 2 that adjacent vertices u, v never satisfy deg (v) = deg (u) = 2, but min{deg (u), deg (v)} 2. Assume that asd(G) > 2 and that u S for some hypothetical defensive alliance S. Then, deg (u) = 2 and (at best) deg+(u) = 1. However, now all neighbors v of u must satisfy deg (v) = 3, i.e., v / S, so that we can conclude that such an alliance S does not exist.

Corollary 8. If a subcubic graph possesses any defensive alliance D, then its size |D| is at most 2.

Defensive Alliances in Signed Graphs

Let us mention that later, we are showing that deciding alliability in signed graphs of maximum degree five is already NP-hard. The following structural observation is sometimes helpful:

Proposition 9. If S is a minimum-size defensive alliance in G = (V, E+, E ), then S is connected in the underlying unsigned graph G0 = (V, E+ E ).

Proof. Let S be a minimum-size defensive alliance in G = (V, E+, E ). Let S S be a connected component of the induced graph G0[S]. Consider some v S . As S is a connected component, within G we find deg+ S (v) = deg+ S (v), deg S (v) = deg S (v) and deg

S (v) = deg

S (v). Hence, because S is a defensive alliance, S must be also a defensive alliance. As S is a minimum-size defensive alliance, S = S follows. Therefore, S is connected in G0.

As can be seen by the previous proof, we can generalize the statement of Proposition 9 by requiring an inclusion-minimal defensive alliance S instead of a minimum-size one. Hence, when looking for a DA S of size at most k, we can assume that the diameter of G0[S] is at most k 1. As mentioned above, balancedness is an important notion in signed networks, in particular in connection with complete graphs. Hence, the next theorem is an interesting and important combinatorial result. This also means that we can determine asd(G) for any weakly balanced signed complete graph G in polynomial time.

Theorem 10. For any signed complete graph G = (V, E+, E ), n = |V |, with E = , we can determine its defensive alliance number asd(G) in the following cases.

1) If G is balanced with partition (V1, V2), where |V1| |V2|, then asd(G) = |V2|. Moreover, any subset S V1 with |S| = |V2| is a minimum defensive alliance.

2) If G is k-balanced with partition (V1, V2, . . . , Vk), where |V1| |V2| . . . |Vk|, then we find:

i) If |V1| n

3 and |V2| n

3 , then asd(G) = 2 l n |V2|

2 m . Any subset S1 of V1 and any

subset S2 of V2 with |S1| = |S2| = l n |V2|

2 m forms a minimum DA.

ii) If |V1| n

2 , then asd(G) = n |V1|. Any subset S of V1 with |S| = n |V1| is a minimum DA.

iii) Otherwise, there is no defensive alliance at all.

Proof. As 1) is obviously a special case of 2), we only consider k-balanced complete signed graphs in the following. Slightly abusing notation, we will denote the cluster Vi to which x V belongs as Vx. Suppose that the nonempty subset S V is a defensive alliance, and for all x S, let V x denote the subset of S which includes the vertices that are from the same partition part as x, i.e., V x = S Vx. By definition of a defensive alliance, we have, for any x S, a) deg+ S (x) + 1 = |V x| deg S (x) = |S| |V x| and b) deg+ S (x) + 1 = |V x| deg

S (x) = n |S| |Vx| + |V x|. So, for all x S, 2|Vx| 2|V x| n |Vx|, i.e., |Vx| n

3 . Hence, vertices in S are from at most three different partition parts. We have to discuss

Arrighi, Feng, Fernau, Mann, Qi & Wolf

the situation S = V 1 V 2 V 3, where V 1 V1, V 2 V2, and V 3 V3. We further know that |V1| |V2| |V3| n

3 . The following discussion shows the subcases i), ii) and iii) of 2) as in the statement of the theorem by distinguishing whether there are three, two or one non-empty subset(s) of the form V x.

Case one: Should we have three non-empty parts V 1, V 2, V 3, then V3 = and hence |V1| = |V2| = |V3| = n

3 . From a) above, |V 1| |V 2| + |V 3|, |V 2| |V 1| + |V 3|, and |V 3| |V 1| + |V 2|. So we have |V 1| = |V 2| = |V 3| = 0, that is to say, there is no such defensive alliance. This corresponds to part 2)iii).

Case two: S = V 1 V 2 with V 2 = . We know |V1| |V2| n

3 . From a) above, we know |V 1| |S| |V 1| = |V 2| and |V 2| |S| |V 2| = |V 1|, i.e., |V 1| = |V 2|. From b) above, |V 2| n |V2| |V 1|. Hence, |S| = |V 1| + |V 2| n |V2|. On the other side, one can

verify that any subset V 1 of V1 and any subset V 2 of V2 with |V 1| = |V 2| = l n |V2|

2 m forms a defensive alliance. This corresponds to part 2)i).

Case three: S = V 1 V1. From b) above, |V 1| n |V1|. Trivially, |V1| |V 1|. Hence, |V1| n 2 and |S| n |V1|. Similarly, we can verify that any subset V 1 of |V1| with |V 1| = n |V1| is a defensive alliance. This corresponds to part 2)ii).

This result also shows the similarities between the notion of a defensive alliance and that of a clustering: A DA is often a cluster, or if not, it is stretching over at most two of them.

5. Formal Problem Definitions

We are now formally defining the decision version of the problems that we consider in this paper. As we will show NP-hardness of the first two problems, most of the following algorithmic research is devoted to finding solutions in special situations, also employing the toolbox of parameterized algorithms.

Defensive (Pointed) Alliability (Def(P)All) Input: A signed network G (and a vertex v) Problem: Is there a DA in G (containing v)?

Minimum Defensive Alliance (Min Def All) Input: A signed network G and an integer k 0 Problem: Is there a DA in G of size at most k?

In the spirit of Correlation Clustering, we are also discussing edge flips. More formally, let G = (V, E+, E ) be a signed graph. For a set T E = E+ E , let GT be the signed graph obtained after flipping the edges of G in T, i.e., GT = (V, E+ T, E T), where denotes the symmetric set difference. Now, Correlation Clustering could be defined as the question to decide, given G and k, if some edge set T exists, |T| k, such that GT is weakly balanced. This question is also known to be NP-complete, see (Bansal et al., 2004). By the mentioned NP-hardness result of Defensive Alliability, this would be also true for the question to flip at most k edges to make the graph alliable. However,

Defensive Alliances in Signed Graphs

the following question, whose clustering variant is trivial, is an interesting variation in the context of alliances as we will present a non-trivial algorithm solving it below.

Defensive Alliance Building (Def All Build) Input: A signed network G = (V, E+, E ), a vertex set D and an integer k 0 Problem: Is there a T E = E+ E of size at most k such that D is a DA in GT ?

In other words, we ask if one can flip k edge signs in G so that D becomes a DA. This problem can be motivated by thinking of D as an ideal alliance, which basically has to be built by creating friendly relationships out of previously unfriendly ones. In other words, we might want to turn a specific group of countries or people into a defensive alliance and we want to know how much we have to pay for it.

6. Alliability

It is possible that no defensive alliance exists in a signed network. As an extreme example, consider any signed network with only negative edges and minimum degree at least 3. So we first consider the existence of defensive alliance in signed networks, which is called Defensive (pointed) Alliability. As already discussed above, the question of alliability makes no sense for the unsigned counterpart as they are trivial, while, surprinsingly, we obtain hardness results for the signed versions.

Theorem 11. Def PAll and Def All are NP-complete.

The reduction is based on the NP-hardness of a well-known variation of the Satisfiability problem, namely NAE-3SAT, see (Schaefer, 1978). According to Schaeffer, NAE-3SAT can be defined as a coloring problem as follows:

Not-All-Equal 3-Satisfiability (NAE-3SAT) Input: A base set X, a collection of sets C1, . . . , Cm X, each having at most three members Problem: Is there a mapping A : X {0, 1} such that A(Ci) = {0, 1} for all 1 i m?

From the coloring point of view, this means that X is colored with two colors such that no set Ci is all one color. From the logical perspective, we can think of X being a set of variables and the coloring being an assignment of the truth values 1 (or true) and 0 (or false). Notice that in Schaeffer s definition, all clauses are monotone, more precisely, all literals are positive, but clearly the problem will not become easier if negative literals are allowed.

Proof. For a signed network G = (V, E+, E ), obviously, Defensive (Pointed) Alliability is in NP, by checking the two defensive conditions of every vertex in a solution S, which runs in polynomial time O(|S|2(|E+| + |E |)).

Arrighi, Feng, Fernau, Mann, Qi & Wolf

We complete our proof, showing NP-hardness by reducing from NAE-3SAT, formulated in its logic version. Let ϕ = C1 Cm be a boolean formula with variable set X (with |X| = n) in which each clause Ci includes exactly 3 positive literals. The question is whether there exists a satisfying assignment such that in each clause there is a literal assigned to false. We are going to describe a signed graph G = (V, E+, E ), where V may contain a special vertex v in the pointed variation of our problem. We first define some auxiliary clique structures. Define NCv = (Vv, , E v ), which is is a negative clique with m + 2 many vertices, containing the possibly special vertex v, as well as NCx,i = (Vx,i, , E x,i), with x X and i N+, which is a negative clique with four vertices; both types of negative cliques serve as not-in-the-solution gadgets, differentiated as big and small, respectively. More technically, we can put Vx,i := {xi,1, xi,2, xi,3, xi,4}. For each variable x in X, we define

C(x) = Cj1, . . . , Cjnx | x Cji, i {1, . . . , nx}, ji {1, . . . , m} , i.e.,

nx is the number of clauses that contain the variable x, and

X (x) := xh | h {1, . . . , 2nx} .

Then we construct the reduction R( ϕ ) :=

1) Build a signed graph G = (V, E+, E ) as follows, which is also shown in Figure 3:

V = Vv {cj | j {1, . . . , m}} [

l {1,...,4nx} Vx,l

E+ = {vcj | j {1, . . . , m}} x2p 1x2p | p {1, . . . , nx}, x X

l {1,...,4nx} E x,l

cjpx2p | p {1, . . . , nx}, Cjp C(x) !

x2px2p+1, x2nxx1 | x X, p {1, . . . , nx 1} x2p 1x4p 3,1, x2p 1x4p 2,1, x2px4p 1,1, x2px4p,1 | x X, p {1, . . . , nx}

2) Return G, v or just G if we talk about Def All.

If ϕ = C1 Cm is a yes-instance of NAE-3SAT, where Ci = xi1 xi2 xi3, xij X and i {1, . . . , m}, j {1, 2, 3}, then there exists a satisfying assignment A for the variables X such that, for each Ci, there are j1, j2 {1, 2, 3} such that xij1 = 1 and xij2 = 0. Let S = {x X | A(x) = 0}. We use the assignment A to show that G possesses a defensive alliance D containing the vertex v:

D := {v} ci | i {1, . . . , m} [

We have to check the two defensive alliance conditions for each vertex in this set D. For the vertex v fixed to be in D,

1. deg+ D(v) + 1 = m + 1 > 0 = deg D(v), and

Defensive Alliances in Signed Graphs

(a) Variable gadget: the squares represent small not-in-the-solution gadgets.

(b) Clause gadget: the diamond is vertex v. (c) A small not-in-the-solution gadget.

Figure 3: Reduction construction for Theorem 11.

2. deg+ D(v) + 1 = m + 1 = deg

Consider any ci for 1 i m. Observe that deg D(ci) = deg SX(ci), with SX = S x S X (x), so that deg D(ci) {1, 2}, as otherwise the NAE-assignment A that determines S would set all variables in Ci either to 0 or to 1, a contradiction. Similarly, deg

D(ci) = deg S X(ci), with

S X = S x X\S X (x), so that again deg

D {1, 2}. Hence, 1) deg+ D(ci) + 1 = 2 deg D(ci); 2) deg+ D(ci) + 1 = 2 deg

D(ci). For each vertex xh D associated to x X, 1) deg+ D(xh) + 1 = 2 deg D(xh); 2) deg+ D(xh) + 1 = 2 = deg

D(xh). Therefore, D is a defensive alliance which contains the vertex v. Let D be a defensive alliance containing vertex v of the signed graph obtained from R( ϕ ). First observe that the not-in-the-solution gadgets deserve their name, i.e., D Vv S x X,l {1,...,4nx} Vx,l = . In order to defend vertex v, all of its positive neighbors

must be in D, i.e., cj | j {1, . . . , m} D . For each vertex ci D, at least one of its

Arrighi, Feng, Fernau, Mann, Qi & Wolf

negative neighbors should be in D, and at least one of its negative neighbors should not be in D, because ci has exactly one positive neighbor, which is v. Then assume that there is some x2p D. As its two negative neighbors x4p 1,1, x4p,1 are in small not-in-the-solution gadgets, x4p 1,1, x4p,1 / D, we know that the other two negative neighbors x2p 1, x2p+1 must belong to D, as only (possibly) the positive neighbor cjp can defend x2p; but it also must defend it, so that cjp D is enforced. The case of x2p+1 D is very similar (including the boundary case of x1). Now, the vertex has degree four and negative degree three. As two of its negative neighbors belong to small not-in-the-solution gadgets, both the negative and the positive remaining neighbors must belong to D, as well, bringing us back to the previous case. Hence, we see that xh D for some h {1, . . . , 2nx} if and only if xh D for all h {1, . . . , 2nx}. In other words, for each x X, X (x) D or X (x) D = . If X (x) D, then for the set of clause vertices c(x) that correspond to the set of clauses C(x), c(x) D. Then we can obtain a satisfying assignment A for ϕ by assigning the value 1, i.e., true, to x X if X (x) D or the value 0, i.e., false, to x if X (x) D = . Therefore, A is a satisfying assignment for ϕ, whose values in each clause are not all equal to each other. Furthermore, without the fixed vertex v, if ci D, then v D, because v is the only positive neighbor of each ci. If some x2p D, according to the above, we know that the corresponding set c(x) of clause vertices satisfies c(x) D, so that v D. It is easy to see that the described procedure for building R( ϕ ) from ϕ can be executed in polynomial time. Consequently, both Def PAll and Def All are NP-complete.

By analyzing the previous proof again more carefully, and taking the notation from that proof, we find:

Lemma 12. The constructed signed graph G has at most 56m + 1 many vertices.

Proof. Let us analyze the parts of the vertex set V of G one-by-one.

|Vv| = m + 2 by definition.

|{cj | j {1, . . . , m}}| = m by definition.

S x X X (x) = P x X 2nx 6m by double-counting, as each clause contains at most 3 literals and nx is the number of clauses in which variable x occurs.

Similarly, S x X S l {1,...,4nx} Vx,l = P x X 16nx = 48m.

Altogether, 56m + 2 = (m + 2) + m + 6m + 48m as claimed.

This (simple) analysis is important, as we like to deduce some further consequences from our designed reduction, looking at it from a fine-grained complexity perspective. To this end, we need a similar analysis concerning the hardness of NAE-3SAT. As we did not find any explicit reference for this in the literature, we provide it in the following.

Theorem 13. Given an instance I = (X, C) of 3SAT, with n = |X| variables and m = |C| clauses, one can construct in polynomial time an instance I = (X , C ) of NAE-3SAT, with n = |X | and m = |C | such that I is satisfiable if and only if I has a solution and such that n = O(n + m) and m = O(n + m).

Defensive Alliances in Signed Graphs

Proof. The claimed reduction is similar to the one indicated in https://en.wikipedia.org/ wiki/Not-all-equal 3-satisfiability. For the given 3SAT-instance I = (X, C), we can assume that all clauses in C contain three literals and that no variable occurs twice in any clause. Let L(X) = {x, x | x X} be the set of literals of I. Further, assume that we have arbitrarily fixed an ordering on the literals in L(C) for each C C, defining three mappings L1, L2, L3 : C L(X). We construct I = (X , C ) as follows:

X := X {ˆx | x X} {s} {x C, ˆx C | C C}. Define the injection f : L(x) X by x 7 x and x 7 ˆx for each x X.

C := {f(L1(C)), f(L2(C)), x C}, {ˆx C, f(L3(C)), s}, {x C, ˆx C} | C C {x, ˆx} | x X .

First, assume that A : X {0, 1} is a satisfying assignment for I. Then A is extended to A : X {0, 1} by letting A (x) = A(x) for x X, A (ˆx) = A(x) (flipping 0 to 1 and 1 to 0), while A (x C) = 1 and A (ˆx C) = 0 if and only if A(L1(C)) = A(L2(C)) = 0 for all C C and A (s) = 1. Observe that for each C C , one of its variables is set to 0 and another one is set to 1. Conversely, if A : X {0, 1} is a not-all-equal assignment of I , then observe that the assignment A : X {0, 1} that flips all variables in comparison with A , i.e., A (x) = (A (x)), is also a not-all-equal assignment of I . Hence, we can assume, w.l.o.g., that A (s) = 0. Let A : X {0, 1} be simply the restriction of A to X. Our setting guarantees that, for each c C, by observing the clause {ˆx C, f(L3(C)), s}, either (1) A (ˆx C) = 1 and hence A (x C) = 0 due to the clause {x C, ˆx C}, or (2) A (f(L3(C))) = 1, so that C is satisfied immediately. In case (1), by observing the clause {f(L1(C)), f(L2(C)), x C}, either A (f(L1(C))) = 1 or A (f(L2(C))) = 1, i.e., the described assignment for I indeed satisfies each C C.

This result allows us to deduce some lower bounds for solvers of monotone NAE-3SAT instances, based on the Exponential-Time Hypothesis (ETH).

Corollary 14. Unless ETH breaks, there is no algorithm solving monotone NAE-3SAT instances with n variables and m clauses in time O 2o(n+m) .

As a further excursion into interesting variants of NAE-SAT, let us make some more observations. Notice that we could also change the construction slightly by replacing all clauses {x, ˆx} of size 2 by the following gadget consisting of 6 clauses (compare Darmann and D ocker (2020)):

NE(x, ˆx) = x, ˆx, y}, {x, ˆx, z}, {v, y, z}, {w, y, z}, {u, v, w} .

In this way, we get an equivalent NAE-3SAT formula, again with O(n+m) many variables and clauses. Even more, both constructions shown in (Darmann & D ocker, 2020) prove that also for the restriction NAE-3SAT-E4 where each clause is monotone and contains three variables and every variable occurs exactly four times, we finally obtain O(n + m) many variables and clauses, so that we can conclude the following stronger ETH result.

Corollary 15. Unless ETH breaks, there is no algorithm solving monotone NAE-3SATE4 instances with n variables and m clauses in time O 2o(n+m) .

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Let us now return to our main theme, which is defensive alliances. Our considerations also allow us to deduce some impossibility results based on the famous Exponential-Time Hypothesis (ETH), see (Impagliazzo et al., 2001).

Corollary 16. Assuming ETH, there is no O(2o(n))-time algorithm for solving Def(P)Allinstances with n vertices.

We can complement our finding by exhibiting polynomial-time algorithms for Def(P)All on some graph classes. Above, we already looked at subcubic and weakly balanced signed graphs. We will look into structural parameters like bounded signed neighborhood diversity or treewidth, also combined with other parameters, later.

7. Building Defensive Alliances

We turn to the task of building an alliance by flipping edges. With a sequence of lemmas, we will prove the following main result of this section.

Theorem 17. Defensive Alliance Building can be solved in polynomial time.

In our algorithm, we will make use of the problem Upper Degree-Constrained Subgraph (for short: UDCS). An instance of UDCS is given by an unsigned graph G = (V, E) and an upper bound uv N for each v V . The task is to find a subgraph H with maximum number of edges, such that for each vertex v V , deg H(v) uv. This problem was introduced by (Gabow, 1983) where the author showed that this problem is solvable in time O p P v V uv |E| . We now describe our algorithm, working on an instance (G, D, k) of Defensive Alliance Building, i.e., G = (V, E+, E ) is a signed graph, D V and k 0. First, we apply the following reduction rule: If there exists a v D with zv := deg G,D(v)

deg+ G,D(v) deg G,D(v) 1 0, then set T = {vx | x N D(v)} and add zv edges from {vx | x N

D(v)} to T, which is part of the solution that we build in the sense of the following correctness assertion, where GT = (V, E+ T, E T):

Lemma 18. G, D, k is a yes-instance of Defensive Alliance Building if and only if GT , D, k is one, with k = k zv deg G,D(v) = k (deg G,D(v) deg+ G,D).

Proof. This lemma can be shown by induction by using the following claim:

Claim 19. Let v D and T E be a solution of the Defensive Alliance Building instance (G, D, k) such that there exist edges vx E \ T and vy E T with x D and y / D. Then T := (T {vx}) \ {vy} is also a solution.

Proof. Let u D \ {v}. So, deg+ GT ,D(u) deg+ GT ,D(u), deg GT ,D(u) deg GT ,D(u) (with equality if u = x) and deg GT ,D(u) = deg GT ,D(u). Since deg+ GT D(v) = deg+ GT ,D(v) + 1 and

deg GT ,D(v) = deg GT ,D(v) + 1, as well as deg GT ,D(v) = deg GT ,D(v) 1, D is a defensive alliance of GT , just as it was of GT .

Applying this claim zv times proves the lemma.

Defensive Alliances in Signed Graphs

From now on, each v D fulfills

deg+ G,D(v) + deg G,D(v) > deg G,D(v) .

Hence, a solution includes only negative edges in the induced signed graph G[D]. For the algorithm, we define B := {v D | deg+ G,D(v)+1 < max{deg G,D(v), deg G,D(v))}, collecting those vertices from D that violate DA conditions. In order to quantify this violation, set b(v) := 0 if v / B and b(v) := max{b1(v), b2(v)} if v B, where

b1(v) := deg G,D(v) deg+ G,D(v) 1,

& deg G,D(v) deg+ G,D(v) 1

We run the polynomial-time algorithm for UDCS on the unsigned graph G := (V, E ) with uv := b(v). Let H = (V, T ) be the subgraph which is returned by this algorithm. Clearly, T only includes edges between vertices in B and, for each v B with deg H (v) < b(v) and each u NG ,B(v) = N G,B(v), deg H (u) = b(u). Otherwise, H would not be maximal. Now, let T := T and H := H ; for v B with deg H(v) < b(v), add edges vx E \ T, with x D if possible, to H and T until equality holds. This implies |T \ T | = |T| |T | = P v B b(v) deg H (v).

Lemma 20. T has minimum cardinality such that D is a defensive alliance of GT = (V, E+ T, E T).

Proof. First of all, we show that D is a defensive alliance of GT . Clearly, T E . Therefore, for each v D \ B,

deg+ GT ,D(v) + 1 deg+ G,D(v) + 1 max{deg G,D(v), deg G,D(v)}

max{deg GT ,D(v), deg GT ,D(v)} .

Let v B. Since T includes at least b(v) edges incident to v with two endpoints in D, deg GT ,D(v) = deg G,D(v) deg+ G,D(v) + b(v) + 1 deg+ GT ,D(v) + 1 and deg GT ,D(v)

deg G,D(v) b(v) deg+ G,D(v) + b(v) + 1 deg+ GT ,D(v) + 1. Thus, D is a defensive alliance. Let T E be of minimum cardinality such that D is a defensive alliance of GT . Assume there exists a v B with |{vx E | vx T }| < b(v). We will show that this assumption leads to a contradiction to the fact that D is a defensive alliance of GT . Case 1: If b(v) = deg G,D(v) deg+ G,D(v) 1, then

deg GT ,D(v) = deg G,D(v) = deg+ G,D(v) + 1 + b(v) > deg+ GT ,D(v) + 1 .

Case 2: For b(v) = deg G,D(v) deg+ G,D(v) 1 2 , we have

deg GT ,D(v) > deg G,D(v) b(v) = b(v) + deg+ G,D(v) + 1 > deg+ GT ,D(v) + 1 .

The case b(v) = deg G,D(v) deg+ G,D(v) 1 2 implies

deg GT ,D(v) > deg G,D(v) b(v) = b(v) + deg+ G,D(v) deg+ GT ,D(v) + 1 .

Arrighi, Feng, Fernau, Mann, Qi & Wolf

As each case contradicts the fact that D is a defensive alliance on GT , we conclude that |{vx E | vx T }| b(v) for each v B. Let e H := V, e T be the output of the UDCS algorithm on e G = (V, T ) with the bounds

from above. Since e G is a subgraph of G, | e T| |T |. Since e T is maximal, adding an edge to e T would increase deg e H,V (v) for at most on v B with b(v) deg e H,V (v). Therefore, we

need to add at least P v B b(v) deg e H(v) many edges to e T to obtain T . Moreover,

|T | | e T| = |T \ e T| X

b(v) deg e H(v) = X

v B (b(v) deg H (v)) X

deg e H(v) deg H (v) .

By the sentence before the lemma and by the famous handshake lemma, we observe

|T | | e T| |T| |T | 2 | e T| |T | = |T| + |T | | e T| | e T| |T| | e T|

Thus, |T| |T |.

We still have to analyze the running time. The exhaustive employment of the reduction rule runs in time O |V |2 . The condition b(v) deg G(v) |V | can be calculated in linear

time for all v V . Furthermore, the UDCS-algorithm runs in time O p

|V | |E| . Adding the vertices in the end runs in linear time with respect to the number of edges. Therefore, overall the algorithm runs in time O |V |2 + p

8. Minimum Defensive Alliances

We now describe a formal link between Minimum Defensive Alliance in unsigned and signed graphs; we describe this in the form of a reduction from Minimum Defensive Alliance on unsigned graphs. This allows us to transfer hardness results known for unsigned graphs to the case of signed graphs.

Theorem 21. There is a polynomial-time transformation that, given an unsigned graph G, produces a signed graph G such that a vertex set A is a defensive alliance in G if and only if it is a defensive alliance in G .

Proof. Let G = (V, E) be an unsigned graph and k N. For v V , define d (v) := l deg(v)+1

2 m , as well as a new set of vertices Mv := {vi,j | i {1, . . . , d (v)}, j {1, 2, 3, 4} }.

We construct a signed graph G = (V , E +, E ) with

v V Mv, E + := E, and

E := {v, vi,1}, {vi,j, vi,ℓ} | v V, i {1, . . . , d (v)}, j, ℓ {1, 2, 3, 4}, j = ℓ .

In other words, the only positive edges of G are inherited from G, and the unsigned graph (V , E ) is subgraph of a split graph, with V V forming an independent set and V \ V forming a collection of cliques. Since deg (vi,j) 3 and deg+(vi,j) = 0 for all i {1, . . . , d (v)} and j {1, 2, 3, 4}, we know A S v V Mv = for each defensive

Defensive Alliances in Signed Graphs

alliance A V in G , i.e., A V . Observe ( ): In G , each v V is incident with exactly d (v) negative edges. For clarity, in the following we attach a possibly second subscript G or G to deg and its variations to express of which graph we are talking about. Let A V be a defensive alliance in the unsigned graph G. By definition, for all v A,

deg G,A(v) + 1 deg G,A(v) = deg G(v) deg G,A(v) ,

i.e., deg G,A(v) deg G(v) 1

2 . Since the degree is an integer, this is equivalent to

deg+ G ,A(v) = deg G,A(v) deg G(v) 1

= d (v) 1 ( ) = deg G ,A(v) 1 .

Also, deg G ,A(v) = 0. Therefore, A is a defensive alliance in G if and only if A is a defensive alliance in G .

As the set of vertices forming an alliance is the same in the original unsigned graph G and the constructed signed graph G , many complexity (hardness) results known for Minimum Defensive Alliance in unsigned graphs translate to complexity (hardness) results for Minimum Defensive Alliance in signed graphs. According to (Enciso, 2009; Jamieson et al., 2009), papers that are discussing alliance problems on planar and chordal unsigned graphs, the following is a direct consequence from the reduction of Theorem 21. Notice that the results for special graph classes obtained this way do not follow from Theorem 11.

Theorem 22. Min Def All is NP-complete, even if the underlying unsigned graph is planar or chordal.

Proof. We still have to show that the presented reduction of Theorem 21 preserves planarity and chordality. For planarity, it suffices to observe that only 4-cliques are attached to each vertex of a planar graph, and this can be done maintaining the planar embedding of the original planar graph. Concerning chordality, we use the concept of a perfect elimination order. For a graph G = (V, E); this refers to bijections σ : {1, . . . , |V |} V such that, for each i {1, . . . , |V |}, N[σ(i)] {σ(1), . . . , σ(i)} is a clique of G[{σ(1), . . . , σ(i)}]. It is well known that a graph is chordal if and only if the graph has a perfect elimination order. As Minimum Defensive Alliance on unsigned chordal graphs is NP-complete by (Jamieson et al., 2009), we can assume that the unsigned graph G = (V, E) that we start with in our reduction is chordal and has a perfect elimination order. We now consider the graph G = (V , E ) obtained by our reduction; more precisely, we discuss its underlying unsigned graph. We freely use the notations concerning the vertices of G from the previous description in the following. Since N[vi,j] = {vi,1, vi,2, vi,3, vi,4} is a clique for each v V , i {1, . . . , d (v)} and j {2, 3, 4}, these vertices can be mentioned in the end of a perfect elimination order. If we delete these vertices, vi,1 is pendant and these vertices can follow in the order. The remaining vertices and edges are the vertices and edges from G. As G is assumed to be chordal, we can conclude our definition of the ordering of the vertices of G

by any perfect elimination ordering of the vertices of G. By the reasoning above, this gives indeed a perfect elimination order of G , proving that G is chordal.

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Another typical restriction often discussed in the literature is an upper bound on the maximum degree of the graph. We have seen in Theorem 7 that the problems that we study are polynomial-time solvable on subcubic signed graphs. Currently, we do not know if this is also true if we lift the upper bound on the degree from three to four, but an increase to five changes the picture, as we show next by modifying the construction of Theorem 11.

Theorem 23. Def All (and Min Def All) on signed graphs is NP-complete even if the maximum degree is 5.

Proof. The membership follows by Theorem 11, also the hardness is obtained by reducing from NAE-3SAT very similarly. We only modify the clause gadget of Figure 3b into Figure 4.

Figure 4: Clause gadget: the squares represent the not-in-the-solution gadget.

Let ϕ = C1 Cm be an input of NAE-3SAT with the variable set X, where |X| = n. In the same way as in the proof of Theorem 11, define Nv,i := (Vv,i, , E v,i), where Vv,i := {vi,1, vi,2, vi,3, vi,4}, i N+, serving as not-in-the-solution gadgets. Notice that now, all these gadgets are small. Also, for each variable x in X: C(x) := {Cj1, . . . , Cjnx | x Cji, i {1, . . . , nx}, ji {1, . . . , m}}, and X (x) := {xh | h {1, . . . , 2nx}}. We construct the signed graph G = (V, E+, E ) with:

V := {ci, di | i {1, . . . , m} } {Vdi,l | i {1, . . . , m}, l {1, 2}} [

v X (x),l {1,2} Vv,l

E+ := {cjdj | j {1, . . . , m}} {x2p 1x2p | p {1, . . . , nx}, x X}

E := {didi+1, d1dm | i {1, . . . , m 1}} {divdi,l, E di,l | i {1, . . . , m}, l {1, 2}}

x X {cjpx2p 1 | p {1, . . . , nx}, Cjp C(x)}

{x2px2p+1, x2nxx1 | x X, p {1, . . . , nx 1}}

x X {x2hvx2h,l | h {1, . . . , nx}, l {1, 2}}

v X (x),l {1,2} E v,l

If A is a solution of ϕ, then for each Ci = xi1 xi2 xi3, there are j1, j2 {1, 2, 3} such that xij1 = 1 and xij2 = 0. Let S = {x X | A(x) = 0}. Define D := {ci, di | i {1, . . . , m}} S x S X (x), We show that D is a defensive alliance. For each ci, 1) deg+ D(ci) + 1 = 2 deg D(ci); 2) deg+ D(ci) + 1 = 2 deg

D(ci). For each di, deg+ D(di) + 1 =

Defensive Alliances in Signed Graphs

2 = deg D(ci) = deg

D(ci). For each vertex xh D associated to x X, 1) deg+ D(xh) + 1 = 2 deg D(xh); 2) deg+ D(xh) + 1 = 2 = deg

D(xh). Therefore, D is a defensive alliance. Now assume there exists a defensive alliance D V of G. As for all u Vv,i, deg (u) 4 > 1 = deg+(u) + 1, we conclude that D {ci, di | i {1, . . . , m}} {X (x) | x X}. Now, assume that there exists some di D. Since deg+(di) = 1 and deg (di) = 4, |D N (di)| = 2 and |D N+(di)| = 1. Because vdi,1, vdi,2 / D ci, di 1, di+1 D (or d1, dm D if i {1, m}). Hence, di D if and only if C := {ci, di | i {1, . . . , m} } D. If ci D for some i, then deg+(di) = 1 and deg (di) = 3 implies deg+ D(ci) = 1 and deg D(ci), deg

D(ci) {1, 2}. With the argument from above, C would be a subset of D. Assume there exists an x X with X (x) D = . By the proof of Theorem 11, X (x) D. Define the assignment A : X {0, 1} with

( 1, x D, 0, x / D,

i.e., A is the characteristic function of A. As described before, if there exists a non-empty defensive alliance, then for each i {1, . . . , m}, ci D and one or two negative neighbors. Therefore, ϕ is a yes-instance of NAE-3SAT.

In conclusion, (Min)Def All is para-NP-hard when parameterized by maximum degree.

Lemma 24. The constructed signed graph G has at most 16m many vertices.

Proof. From the previous reduction construction, |{ci, di | i {1, . . . , m} } {Vdi,l | i {1, . . . , m}, l {1, 2}}| 2m + 8m = 10m. Combined with Lemma 12, there are at most 10m + 6m = 16m many vertices in total.

Naturally inherited from our reduction, we have the next ETH-based result:

Corollary 25. Under ETH, there is no algorithm for solving Def All (nor Min Def All) on n-vertex signed graphs of maximum degree 5 in time O(2o(n)).

9. Parameterized Complexity and Algorithms

We now look into this problem from the viewpoint of parameterized complexity. We will consider various parameterizations, starting with solution size, sometimes also called the natural parameterization. Subsequently, we will also look at treewidth (of the underlying unsigned graph), at combined parameters, as well as a new parameter (signed neighborhood diversity) that we introduce in this paper as a genuine parameter for signed graphs.

9.1 Parameter Solution Size

While Minimum Defensive Alliance on unsigned graphs with solution-size parameterization is in FPT, see (Fernau & Raible, 2007), we will show for signed graphs a W[1]- completeness result, where hardness is given by a reduction from Clique and membership is given by a reduction to Short Nondeterministic Turing Machine Computation (Cesati, 2003). We now define the two problems that we employ more formally:

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Clique Input: An unsigned graph G and an integer k Problem: Is there a clique in G with k vertices?

Short Nondeterministic Turing Machine Computation Input: A single-tape nondeterministic Turing machine M, a word x on the input alphabet Σ and an integer k Problem: Does M accept x within k steps?

Theorem 26. Min Def All with solution-size parameterization is W[1]-complete, even on balanced signed graphs.

Proof. It is well-known that Clique with solution-size parameterization is W[1]-complete. This is the basis for our reduction. Let G = (V, E), k be any instance of Clique. Define Cv,i = {vij|j {1, 2, 3, 4}} for all i {1, . . . , max{3, k}}, and VE = {be | e E}, also called edge-vertices. The reduction R is defined as: R( G, k ) :=

1) Build a signed graph G = (V , E +, E ):

E + := {ube, vbe | e = uv E}, E := {vvi1, bebel1, vijvih, beljbelh | v V, i {1, . . . , k}, e E, l {1, 2, 3}, j, h {1, 2, 3, 4}, j = h}.

2) Return D G , k + k(k 1)

If G, k is a yes-instance of Clique, without loss of generality, G contains a clique of size at least k, denoted as Ck = {v1, . . . , vk}. Let S = Ck Ek, where Ek = {d vivj | i, j {1, . . . , k}, i = j}, combined with the reduction R, we know for each v Ck, deg+ S (v) = k 1, so (1) deg+ S (v) + 1 = k deg S (v) = 0; (2) deg+ S (v) + 1 = k deg

S (v) = k. For all be Ek, deg+ S (be) = 2, so (1) deg+ S (be) + 1 = 3 deg S (be) = 0; (2) deg+ S (be) + 1 = 3 deg

S = 3. That

is to say, S forms a defensive alliance of size k + k(k 1)

2 . Conversely, if the signed graph G built by R contains a defensive alliance S with |S| k + k(k 1)

2 . For all v Cx,i, deg+(v) + 1 = 0 + 1 < deg (v)

2 = 2. Therefore, such vertices cannot be in any defensive alliance. Moreover, any two vertices in V are not adjacent, and also VE forms an independent set. Therefore, S = V1 V2, where V1 V, V2 VE. By construction, we have deg (v) = k, for all v V and deg (be) = 3 for all e E. So for v1 V1, |{be V2 | x V : e = v1x E}| k 1 ,

and for be V2, its two incident vertices must be in S. So, we know |V1| k. To defend k vertices in V1, we need at least (k 1) + (k 2) + . . . + 1 = k(k 1)

2 many corresponding edge-vertices in V2 without the addition of new vertices. So |S| = |V1| + |V2| k + k(k 1)

2 . Then we have S = V1 V2, where |V1| = k, |V2| = k(k 1)

2 . Obviously, V1 is a clique of G with size k.

Defensive Alliances in Signed Graphs

For the membership proof, we use the Turing machine characterization of W[1] as developed by Cesati (2003). Formally, we have to describe a (in our case, polynomial-time, as well as parameterized) reduction from Minimum Defensive Alliance to Short Nondeterministic Turing Machine (NTM) Computation, consisting in a single-tape nondeterministic Turing machine M, a word x on the input alphabet of M, and a positive integer k. The task is to decide if M accepts x in at most k steps. Given a signed graph G = (V , E +, E ) with n vertices and m = m+ + m edges, and a positive integer k , we can construct a single-tape nondeterministic Turing machine M, which nondeterministically guesses k vertices of G and writes as (S :=){v1, v2, . . . , vk } onto the tape. Then, M scans each guessed vertex vi and rejects either (1) deg+ S (vi) + 1 < deg S (vi), or (2) deg+ S (vi) + 1 < deg (vi) deg S (vi). Otherwise, it accepts. It can be verified that the Turing machine M accepts in O(k 2) steps if and only if there is a defensive alliance of size k

in G . This explains the correctness of the reduction that we sketched.

Notice that this result is not only a negative message, as by the well-known inclusion W[1] XP, we also get the following algorithmic result, as XP is also known as poor man s FPT . This can be truly interesting also from a practical side, as testified by Schirneck (2022) in the context of databases.

Corollary 27. Min Def All XP when parameterized with solution size.

9.2 Treewidth

Another very commonly studied parameter is treewidth. According to [(Bliem & Woltran, 2018), Theorem 1], Minimum Defensive Alliance on unsigned graphs with treewidth as its parameter is also W[1]-hard. With Theorem 21, this translates into our setting as follows.

Theorem 28. Min Def All is W[1]-hard, when parameterized by the treewidth of the underlying unsigned graph.

Proof. Let (G, k) is an instance of Minimum Defensive Alliance on unsigned graphs, based on Theorem 21, we can obtain an instance of Minimum Defensive Alliance on signed graphs (G , k) in polynomial time. We show that the treewidth of the underlying graph of G depends only on the treewidth of G, by modifying an optimal tree decomposition T of G as follows: for each v V (G), take an arbitrary node whose bag B contains v, and then add d (v) nodes C1, C2, . . . , Cd (v) as its children such that the bag of each Ci is B {vi,1}; and then add a child node Ni to each node Ci with bag {vi,1, vi,2, vi,3, vi,4}. It is easy to verify that the result is a valid tree decomposition of the underlying graph of G

and its width is at most the treewidth of G plus 1 or 4. Following [(Bliem & Woltran, 2018), Theorem 1], we know Minimum Defensive Alliance on signed graphs is W[1]-hard when parameterized by treewidth.

From the perspective of Parameterized Complexity, it would be interesting to know if Min Def All, when parameterized by treewidth, belongs to W[1] or (probably) not. The same question is open for the unsigned case. Notice that the preceding result has some (negative) algorithmic consequences for a case that is important in the context of geographic applications, namely, that of planar signed

Arrighi, Feng, Fernau, Mann, Qi & Wolf

networks. Not only is Min Def All NP-hard in this case by Theorem 22, but also the standard approach to show that a planar graph problem is in FPT, when parameterized by solution size and aiming at subexponential running times, fails here, as it is based on FPTalgorithms using a tree decomposition of width bounded by solution size, as show-cased for Dominating Set in (Alber et al., 2002). There is an alternative (in a sense, quicker) way to deal with algorithms that deal with treewidth algorithms (see (Flum & Grohe, 2006) for a textbook presentation): designing a CMSOL formula and then invoking Courcelle s theorem (or a variant thereof). One can actually start out with formulating the property of being a defensive alliance of size at most k with the help of a FO formula (of a size bounded by a function in k). Now, it is very tempting to try even more general meta-theorems as (Grohe et al., 2017, Theorem 1.1) to then claim FPT-results with solution-size parameterization for nowhere dense graphs. However, this approach is not immediately viable, because the proof of the mentioned theorem makes heavy use of the fact that this is about nowhere dense graphs, i.e., in particular about finite structures with a single relation of arity two, while signed graphs are finite structures with two relations of arity two. However, as it is indeed possible to formulate the mentioned FO formula, with similar ideas, we can at least (rather immediately) deduce a result concerning combined parameters as we will consider next.

9.3 Combined Parameters

We have seen that there is no hope to find parameterized algorithms for a number of parameters, more specifically:

Unless FPT = W[1], the parameter solution size is not viable due to Theorem 26.

Under even weaker assumptions, Theorem 28 proves that the parameter treewidth is not useful (alone) to derive parameterized algorithms.

Even worse, Theorem 23 shows that with respect to the parameter maximum degree, our problem is even para-NP-hard.

This raises the question what can be done if we combine the mentioned parameters. Possibly even somewhat surprisingly, we show in this subsection that any combination of these hard parameters leads to FPT results.

Theorem 29. Min Def All is in FPT when parameterized by the treewidth of the underlying unsigned graph and by solution size.

Proof. We show that there exists a CMSOL formula φ of size polynomial in the solution size k that describes the scenario there exists a defensive alliance of size (exactly) k in the given signed graph G . Written in EMSO notation, where D is a set of vertices that should have size k, we can write:

ϕ+,ℓ(x) = _

ϕ ,i in (x) ϕ ,j out(x)

Here, the three different FO formulae ϕz(x) have the following meanings.

Defensive Alliances in Signed Graphs

ϕ+,ℓ(x) checks if there are exactly ℓpositive neighbors of x in D;

ϕ ,i in (x) checks if there are exactly i negative neighbors of x within D;

ϕ ,j out(x) checks if there are exactly j negative neighbors of x outside D.

Assuming that these formulae can be designed, then the cases covered by the selections of ℓ, i, j show that D is indeed a defensive alliance, as ℓ+ 1 = deg+ S (x) i = deg S (x) and ℓ+ 1 j = deg

S (x). Also, it should be clear that the size of the overall formula is bounded by a polynomial in k, should this be the case for the three types of FO formulae. Obviously, these three types have a very similar flavor. We hence only give some details on the construction of ϕ+,ℓ(x) now. ϕ+,ℓ(x) equals

y1, . . . , yℓ

diff(y1, . . . , yℓ)

1 λ ℓ (D(yλ) E+(x, yλ)) z

(D(z) E+(x, z) = _

1 λ ℓ z = yλ

where diff(y1, . . . , yℓ) is a shorthand for some standard formula (of length quadratic in ℓ) that tests if all vertices y1, . . . , yℓare pairwise different.

When we consider the combination of different parameters, we can design parameterized algorithms with combined parameter solution size and maximum degree, as we have degree and diameter bounded by Proposition 9 and can hence obtain a (huge) kernel; see (Fernau, 2018). Alternatively, we can build a search tree quite analogously to the case of unsigned graphs, as in (Fernau & Raible, 2007).

Theorem 30. Min Def All is in FPT when parameterized both by solution size and by maximum degree.

Proof. Let (G, k) be an instance of Min Def All, where the maximum degree of the underlying unsigned graph of G is d. We show that Min Def All is fixed-parameter tractable with combined parameters k and d. From Proposition 9, we are looking for a defensive alliance which is connected in the underlying graph. We guess a vertex v being in a defensive alliance D with |D| k. If {v} is already a defensive alliance, we are done; otherwise, we branch on the subset of the neighborhood of v, which leads to 2d branches. Then we have a defensive alliance of size not larger than k or we keep on branching on the union of the neighborhoods resulting in a branch of size 2k(d 1). As D is connected, we can branch at most k 1 times and obtain a search-tree of size bounded by 2d2k(k 2)(d 1) = 2O(dk2). Moreover, we can check whether we have already obtained a defensive alliance of size at most k in time O(k2). We could branch over all vertices of G in the beginning, so that the problem can be solved in time O(k22O(dk2)n).

We can also combine the parameters treewidth and maximum degree. Again, the picture changes and we encounter parameterized tractability.

Theorem 31. (Min)Def All is in FPT when parameterized both by treewidth and maximum degree.

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Analyzing the proof of Theorem 29, one can see that we could also design a CMSOL formula that proves this result; in fact, as we are always looking into the neighborhood of a certain vertex of the alliance, every time we state a dependence of the formula length on the solution size, we could as well state a dependence on the maximum degree, so that the very same formula can be considered. But as FPT algorithms based on the MSO machinery are deemed to be impractical, we are presenting an explicit dynamic programming algorithm for this case. It should be mentioned that conversely, also this algorithm can be adapted to prove Theorem 29.

Proof. Let G = (V, E+, E ) be an instance of Def All with bounded treewidth l and maximum degree . Actually, we will describe an algorithm based on the principle of dynamic programming that also solves the minimization version in the sense that it first decides if G admits a defensive alliance at all (which is signalled by having computed as the size of the smallest alliance) or it will output the size of the smallest defensive alliance of G. Clearly, this would also allow us to solve an instance of Min Def All if necessary. Assume that a nice tree decomposition T = (T, {Xt}t V (T)) of G with width l is known. Namely, recall that we can compute such a tree decomposition, given G, in FPT-time when parameterized by the treewidth of the input (Cygan et al., 2015). We consider T as a rooted tree by arbitrarily choosing a root ρ and Tt as the subtree of T rooted at t T defined by those vertices whose unique path to ρ will contain t. Define Yt = S t V (Tt) Xt for each t V (T). We want to use dynamic programming to solve this problem. Therefore, we build a table τt considering all partial solutions on Yt (for t V (T)) depending on the interaction between the partial solution and the bag Xt. For each At = {v1, . . . , vj} Xt, let τt[At, i 1, e 1, . . . , i j, e j] with |At| := j l + 1, be the minimum size of the current solution St on Yt, where Xt St = At and i k = deg+ St(vk) deg St(vk) + 1 or e k = deg+ St(vk) deg

St(vk) + 1 = deg St(vk) deg (vk) + 1 records the first (internal) or second (external) defensive alliance condition for each k {1, . . . , j}, respectively. For each configuration [At, i 1, e 1, . . . , i j, e j] of node t, more precisely, its value

τt[At, i 1, e 1, . . . , i j, e j]

is given by:

min{|St| | St Yt, St Xt = At,

vk At, i k = deg+ St(vk) deg St(vk) + 1, e k = deg St(vk) deg (vk) + 1,

u St \ At, deg+ St(u) deg St(u) + 1 0, deg St(u) deg (u) + 1 0}.

Here, we see already how the idea of a partial solution is implemented by using the fact that bags are separators in the graph. Namely, the vertices in St that are not in At must satisfy the conditions imposed upon defensive alliance vertices as they will never see any further neighbors when walking towards the root of the tree decomposition. Notice that these conditions are not only locally looking at the part of the graph that has been processed when walking bottom-up along the tree decomposition, but the degree conditions are referring to the whole graph G. This feature is different from most algorithms that use dynamic programming for computing graph parameters along tree decompositions. Conversely, from the perspective of the vertex set At presumed to be a subset of a defensive alliance, the

Defensive Alliances in Signed Graphs

exact set of neighbors in Yt \ Xt is irrelevant, it only counts how many friends or foes are within or outside the set St At. This information is fixed in the last 2 j descriptors of a table row. Let Zt[At, i 1, e 1, . . . , i j, e j] be the underlying set of sets, so that

τt[At, i 1, e 1, . . . , i j, e j] = min{|St| | St Zt[At, i 1, e 1, . . . , i j, e j]} .

If Zt[At, i 1, e 1, . . . , i j, e j] = , we set τt[At, i 1, e 1, . . . , i j, e j] := . Obviously, the number of entries of each table is bounded by 2l+1 (2 +1)2(l+1). We now specifically present how to build the table of t V (T) by using the tables of its children. The initialization sets all tables of leaf nodes t of the tree decomposition with one entry τt[ ] = 0.

- Consider the case of an introduce node t with unique child t , where Xt = Xt {v}. For each configuration [At, i 1, e 1, . . . , i j, e j] of t, we have:

i) If v / At, then τt[At, i 1, e 1, . . . , i j, e j] = τt [At, i 1, e 1, . . . , i j, e j].

ii) If v At, without loss of generality, we regard v as the jth vertex of At, for each k {1, . . . , j 1}, we define

i k 1, if vkvj E+

i k + 1, if vkvj E

i k, otherwise

( e k 1, if vkvj E+ E

e k, otherwise

as well as e i k := deg+ At(vk) deg At(vk) + 1

e e k := deg At(vk) deg (vk) + 1

for k {1, . . . , j}. Then,

τt[At, i 1, e 1, . . . , i j, e j] =

τt [At \ {v}, ,i 1 , ,e 1 , . . . , ,i j 1, ,e j 1] + 1 if i j =e i j and

e j =e e j , otherwise.

- Now, consider the case of a forget node t with unique child t , where Xt = Xt \ {v}. For each configuration [At, i 1, e 1, . . . , i j, e j] of t, we can compute the table entry τt[At, i 1, e 1, . . . , i j, e j] as

min{τt [At, i 1, e 1, . . . , i j, e j], τt [At {v}, i 1, e 1, . . . , i j, e j, ki, ke] | ki, ke 0} .

- Finally, consider the case of a join node t with two children t and t , where Xt = Xt = Xt . For each configuration [At, i 1, e 1, . . . , i j, e j] of t, we set:

τt[At, i 1, e 1, . . . , i j, e j] = min{τt [At, xi 1, xe 1, . . . , xi j, xe j] + τt [At, xi 1, xe 1, . . . , xi j, xe j] |At|

| xi k + yi k = i k + e i k, xe k + ye k = e k + e e k} .

Arrighi, Feng, Fernau, Mann, Qi & Wolf

For the remaining proof, we want to show that the given recursion fits the definition. For this we use induction on the tree decomposition structure. We start with a leaf node t. This implies Xt = Yt = . Hence, At = and St = fulfills all necessary conditions of the underlying set of τt[ ]. This implies τt[ ] = 0. Let now t be a node and assume we calculated all values for the tables of the children. We will use case distinction for t depending on three cases, t being either an introduce, a forget or a join node. We start with the introduce node case. Let t be the child of t and v be the introduced vertex. At = {v1, . . . , vj} Xt and i 1, e 1, . . . , i j, e j { + 1, . . . , + 1}. Assume v / At. Hence, At Xt and as Yt = Yt {v}, St Yt for each St Zt[At, i 1, e 1, . . . , i j, e j]. Therefore, Zt[At, i 1, e 1, . . . , i j, e j] = Zt [At, i 1, e 1, . . . , i j, e j]

and τt[At, i 1, e 1, . . . , i j, e j] = τt [At, i 1, e 1, . . . , i j, e j].

Let v At. Without loss of generality, v = vj. Since N(v) Yt Xt by the separator property of bags, i j = deg+ At(vj) deg At(vj)+1 = e i j or e j = deg At(vj) deg (vj)+1 = e e j would imply Zt[At, i 1, e 1, . . . , i j, e j] = and τt[At, i 1, e 1, . . . , i j, e j] = . Therefore, assume i j = e i j and e j = e e j. Let St Zt[At, i 1, e 1, . . . , i j, e j] and St := St \ {v} with |St| = τt[At, i 1, e 1, . . . , i j, e j]. For all k {1, . . . , j 1}, ,i k = deg+ St (vk)

deg St (vk) + 1 and ,e k = deg St (vk) deg (vk) + 1 holds by definition of ,i k , ,e k . For each u St \ Xt = St \ Xt , deg+ St(u) = deg+ St (u) and deg St(u) = deg St (u). Since

further St Yt , St Zt [At \ {v}, ,i 1 , ,e 1 , . . . , ,i j 1, ,e j 1]. Assume there exists an

S t Zt [At \ {v}, ,i 1 , ,e 1 , . . . , ,i j 1, ,e j 1] with |S t | < |St |. This would contradict |St| = τt[At, i 1, e 1, . . . , i j, e j], S t {v} Zt[At, i 1, e 1, . . . , i j, e j] and |S t {v}| < |St {v}|. As our second case, assume that t is a forget node and that t is its child with Xt = Xt \ {v}. We know that Yt = Yt . Let At = {v1, . . . , vj} Xt and i 1, e 1, . . . , i j, e j { + 1, . . . , + 1}, for each St Yt(= Yt ) with St Xt = At, if v / St, then Zt [At, i 1, e 1, . . . , i j, e j] Zt[At, i 1, e 1, . . . , i j, e j]; if v St, as v / At, i.e., v St\At, only when ki := deg+ St(v) deg St(v) + 1 0, ke := deg St(v) deg (v) + 1 0, we have Zt [At {v}, i 1, e 1, . . . , i j, e j, ki, ke] Zt[At, i 1, e 1, . . . , i j, e j]. So

τt[At, i 1, e 1, . . . , i j, e j] = min{t [At, i 1, e 1, . . . , i j, e j], t [At {v}, i 1, e 1, . . . , i j, e j, ki, ke]

| ki, ke 0}.

Finally, assume that t is a join node with two children t and t , where Xt = Xt = Xt . We know that Yt = Yt Yt , from the property of tree decomposition, Yt Yt = Xt = Xt = Xt . Let At = {v1, . . . , vj} Xt and i 1, e 1, . . . , i j, e j { + 1, . . . , + 1}, for each St Yt with St Xt = At, let St = S1 S2 S3, where S1 St Yt \ Yt , S2 St Yt \ Yt , S3 = St \ (S1 S2). Clearly, St := S1 S3 Yt with St Xt = S3, St := S2 S3 Yt with St Xt = S3, S3 = St (Yt Yt ) = At. So for each vk At,

i k = deg+ St(vk) deg St(vk) + 1

= deg+ S1(vk) + deg+ S2(vk) + deg+ S3(vk) deg S1(vk) deg S2(vk) deg S3(vk) + 1 ,

Defensive Alliances in Signed Graphs

i.e., i k = (deg+ S1(vk) + deg+ S3(vk) deg S1(vk) deg S3(vk) + 1) + (deg+ S2(vk) + deg+ S3(vk)

deg S2(vk) deg S3(vk)+1) (deg+ S3(vk) deg S3(vk)+1) = ,i k + ,i k f i k, and analogously, e k = ,e k + ,e k e e k. Therefore,

Zt [At, ,i 1 , ,e 1 , . . . , ,i j , ,e j ] Zt [At, ,i 1 , ,e 1 , . . . , ,i j , ,e j ]

is a subset of Zt[At, i 1, e 1, . . . , i j, e j] as

|St| = |S1| + |S2| + |S3| = (|S1| + |S3|) + (|S2| + |S3|) |S3| ,

τt[At, i 1, e 1, . . . , i j, e j] equals the minimum over all sums

τt [At, ,i 1 , ,e 1 , . . . , ,i j , ,e j ] + τt [At, ,i 1 , ,e 1 , . . . , ,i j , ,e j ] |At|

where ,i k + ,i k = i k + e i k, ,e k + ,e k = e k + e e k, as we claimed it above.

Admittedly, networks of bounded degree are rarely encountered in the real world. Still, combinatorial questions restricted to bounded-degree graphs are traditionally considered, as this study can serve as an indication for conceptually related graph classes. For instance, although high-degree hubs could occur in real-world networks, they still have bounded average degree or bounded degeneracy, notions related to bounded degree. We have to leave it as an open question if we can generalize the previous result to the combined parameters treewidth plus average degree or plus degeneracy. We can only state that our algorithmic result also leads to an FPT-result concerning the parameter domino treewidth, see (Bodlaender & Engelfriet, 1997; Bodlaender, 1999; Ding & Oporowski, 1995). This result hence raises the question if we can find efficient algorithms for sparse graphs of bounded treewidth that might model at least some realistic network scenarios.

9.4 Signed Neighborhood Diversity: a New Parameter

We next discuss a new structural parameter for signed graphs, signed neighborhood diversity snd, which makes the problems tractable, parameterized by snd. Our construction is a non-trivial extension of a similar result for unsigned graphs shown in (Gaikwad et al., 2021).

Definition 4. (Signed Neighborhood Diversity snd) Let G = (V, E+, E ) be a signed graph. Define the binary relation snd on V by v u if and only if N+(v)\{u} = N+(u)\{v} and N (v) \ {u} = N (u) \ {v}. snd(G) is the number of equivalence classes of snd on G.

We will exhibit the parameterized algorithm in the following, which is implemented by an ILP with 2 snd(G) many variables. By (Cygan et al., 2015, Theorem 6.5), this ILP can be solved in FPT-time. Let d := snd(G), and C1, . . . , Cd denote the equivalence classes of snd. Further, define N+ i := {j {1, . . . , d} | Cj N+(Ci)} and N i := {j {1, . . . , d} | Cj N (Ci)}. For the ILP, we need z+ 1 , . . . , z+ d {0, 1} with z+ i = 1 if and only if i N+ i . Similarly, define z 1 , . . . , z d {0, 1}. The ILP has the variables, x1, . . . , xd, w1, . . . , wd. For each

Arrighi, Feng, Fernau, Mann, Qi & Wolf

i {1, . . . , d}, xi {0, . . . , |Ci|} represents the number of vertices in Ci which are in our solution; wi {0, 1} expresses if xi is 0 or not. Then the ILP is given by:

z i 2 (1 wi) |V |

i {1, . . . , d} (1)

2 (1 wi) |V |

i {1, . . . , d} (2)

xi |Ci| wi i {1, . . . , d} (3)

wi xi i {1, . . . , d}. (4)

Lemma 32. There exists a defensive alliance S V on G if and only if the ILP has a solution. If such a solution exists, then |S| = Pd i=1 xi.

Proof. Let S be a defensive alliance on G. Then define x i := |S Ci|, for each i {1, . . . , d}. Let i {1, . . . , d}. Then set w i to 1 if and only if x i = 0. Otherwise, set wi to 0. Clearly, w i {0, 1} and 0 x i |Ci|. Further, x i and w i fulfill the inequalities in 3 and 4.

Now we want to show that deg+ S (v) = P j N+ i x j z+ i holds for each v S Ci.

Since, for each j {1, . . . , d} and v, u Cj, N+(v) \ {u} = N+(u) \ {v}, Ck N+(Ci) or Ck N+(Ci) = . Therefore, deg+ S\Ci(v) = P j N+ i \{i} x j for each v Ci. Let v

S Ci. If i N+ i , then deg+ S Ci(v) = |S Ci| 1 = x i zi. This implies deg+ S (v) = P j N+ i x j z+ i for all v S Ci. Analogously, deg S (v) = P j N i x j z i and

deg S(v) = P j N i |Cj| x j (as deg Cj\S(v) = |Cj \ S| = |Cj| x j for each j {1, . . . , d}) holds for each v S Ci. If w i = 0, then we observe

+ 1 z+ i 0 > |V | 2|V | ( X

x j) z i 2 (1 wi) |V |.

Analogously, P j N+ i x j + 1 z+ i > P j N i |Cj| x j 2 (1 wi) |V | holds. For

w i = 1, there exists a v S Ci. Then

+ 1 zi = deg+ S (v) deg S (v)

z i 2 (1 wi) |V |.

Furthermore,

+ 1 zi = deg+ S (v) deg

2 (1 wi) |V |.

Defensive Alliances in Signed Graphs

Hence x 1, . . . , x d, w 1, . . . , w d is a solution for the ILP. Further

j=1 |S Cj| =

Now assume there exists a solution x 1, . . . , x d, w 1, . . . , w d for the ILP. Let i {1, . . . , d} If x i = 0, then 0 w i x i 0 (see inequality 4) implies w i = 0. For x i = 0, 0 < x i |Ci| w i implies w i = 1. Choose a set S such that xj = |S Cj| for j {1, . . . , d}. This can be done as

0 xj |Cj| and C1, . . . , Cd is a partition. As above, deg+ S (v) = P j N+ i x j z+ i ,

deg S (v) = P j N i x j z i and deg S(v) = P j N i |Cj| x j hold for all i {1, . . . , d}

and v Ci S. Let i {1, . . . , d} and v S Ci. This implies x i > 0 and w i = 1. Therefore,

deg+ S (v) + 1 =

2 (1 wi) |V | =

deg+ S (v) + 1 =

z i 2 (1 wi) |V | =

= deg S (v).

Therefore, S is a defensive alliance.

Theorem 33. snd-Minimum Defensive Alliance and snd-Defensive Alliability are in FPT.

As a side note, observe that the ILP formulation above also contains, as a sub-system of equations, a way how to express (Min)Def All as an ILP, which could be interesting for solving such problems in practice. We were not able to find a similar parameterized algorithm when considering the parameterization by the neighborhood diversity of the underlying unsigned graph. This is also due to the fact that we do not know if Minimum Defensive Alliance is still hard or possibly polynomial-time solvable if the underlying graph is a clique. Knowing good algorithmic approaches for Minimum Defensive Alliance on cliques could be also helpful when thinking of modular decompositions or similar concepts that are often used for developing efficient algorithms on networks. Therefore, it is natural to consider weaker parameterizations of the underlying unsigned graph. This discussion makes the following result interesting.

Theorem 34. Def All and Min Def All can be solved in FPT-time when parameterized by the vertex cover number of the underlying unsigned graph.

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Proof. Let vc be the vertex cover number of the underlying graph of G and C be a minimum vertex cover of the underlying graph. Notice that we can compute such a set C in FPTtime; the currently best algorithm is described in (Chen et al., 2010). Then, I := V \ C is an independent set. For each vertex in I, all its neighbors are in C. Distinguished from attributes of edge relationship, there are at most 3vc different neighborhoods for the vertices of I. So the signed neighborhood diversity snd(G) 3vc + vc. From Theorem 33, the claim follows.

10. Discussion

In this paper, we have introduced the notion of defensive alliances in signed networks and provided several algorithmic results for different problem settings. We conclude with suggesting further meaningful variants of problems concerning defensive alliances motivated from a practical perspective.

It can be argued that at least in some practical settings, more positive than negative edges can be expected. For instance, if a signed network is obtained by asking people to name friends or enemies, then most people would rather name friends than explicitly declaring others as enemies. Hence, it might be even an idea to consider the number of negative edges as a parameter for Minimum Defensive Alliance. However, observe that as long as |E | < 2|V |, there always must be a vertex that is not incident to any negative edge, i.e., there always is a defensive alliance of size one. Only if |E | 2|V |, then this pigeonhole argument is no longer true, but then we get trivial FPT algorithms, as it is clear that Minimum Defensive Alliance can be solved in time O (2|V |). Therefore, this parameter is not very interesting.

In our main model, we considered negative relationships within an alliance in the same way as negative relationships outside, but with a different intuition and reasoning behind: negative relations outside the alliance are meant to be enemies , while negative relations inside should stay neutral, but we do not like to see too many of them also for psychological reasons; or if there are some issues on which the alliance should agree, then it is also bad if one partner in the alliance has too many negative relations inside. But one could think of treating both outside and inside negative relationships differently. This is one of the reasons why we introduced (k1, k2)-defensive alliances as a more general setting, but we did not study them in detail in this rather introductory paper.

In the literature of alliances, also a parameterized variant was discussed, requiring that the difference between (positive) relations inside and (negative) relations outside is at least r for some fixed r. We mainly discussed the case r = 1 in this paper. The background is that, according to military history, an attacker should be really stronger than a defender to have a chance of victory. Clearly, also this aspect is contained in our more general definition of (k1, k2)-defensive alliances. However, we confined our complexity discussions to the standard case when k1 = k2 = 1 in order to avoid unnecessary technical complications in this first paper that introduces these notions. Yet, it would be interesting (and a natural question) to extend these complexity (and algorithmic) results to the more general setting.

Defensive Alliances in Signed Graphs

As in Defensive Alliance Building, counting the necessary flips means counting costs, it would make sense to introduce costs on the edges: some parties might be harder to persuade to become friends than others. Our alliance building algorithm can be adapted to this setting, as weighted variants of UDCS can be also solved in polynomial time.2

Likewise, in Minimum Defensive Alliance, it would make sense to put weights on the vertices, modelling different strengths of the involved parties. For instance, not all members of NATO can be considered to be equally powerful. In addition, edge weights in the interval [ 1, 1] could be considered, better quantifying the degree of friendship or enmity. Then, one could generalize the setting towards directed graphs, taking into consideration that this degree need not be symmetric. Similar notions have been introduced also for unsigned directed graphs, see (Mojdeh et al., 2020). Another possibility would be to associate (on top) costs or even cost functions to the variation with directed edges with edge weights, so that it becomes clear how much one has to pay to change the attitude of u towards v. Most questions are open here.

One may argue that it would be more justifiable not to treat internal and external enemies alike, as we do in our proposed main line of definition of a defensive alliance S. Clearly, one solution would be to choose k1 = k2 in the more general definition. Alternatively, one could introduce a scaling factor α [0, 1] and require that deg+ S (v)+ 1 α deg S (v) for all v S, so that α = 1 would correspond to the (first) condition discussed in this paper, while α = 0 means that internal enemies are completely ignored, as they are supposed to stay neutral in case of a conflict, i.e., only the friends within an alliance count. Clearly, setting α = 0 will take off the hardness of Defensive Alliability. It might be also interesting to consider factors α > 1, up to directly requiring that all internal connections are positive. However, notice that not all mutual connections within existing defensive alliances like NATO are genuinely friendly. For instance, the relation between Greece and Turkey has always been critical. This is also true for the defensive alliances found in (Read, 1954). Regarding Minimum Defensive Alliance, most hardness and algorithmic results hold for any α > 0.

Our conditions do not impose explicit constraints on the relative levels of internal and external negative relationships. Adding this as a third condition could also help ensure alliance stability.

On a more technical side, a very interesting question is the complexity status of Defensive Alliability or of Minimum Defensive Alliance if the underlying graph is complete. Recall that for the well-known question of Correlation Clustering, NPhardness is preserved under this restriction; it even has a name of its own: Cluster Editing. This question is related to asking if (Min)Def All can be solved in FPT-time when parameterized by the neighborhood diversity of the underlying unsigned graph, or even, more restrictively, by the distance to clique (which denotes the vertex cover number

2. This is explained in more details in the technical report version (Gabow, 1982).

Arrighi, Feng, Fernau, Mann, Qi & Wolf

of the complement graph). In fact, we are not aware of a concrete problem that is FPT under vertex cover parameterization but not in FPT under distance to clique. Interestingly, after the first report version of this paper (Arrighi et al., 2023) was published, a similar generalization of the notion of offensive alliances towards signed graph was suggested in (Feng et al., 2024); the according decision problems seem to be easier from the perspective of parameterized algorithms compared to defensive alliances. This opens up research lines looking for accordingly defined dual alliances (that are both defensive and offensive). Also, for all notions of alliances, one could look into the related partitioning problems (into such alliances) as has been done for the unsigned case before. As these alliances formalize a kind of coalition, also dynamic aspects concerning notions of stability, as discussed, e.g., in (Brandt & Bullinger, 2022), would be a possible line of future research. Since the publication of the first report version of this paper, a group of students (Sebastian et al., 2024) implemented and tested some of the polynomial-time algorithms presented in this paper, most notably, the one on building alliances. The tests certify that the suggested algorithms scale well also for larger networks.

Acknowledgements

This work is supported by National Natural Science Foundation of China (CN) with No. 12471330. We are also grateful for the support of Zhidan Feng through China Scholarship Council.

Alber, J., Bodlaender, H. L., Fernau, H., Kloks, T., & Niedermeier, R. (2002). Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33, 461 493.

Amelio, A., & Pizzuti, C. (2013). Community mining in signed networks: a multiobjective approach. In Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 13, pp. 95 99. ACM.

Amrollahi, A. (2021). A conceptual tool to eliminate filter bubbles in social networks. Australasian Journal of Information Systems, 25.

Arrighi, E., Feng, Z., Fernau, H., Mann, K., Qi, X., & Wolf, P. (2023). Defensive alliances in signed networks. Tech. rep., Ar Xiv, Cornell University.

Bansal, N., Blum, A., & Chawla, S. (2004). Correlation clustering. Machine Learning, 56(1-3), 89 113.

Bessi, A., Coletto, M., Davidescu, G. A., Scala, A., Caldarelli, G., & Quattrociocchi, W. (2015). Science vs conspiracy: Collective narratives in the age of misinformation. Plo S one, 10(2), e0118093.

Bliem, B., & Woltran, S. (2018). Defensive alliances in graphs of bounded treewidth. Discrete Applied Mathematics, 251, 334 339.

Bodlaender, H. L. (1999). A note on domino treewidth. Discrete Mathematics & Theoretical Computer Science, 3(4), 141 150.

Defensive Alliances in Signed Graphs

Bodlaender, H. L., & Engelfriet, J. (1997). Domino treewidth. Journal of Algorithms, 24(1), 94 123.

Brandt, F., & Bullinger, M. (2022). Finding and recognizing popular coalition structures. Journal of Artificial Intelligence Research, 74, 569 626.

Brashears, M., & Brashears, L. (2016). The enemy of my friend is easy to remember: Balance as a compression heuristic. Advances in Group Processes, 33, 1 31.

Bron, C., & Kerbosch, J. (1973). Finding all cliques of an undirected graph (algorithm 457). Communications of the ACM, 16(9), 575 576.

Brusco, M., & Steinley, D. (2010). K-balance partitioning: An exact method with applications to generalized structural balance and other psychological contexts. Psychological Methods, 15(2), 145 157.

Cadena, J., Vullikanti, A. K., & Aggarwal, C. C. (2016). On dense subgraphs in signed network streams. In 16th International Conference on Data Mining, ICDM, pp. 51 60. IEEE.

Cartwright, D., & Harary, F. (1956). Structural balance: a generalization of Heider s theory. The Psychological Review, 63(5), 277 293.

Cesati, M. (2003). The Turing way to parameterized complexity. Journal of Computer and System Sciences, 67, 654 685.

Chen, J., Kanj, I. A., & Xia, G. (2010). Improved upper bounds for vertex cover. Theoretical Computer Science, 411(40 42), 3736 3756.

Chen, S. (2023). How social media can solve the problem of filter bubbles under the New Media algorithm recommendation mechanism the example of Tik Tok. In Proceedings of the 2023 2nd International Conference on Social Sciences and Humanities and Arts (SSHA 2023), pp. 1284 1288. Atlantis Press.

Cheng, H., Yan, X., & Han, J. (2010). Discriminative frequent pattern-based graph classification. In Yu, P. S., Han, J., & Faloutsos, C. (Eds.), Link Mining: Models, Algorithms, and Applications, pp. 237 262, New York, NY. Springer, New York.

Chiang, K.-Y., Hsieh, C.-J., Natarajan, N., Dhillon, I. S., & Tewari, A. (2014). Prediction and clustering in signed networks: a local to global perspective. Journal of Machine Learning Research, 15(1), 1177 -1213.

Chu, L., Wang, Z., Pei, J., Wang, J., Zhao, Z., & Chen, E. (2016). Finding gangs in war from signed networks. In 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pp. 1505 1514. Association for Computing Machinery.

Crandall, C. S., Silvia, P. J., N Gbala, A. N., Tsang, J.-A., & Dawson, K. (2007). Balance theory, unit relations, and attribution: The underlying integrity of Heiderian theory. Review of General Psychology, 11(1), 12 30.

Cucuringu, M., Davies, P., Glielmo, A., & Tyagi, H. (2019). SPONGE: A generalized eigenproblem for clustering signed networks. In Chaudhuri, K., & Sugiyama, M. (Eds.), The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, Vol. 89 of Proceedings of Machine Learning Research, pp. 1088 1098. PMLR.

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Cucuringu, M., Singh, A. V., Sulem, D., & Tyagi, H. (2021). Regularized spectral methods for clustering signed networks. Journal of Machine Learning Research, 22, 264:1 264:79.

Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized Algorithms. Springer.

Darmann, A., & D ocker, J. (2020). On a simple hard variant of not-all-equal 3-SAT. Theoretical Computer Science, 815, 147 152.

Davis, J. A. (1967). Clustering and structural balance in graphs. Human Relations, 20, 181 187.

De Soto, C. B., Henley, N. M., & London, M. M. (1968). Balance and the grouping schema. Journal of Personality and Social Psychology, 8(1), 1 7.

Del Vicario, M., Bessi, A., Zollo, F., Petroni, F., Scala, A., Caldarelli, G., Stanley, H. E., & Quattrociocchi, W. (2016). The spreading of misinformation online. Proceedings of the National Academy of Sciences, 113(3), 554 559.

Ding, G., & Oporowski, B. (1995). Some results on tree decomposition of graphs. Journal of Graph Theory, 20(4), 481 499.

Doreian, P., & Mrvar, A. (2015). Structural balance and signed international relations. Journal of Social Structure, 16(1), 1 49.

Easley, D., & Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press.

Enciso, R. I. (2009). Alliances in Graphs: Parameterized Algorithms and on Partitioning Series-Parallel Graphs. Ph.D. thesis, College of Engineering and Computer Science at the University of Central Florida, Orlando, USA.

Eppstein, D., L offler, M., & Strash, D. (2013). Listing all maximal cliques in large sparse real-world graphs. ACM Journal of Experimental Algorithmics, 18.

Feng, Z., Fernau, H., Mann, K., & Qi, X. (2024). Offensive alliances in signed graphs. In Chen, X., & Li, B. (Eds.), Theory and Applications of Models of Computation - 18th Annual Conference, TAMC, Vol. 14637 of LNCS, pp. 234 246. Springer.

Fernau, H. (2018). Extremal kernelization: A commemorative paper. In Brankovic, L., Ryan, J., & Smyth, W. F. (Eds.), Combinatorial Algorithms, IWOCA 2017, Vol. 10765 of LNCS, pp. 24 36. Springer.

Fernau, H., & Raible, D. (2007). Alliances in graphs: a complexity-theoretic study. In Leeuwen, J., Italiano, G. F., Hoek, W., Meinel, C., Sack, H., Pl aˇsil, F., & Bielikov a, M. (Eds.), SOFSEM 2007, Proceedings Vol. II, pp. 61 70. Institute of Computer Science ASCR, Prague.

Fernau, H., & Rodr ıguez-Vel azquez, J. A. (2014). A survey on alliances and related parameters in graphs. Electronic Journal of Graph Theory and Applications, 2(1), 70 86.

Flum, J., & Grohe, M. (2006). Parameterized Complexity Theory. Text in Theoretical Computer Science. Springer.

Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3), 75 174.

Defensive Alliances in Signed Graphs

Fricke, G., Lawson, L., Haynes, T. W., Hedetniemi, S. M., & Hedetniemi, S. T. (2003). A note on defensive alliances in graphs. Bulletin of the Institute of Combinatorics and its Applications, 38, 37 41.

Gabow, H. N. (1982). An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. Tech. rep. CU-CS-252-82, University of Colorado at Boulder, Department of Computer Science, USA.

Gabow, H. N. (1983). An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Johnson, D. S., Fagin, R., Fredman, M. L., Harel, D., Karp, R. M., Lynch, N. A., Papadimitriou, C. H., Rivest, R. L., Ruzzo, W. L., & Seiferas, J. I. (Eds.), Proceedings of the 15th Annual ACM Symposium on Theory of Computing, STOC, pp. 448 456. Association for Computing Machinery.

Gaikwad, A., Maity, S., & Tripathi, S. K. (2021). Parameterized complexity of defensive and offensive alliances in graphs. In Goswami, D., & Hoang, T. A. (Eds.), Distributed Computing and Internet Technology - 17th International Conference, ICDCIT, Vol. 12582 of LNCS, pp. 175 187. Springer.

Gao, M., Lim, E.-P., Lo, D., & Prasetyo, P. K. (2016). On detecting maximal quasi antagonistic communities in signed graphs. Data Mining and Knowledge Discovery, 30, 99 146.

Grohe, M., Kreutzer, S., & Siebertz, S. (2017). Deciding first-order properties of nowhere dense graphs. Journal of the ACM, 64(3), 17:1 17:32.

Guha, R. V., Kumar, R., Raghavan, P., & Tomkins, A. (2004). Propagation of trust and distrust. In Feldman, S. I., Uretsky, M., Najork, M., & Wills, C. E. (Eds.), Proceedings of the 13th international conference on World Wide Web, WWW., pp. 403 412. ACM.

Hage, P., & Harary, F. (1983). Structural Models in Anthropology, chap. 3. Signed Graphs. Cambridge University Press.

Hao, F., Yau, S. S., Min, G., & Yang, L. T. (2014). Detecting k-balanced trusted cliques in signed social networks. IEEE Internet Computing, 18(2), 24 31.

Harary, F. (1953). On the notion of balance of a signed graph. Michigan Mathematical Journal, 2, 2143 146.

Harary, F. (1961). A structural analysis of the situation in the Middle East in 1956. Journal of Conflict Resolution, 5(2), 167 178.

Haynes, T. W., Hedetniemi, S. T., & Henning, M. A. (2021). Structures of Domination in Graphs, Vol. 66 of Developments in Mathematics. Springer.

Healy, B., & Stein, A. (1973). The balance of power in international history: Theory and reality. The Journal of Conflict Resolution, 17(1), 33 61.

Heider, F. (1946). Attitudes and cognitive organization. The Journal of Psychology, 21, 107 12.

Hiller, T. (2017). Friends and enemies: A model of signed network formation. Theoretical Economics, 12(3), 1057 1087.

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

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Jamieson, L. H., Hedetniemi, S. T., & Mc Rae, A. A. (2009). The algorithmic complexity of alliances in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 68(137 150).

Jiang, J., Ren, X., & Ferrara, E. (2021). Social media polarization and echo chambers in the context of COVID-19: Case study. JMIRx Med, 2(3), e29570.

Kim, B. J., Liu, J., Um, J., & Lee, S.-I. (2005). Instability of defensive alliances in the predator-prey model on complex networks. Physical Review E, 72(4), 041906.

Kristiansen, P., Hedetniemi, S. M., & Hedetniemi, S. T. (2004). Alliances in graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 48, 157 177.

Kunegis, J., Lommatzsch, A., & Bauckhage, C. (2009). The slashdot zoo: Mining a social network with negative edges. In Proceedings of the 18th International Conference on World Wide Web, WWW, pp. 741 -750. Association for Computing Machinery.

Li, R.-H., Dai, Q., Qin, L., Wang, G., Xiao, X., Yu, J. X., & Qiao, S. (2021). Signed clique search in signed networks: Concepts and algorithms. IEEE Transactions on Knowledge and Data Engineering, 33(2), 710 727.

Mercado, P., Tudisco, F., & Hein, M. (2016). Clustering signed networks with the geometric mean of Laplacians. In Lee, D. D., Sugiyama, M., von Luxburg, U., Guyon, I., & Garnett, R. (Eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems, Neur IPS, pp. 4421 4429.

Mercado, P., Tudisco, F., & Hein, M. (2019). Spectral clustering of signed graphs via matrix power means. In Chaudhuri, K., & Salakhutdinov, R. (Eds.), Proceedings of the 36th International Conference on Machine Learning, ICML, Vol. 97 of Proceedings of Machine Learning Research, pp. 4526 4536. PMLR.

Mohazab, F., & Feger, H. (1985). An extension of Heiderian balance theory for quantified data. European Journal of Social Psychology, 15, 147 165.

Mojdeh, D. A., Samadi, B., & Yero, I. G. (2020). Global defensive k-alliances in directed graphs: combinatorial and computational issues. RAIRO Operations Research, 54(4), 1027 1040.

Ouazine, K., Slimani, H., & Tari, A. (2018). Alliances in graphs: Parameters, properties and applications a survey. AKCE International Journal of Graphs and Combinatorics, 15(2), 115 154.

Palla, G., Der enyi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435, 814 818.

Pons, P., & Latapy, M. (2006). Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications, 10(2), 191 218.

Read, K. E. (1954). Cultures of the central highlands, New Guinea. Southwestern Journal of Anthropology, 10(1), 1 43.

Ross Arguedas, A., Robertson, C., Fletcher, R., & Nielsen, R. K. (2022). Echo chambers, filter bubbles, and polarisation: a literature review. Tech. rep., Reuters Institute for the Study of Journalism.

Defensive Alliances in Signed Graphs

Saloj arvi, E., Rantanen, M., Nieminen, E., Juote, A., & Hanhela, H. (2020). The incel phenomenon in the digital era how echo chambers have fueled the incel movement. In Amadae, S. M. (Ed.), Computational Transformation of the Public Sphere: Theories and Cases, pp. 195 210. Faculty of Social Sciences, University of Helsinki.

Schaefer, T. J. (1978). The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium Theory of Computing, STOC, pp. 216 226. ACM.

Schirneck, M. (2022). Enumeration algorithms in data profiling. Ph.D. thesis, University of Potsdam, Germany.

Seba, H., Lagraa, S., & Kheddouci, H. (2012). Alliance-based clustering scheme for group key management in mobile ad hoc networks. The Journal of Supercomputing, 61(3), 481 501.

Sebastian, A. S., Ilyas, M. S., Nair, S. M., & Sundaram, V. K. S. (2024). Algorithms on signed graphs. Research case study: Masters data science, Abteilung Informatikwissenschaften, Fachbereich IV, Universit at Trier, Germany.

Shafique, K. H. (2004). Partitioning a graph in alliances and its application to data clustering. Phd thesis, School of Computer Science, University of Central Florida, Orlando, USA.

Song, D., & Meyer, D. A. (2015). Recommending positive links in signed social networks by optimizing a generalized AUC. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI, pp. 290 296. AAAI Press.

Sozio, M., & Gionis, A. (2010). The community-search problem and how to plan a successful cocktail party. In Rao, B., Krishnapuram, B., Tomkins, A., & Yang, Q. (Eds.), Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pp. 939 948. Association for Computing Machinery.

Spohr, D. (2017). Fake news and ideological polarization: Filter bubbles and selective exposure on social media. Business Information Review, 34(3), 150 160.

Sun, R., Chen, C., Wang, X., Zhang, Y., & Wang, X. (2022). Stable community detection in signed social networks. IEEE Transactions on Knowledge and Data Engineering, 34(10), 5051 5055.

Sunstein, C. R. (2001). Echo Chambers: Bush v. Gore, Impeachment, and Beyond. Princeton University Press.

Szab o, G., & Cz ar an, T. (2001). Defensive alliances in spatial models of cyclical population interactions. Physical Review E, 64(4), 042902.

Tang, J., Chang, Y., Aggarwal, C. C., & Liu, H. (2016). A survey of signed network mining in social media. ACM Computing Surveys, 49(3), 42:1 42:37.

Tzeng, R., Ordozgoiti, B., & Gionis, A. (2020). Discovering conflicting groups in signed networks. In Larochelle, H., Ranzato, M. A., Hadsell, R., Balcan, M., & Lin, H. (Eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, Neur IPS.

Wang, X., Wang, P., & So, A. M. (2022). Exact community recovery over signed graphs. In Camps-Valls, G., Ruiz, F. J. R., & Valera, I. (Eds.), International Conference on

Arrighi, Feng, Fernau, Mann, Qi & Wolf

Artificial Intelligence and Statistics, AISTATS, Vol. 151 of Proceedings of Machine Learning Research, pp. 9686 9710. PMLR.

Yang, B., Cheung, W. K., & Liu, J. (2007). Community mining from signed social networks. IEEE Transactions on Knowledge and Data Engineering, 19(10), 1333 1348.

Ye, J., Cheng, H., Zhu, Z., & Chen, M. (2013). Predicting positive and negative links in signed social networks by transfer learning. In Proceedings of the 22nd International Conference on World Wide Web, WWW, pp. 1477 1488. Association for Computing Machinery.

Yero, I. G., & Rodr ıguez-Vel azquez, J. A. (2017). A survey on alliances in graphs: defensive alliances. Utilitas Mathematica, 105, 141 172.

Zorn, T. J., Mata, A., & Alves, H. (2022). Attitude similarity and interpersonal liking: A dominance of positive over negative attitudes. Journal of Experimental Social Psychology, 100, 104281.