Alliances in Graphs: A Parameterized Perspective

Abstract

Throughout history, humans have formed communities, guilds, faiths etc in the hope of coming together with a group of people having similar requirements, visions and goals. Their reasons to do so, usually rest on the fact that any group with common interests often provides added mutual benefits to the union in fields of trade, culture, defense, etc as compared to the individual. Such activities are commonly seen in the present day, in areas of geo-politics, cultures, trades, economics, unions etc and are popularly termed as alliances. The concept of an alliance was first captured as a graph theoretic problem in 2004 by Kristiansen, Hedetniemi, and Hedetniemi in [47]. Based on the structure, formation and goals of an alliance, many variations of the problem exist in graph theory. A defensive alliance is usually formed with the aim of defending its members against non-members, and hence it is natural to ask that each member of the alliance should have more friends within the alliance (including oneself) than outside. More formally, a defensive alliance in a graph G = (V, E) is a non-empty set of vertices S satisfying the condition that every vertex v ∈ S has at least as many neighbors (including itself) in S than it has in V \ S. Similarly, an offensive alliance is formed with the inverse goal of offending or attacking non-members of the alliance. An offensive alliance in a graph G = (V, E) is a non-empty set of vertices S satisfying the condition that every vertex v ∈ N(S) has at least as many neighbors in S than it has in V \S (including itself). It is known that the problems of finding small defensive and offensive alliances are NP-complete. We enhance our understanding of the problems from the viewpoint of parameterized complexity. Strong versions of the above problems do not consider the self to be a friend, and the minimal versions try to find those alliances which lose the required property in the absence of any member. These variations in types of alliances manifest themselves ubiquitously in daily life scenar- ios and applications, thereby attributing value to the study of their graph theoretic versions and related algorithms. Alliances have been used to study problems such as classification and clustering problems, understanding communities on the internet, protocols for distribu- tion etc. [20, 58, 36]. The data clustering problem relies on the concept of partitioning the vertices of the graph into multiple strong defensive alliances. This problem was introduced by Gerber and Kobler [34] and is called the Satisfactory Partition problem. Almost all variants of the alliance problem are NP-hard, and so there is very little hope for finding efficient polynomial time algorithms for these problems. However, the applicabilityof this problem warrants the use of techniques which can make these variants computation- ally tractable under certain scenarios. Two key approaches for achieving this goal involve the polynomial-time approximation algorithms and the concept of fixed-parameter tractable (FPT) algorithms. The former involves finding algorithms which approximate the optimal solution in polynomial time, thereby creating a trade-off between the correctness and time complexity of the algorithm. On the other hand, FPT algorithms originated from the theory of parameterized complexity as introduced by Downey and Fellows. Problems which do not admit a polynomial time solution, often make use of exponential time algorithms, thereby making them intractable. The idea in these cases is to associate a parameter k with every instance of the problem, and then try to develop an algorithm that captures the exponential growth only as a function of the parameter k. We would then obtain an algorithm with running time f(k) · n c where n is the size of the input, k is the parameter, f(·) is some computable function, and c is a constant that is independent on k and n. Such algorithms are said to be fixed-parameter tractable algorithms. However, presently, FPT algorithms are not known for all NP-hard problems. The study of these fixed-parameter intractable prob- lems led to the formation of the W-hierarchy of complexity classes. Similar to the theory of classical complexity, showing that a parameterised problem is one of the hardest problems in any one of the W-classes, gives evidence that it is unlikely for the problem to admit an FPT algorithm. In this dissertation, we consider parameterized algorithms and complexity of the following problems: defensive and offensive alliances in graphs, locally minimal defensive alliances in graphs, and the satisfactory partition problem in graphs. We obtain the following results. • We design FPT algorithms for Defensive Alliance and Offensive Alliance when parameterized by neighbourhood diversity of the input graph. We prove that Defensive Alliance and Offensive Alliance are polynomial time solvable for graphs with bounded treewith. • We study parameterized intractability of the Defensive Alliance problem. We prove that the Defensive Alliance problem is W[1]-hard when parameterized by the pathwidth of the input graph. We also prove that the Exact Defensive Alliance problem is W[1]-hard when parameterized by the feedback vertex set number and the pathwidth of the input graph. • We design a polynomial-time algorithm for the Connected Locally Minimal Strong Defensive Alliance on trees. We prove that Locally Minimal De- fensive Alliance problem is NP-complete, even when restricted to planar graphs. We give a randomized FPT algorithm for the Exact Connected Locally Minimal Defensive Alliance problem using color coding technique. We give an FPT algo- rithm for Locally Minimal Defensive Alliance when parameterized by neigh- bourhood diversity of the input graph. We prove that Exact Connected Locally Minimal Defensive Alliance parameterized by treewidth is W[1]-hard and thus not FPT (unless FPT=W[1]). Finally we show that the Locally Minimal Defen- sive Alliance problem is polynomial time solvable for graphs with bounded treewith. • We design a polynomial-time algorithm for the Satisfactory Partition problem for block graphs. We prove that the Satisfactory Partition and Balanced Sat- isfactory Partition problems are fixed parameter tractable (FPT) when parame- terized by neighbourhood diversity. We show that the Satisfactory Partition and Balanced Satisfactory Partition problems can be solved in polynomial time for graphs of bounded clique-width. Finally we prove that the Balanced Satisfactory Partition problem is W[1]-hard when parameterized by treewidth.