We initiate the study of the shortest reconfiguration problem for independent sets under the adjacency relation derived from the independent set polytope. Given a graph and two independent sets, the problem asks for a shortest sequence transforming one into the other such that the subgraph induced by the symmetric difference of any two consecutive sets is connected. This is equivalent to finding a shortest path on the 1-skeleton of the independent set polytope. We prove that the problem is NP-hard even on planar graphs of bounded degree, as well as on split graphs. Notably, the hardness for planar graphs of bounded degree still holds even when deciding whether the target can be reached in at most two steps. For split graphs, we further show the W[2]-hardness when parameterized by the number of steps, as well as the inapproximability of the optimal length. As a consequence, we prove that the length of a shortest path between two vertices of a 0/1 polytope in ℝⁿ described by O(n) linear inequalities is hard to approximate within a factor of (1-ε)ln n for any constant ε > 0, unless P = NP. On the positive side, we provide polynomial-time algorithms for block graphs, cographs, and bipartite chain graphs. Moreover, for paths and cycles, we show that the optimal length of the shortest reconfiguration sequence exactly matches a trivial upper bound.

In this paper, we study the task of enumerating (and counting) locally and globally minimal defensive alliances in graphs. We consider general graphs as well as special graph classes, like trees, bipartite graphs, and split graphs. From an input-sensitive perspective, our presented algorithms are mostly optimal, meaning that their running times (neglecting polynomial factors) match concrete families of graphs that contain that many minimal alliances.

The concept of Roman domination has recently been studied concerning enumerating and counting in F. N. Abu-Khzam et al. (WG 2022). More technically speaking, a function that assigns 0,1,2 to the vertices of an undirected graph is called a Roman dominating function if each vertex assigned zero has a neighbor assigned two. Such a function is called minimal if decreasing any assignment to any vertex would yield a function that is no longer a Roman dominating function. It has been shown that minimal Roman dominating functions can be enumerated with polynomial delay, i.e., between any two outputs of a solution, no more than polynomial time will elapse. This contrasts what is known about minimal dominating sets, where the question whether or not these can be enumerated with polynomial delay is open for more than 40 years. This makes the concept of Roman domination rather special and interesting among the many variants of domination problems studied in the literature, as it has been shown for several of these variants that the question of enumerating minimal solutions is tightly linked to that of enumerating minimal dominating sets, see M. Kanté et al. in SIAM J. Disc. Math., 2014. The running time of the mentioned enumeration algorithm for minimal Roman dominating functions (Abu-Khzam et al., WG 2022) could be estimated as 𝒪(1.9332ⁿ) on general graphs of order n. Here, we focus on special graph classes, as has been also done for enumerating minimal dominating sets before. More specifically, for chordal graphs, we present an enumeration algorithm running in time 𝒪(1.8940ⁿ). It is unknown if this gives a tight bound on the maximum number of minimal Roman dominating functions in chordal graphs. For interval graphs, we can lower this time bound further to 𝒪(1.7321ⁿ), which also matches the known lower bound concerning the maximum number of minimal Roman dominating functions. We can also provide a matching lower and upper bound for forests, which is (incidentally) the same, namely 𝒪^*(√3ⁿ). Furthermore, we present an optimal enumeration algorithm running in time 𝒪^*(∛3ⁿ) for split graphs and for cobipartite graphs, i.e., we can also give a matching lower bound example for these graph classes. Hence, our enumeration algorithms for interval graphs, forests, split graphs and cobipartite graphs are all optimal. The importance of our results stems from the fact that, for other types of domination problems, optimal enumeration algorithms are not always found. Interestingly, we use a different form of analysis for the running times of our different algorithms, and the branchings had to be tailored and tweaked to obtain the intended optimality results. Our Roman dominating functions enumeration algorithm for trees and forests is distinctively different from the one for minimal dominating sets by Rote (SODA 2019).Our approach also allows to give concrete formulas for counting minimal Roman dominating functions on more concrete graph families like paths.

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.

Abstract. The question to enumerate all (inclusionwise) minimal connected dominating sets in a graph of order [Formula: see text] in time significantly less than [Formula: see text] is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time [Formula: see text], using polynomial space only. The key to this result is the consideration of this enumeration problem on 2-degenerate graphs, which is proven to be possible in time [Formula: see text]. Apart from solving this old open question, we also show new lower bound results. More precisely, we construct a family of graphs of order [Formula: see text] with [Formula: see text] many minimal connected dominating sets, while previous examples achieved [Formula: see text]. Our example happens to yield 4-degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2-degenerate and of 3-degenerate graphs, which are [Formula: see text] and [Formula: see text], respectively. We also address essential questions concerning output-sensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much effort. More precisely, we prove that it is NP -complete to decide, given a graph [Formula: see text] and a vertex set [Formula: see text], if there exists a minimal connected dominating set [Formula: see text] with [Formula: see text], even if [Formula: see text] is known to be 2-degenerate. Our reduction also shows that even any subexponential delay is not easy to achieve for enumerating minimal connected dominating sets. Another reduction shows that no FPT -algorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by [Formula: see text]. This also adds one more problem to the still rather few natural parameterized problems that are complete for the parameterized complexity class W [3]. We also relate our enumeration problem to the famous Hitting Set Transversal problem, a problem open for more than four decades, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay, by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic (polynomial-delay) solution to the Hitting Set Transversal problem.

International audience

Abstract Roman domination is one of the many variants of domination that keeps most of the complexity features of the classical domination problem. We prove that Roman domination behaves differently in two aspects: enumeration and extension. We develop non-trivial enumeration algorithms for minimal Roman dominating functions with polynomial delay and polynomial space. Recall that the existence of a similar enumeration result for minimal dominating sets is open for decades. Our result is based on a polynomial-time algorithm for Extension Roman Domination : Given a graph $$G=(V,E)$$ G = ( V , E ) and a function $$f:V\rightarrow \{0,1,2\}$$ f : V → { 0 , 1 , 2 } , is there a minimal Roman dominating function $$\tilde{f}$$ f ~ with $$f\le \tilde{f}$$ f ≤ f ~ ? Here, $$\le $$ ≤ lifts $$0< 1< 2$$ 0 < 1 < 2 pointwise; minimality is understood in this order. Our enumeration algorithm is also analyzed from an input-sensitive viewpoint, leading to a run-time estimate of $$\mathcal {O}(1.9332^n)$$ O ( 1 . 9332 n ) for graphs of order n ; this is complemented by a lower bound example of $$\Omega (1.7441^n)$$ Ω ( 1 . 7441 n ) .

The question to enumerate all (inclusion-wise) minimal connected dominating sets in a graph of order n in time significantly less than 2ⁿ is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time 𝒪(1.9896ⁿ), using polynomial space only. The key to this result is the consideration of this enumeration problem on 2-degenerate graphs, which is proven to be possible in time 𝒪(1.9767ⁿ). Apart from solving this old open question, we also show new lower bound results. More precisely, we construct a family of graphs of order n with Ω(1.4890ⁿ) many minimal connected dominating sets, while previous examples achieved Ω(1.4422ⁿ). Our example happens to yield 4-degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2-degenerate and of 3-degenerate graphs, which are Ω(1.3195ⁿ) and Ω(1.4723ⁿ), respectively. We also address essential questions concerning output-sensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much efforts. More precisely, we prove that it is NP-complete to decide, given a graph G and a vertex set U, if there exists a minimal connected dominating set D with U ⊆ D, even if G is known to be 2-degenerate. Our reduction also shows that even any subexponential delay is not easy to achieve for enumerating minimal connected dominating sets. Another reduction shows that no FPT-algorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by |U|. This also adds one more problem to the still rather few natural parameterized problems that are complete for the class W[3]. We also relate our enumeration problem to the famous open Hitting Set Transversal problem, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic solution to the Hitting Set Transversal problem.