Nacim Oijid

Given a digraph, an ordering of its vertices defines a backedge graph, namely the undirected graph whose edges correspond to the arcs pointing backwards with respect to the order. The degreewidth of a digraph is the minimum over all ordering of the maximum degree of the backedge graph. We answer an open question by Keeney and Lokshtanov [WG 2024], proving that it is NP-hard to determine whether an oriented graph has degreewidth at most 1, which settles the last open case for oriented graphs. We complement this result with a general discussion on parameters defined using backedge graphs and their relations to classical parameters.

We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset positional games, which are positional games with an additional structure – a poset on the elements of the board. Throughout the game play, based on this poset and the set of the board elements that are claimed up to that point, we reduce the set of available moves for the player whose turn it is – an element of the board can only be claimed if all the smaller elements in the poset are already claimed. We proceed to analyze these games in more detail, with a prime focus on the most studied convention, the Maker-Breaker games. First we build a general framework around poset positional games. Then, we perform a comprehensive study of the complexity of determining the game outcome, conditioned on the structure of the family of winning sets on the one side and the structure of the poset on the other.

We study the algorithmic complexity of Maker-Breaker games played on the edge sets of general graphs. We mainly consider the perfect matching game and the H-game. Maker wins if she claims the edges of a perfect matching in the first, and a copy of a fixed graph H in the second. We prove that deciding who wins the perfect matching game and the $H$-game is PSPACE-complete, even for the latter in small-diameter graphs if $H$ is a tree. Toward finding the smallest graph $H$ for which the $H$-game is PSPACE-complete, we also prove that such an $H$ of order 51 and size 57 exists. We then give several positive results for the $H$-game. As the $H$-game is already PSPACE-complete when $H$ is a tree, we mainly consider the case where $H$ belongs to a subclass of trees. In particular, we design two linear-time algorithms, both based on structural characterizations, to decide the winners of the $P_4$-game in general graphs and the $K_{1,l}$-game in trees. Then, we prove that the $K_{1,l}$-game in any graph, and the $H$-game in trees are both FPT parameterized by the length of the game, notably adding to the short list of games with this property, which is of independent interest. Another natural direction to take is to consider the $H$-game when $H$ is a cycle. While we were unable to resolve this case, we prove that the related arboricity-k game is polynomial-time solvable. In particular, when $k=2$, Maker wins this game if she claims the edges of any cycle.

Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins, and if no one manages to do it, the game ends by a draw. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on Incidence, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of Incidence is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.

We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words, we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here three relaxations of Clique: s-Club and s-Clique, in which the relaxation is focused on the distances in respectively the cluster and the original graph, and γ-Complete Subgraph in which the relaxation is made on the minimal degree in the cluster. As these three problems are known to be NP-hard, we study here their parameterized complexities. We prove that s-Club and s-Clique are NP-hard even restricted to graphs of degeneracy ≤3 whenever, and to graphs of degeneracy ≤2 whenever, which is a strictly stronger result than its W[1]-hardness parameterized by the degeneracy. Concerning γ-Complete Subgraph, we prove that it is W[1]-hard parameterized both by the degeneracy, implying the W[1]-hardness parameterized by the number of vertices in the γ-complete-subgraph, and by the number of elements outside the γ-complete subgraph.

We study the Maker–Maker version of the domination game introduced in 2018 by Duchêne et al. Given a graph, two players alternately claim vertices. The first player to claim a dominating set of the graph wins. As the Maker–Breaker version, this game is PSPACE-complete on split and bipartite graphs. Our main result is a linear time algorithm to solve this game in forests. We also give a characterization of the cycles where the first player has a winning strategy.

The game Influence is a scoring combinatorial game that has been introduced in 2021 by Duchêne et al. [5]. It is a good representative of Milnor's universe of scoring games, i.e. games where it is never interesting for a player to miss their turn. New general results are first given for this universe, by transposing the notions of mean and temperature derived from non-scoring combinatorial games. Such results are then applied to Influence to refine the case of unions of segments started by Duchêne et al. [5]. The computational complexity of the score of the game is also solved and proved to be PSPACE-complete. We finally focus on some specific cases of Influence when the graph is bipartite, by giving explicit strategies and bounds on the optimal score on structures like grids, hypercubes or tori.

Given a graph G and k an integer, we introduce the following game played in G. Each round, Alice colours an uncoloured vertex of G red, and then Bob colours one blue (if any remain). Once every vertex is coloured, Alice wins if there is a connected red component of order at least k, and otherwise, Bob wins. This is a Maker-Breaker version of the Largest Connected Subgraph game introduced in [Bensmail et al. The Largest Connected Subgraph Game. Algorithmica, 84(9):2533--2555, 2022]. We want to compute c_g(G), which is the maximum k such that Alice wins in G, regardless of Bob's strategy. Given a graph G and k an integer, we prove that deciding whether c_g(G)≥ k is PSPACE-complete, even if G is a bipartite, split, or planar graph. To better understand the Largest Connected Subgraph game, we then focus on A-perfect graphs, which are the graphs G in which Alice can ensure that the red subgraph is connected. We give sufficient conditions, in terms of the minimum and maximum degrees or the number of edges, for a graph to be A-perfect. Also, we show that, for any d ≥ 4, there are arbitrarily large A-perfect d-regular graphs, but no cubic graph with order at least 18 is A-perfect. Lastly, we show that c_g(G) is computable in linear time when G is a P_4-sparse graph (a superclass of cographs).

The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic theory. Several of its aspects of interest have been investigated in the literature, including variants for modifications of proper colourings. These variants include, notably, the achromatic number of graphs, which is the maximum number of colours required to colour the vertices of graphs properly so that each possible combination of distinct colours is assigned along some edge. The behaviours of this parameter have led to many investigations of interest, bringing to light both similarities and discrepancies with the chromatic number. This work takes place in a recent trend aiming at extending the chromatic theory of graphs to the realm of signed graphs, and, in particular, at investigating how classic results adapt to the signed context. Most of the works done in that line to date are with respect to two main generalisations of proper colourings of signed graphs, attributed to Zaslavsky and Guenin. Generalising the achromatic number to signed graphs was initiated recently by Lajou, his investigations being related to Guenin's colourings. We here pursue this line of research, but with taking Zaslavsky's colourings as our notion of proper colourings. We study the general behaviour of our resulting variant of the achromatic number, mainly by investigating how known results on the classic achromatic number generalise to our context. Our results cover, notably, bounds, standard operations on graphs, and complexity aspects.

A monitoring edge-geodetic set (or meg-set for short) of a graph is a set of vertices M such that if any edge is removed, then the distance between some two vertices of M increases. This notion was introduced by Foucaud et al. in 2023 as a way to monitor networks for communication failures. As computing a minimal meg-set is hard in general, recent works aimed to find polynomial-time algorithms to compute minimal meg-sets when the input belongs to a restricted class of graphs. Most of these results are based on the property of some classes of graphs to admit a unique minimum meg-set, which is then easy to compute. In this work, we prove that chordal graphs also admit a unique minimal meg-set, answering a standing open question of Foucaud et al.

Vertex splitting is a graph modification operation in which a vertex is replaced by multiple vertices such that the union of their neighborhoods equals the neighborhood of the original vertex. We introduce and study vertex splitting as a graph modification operation for transforming graphs into interval graphs. Given a graph G and an integer k, we consider the problem of deciding whether G can be transformed into an interval graph using at most k vertex splits. We prove that this problem is NP-hard, even when the input is restricted to subcubic planar bipartite graphs. We further observe that vertex splitting differs fundamentally from vertex and edge deletions as graph modification operations when the objective is to obtain a chordal graph, even for graphs with maximum independent set size at most two. On the positive side, we give a polynomial-time algorithm for transforming, via a minimum number of vertex splits, a given graph into a disjoint union of paths, and that splitting triangle free graphs into unit interval graphs is also solvable in polynomial time.

Given a c-colored graph G, a vertex of G is happy if it has the same color as all its neighbors. The notion of happy vertices was introduced by Zhang and Li to compute the homophily of a graph. Eto, et al. introduced the Maker-Maker version of the Happy vertex game, where two players compete to claim more happy vertices than their opponent. We introduce here the Maker-Breaker happy vertex game: two players, Maker and Breaker, alternately color the vertices of a graph with their respective colors. Maker aims to maximize the number of happy vertices at the end, while Breaker aims to prevent her. This game is also a scoring version of the Maker-Breaker Domination game introduced by Duchene, et al. as a happy vertex corresponds exactly to a vertex that is not dominated in the domination game. Therefore, this game is a very natural game on graphs and can be studied within the scope of scoring positional games. We initiate here the complexity study of this game, by proving that computing its score is PSPACE-complete on trees, NP-hard on caterpillars, and polynomial on subdivided stars. Finally, we provide the exact value of the score on graphs of maximum degree 2, and we provide an FPT-algorithm to compute the score on graphs of bounded neighborhood diversity. An important contribution of the paper is that, to achieve our hardness results, we introduce a new type of incidence graph called the literal-clause incidence graph for 2-SAT formulas. We prove that QMAX 2-SAT remains PSPACE-complete even if this graph is acyclic, and that MAX 2-SAT remains NP-complete, even if this graph is acyclic and has maximum degree 2, i.e. is a union of paths. We demonstrate the importance of this contribution by proving that Incidence, the scoring positional game played on a graph is also PSPACE-complete when restricted to forests.

The classical Maker-Breaker positional game is played on a board which is a hypergraph H, with two players, Maker and Breaker, alternately claiming vertices of H until all the vertices are claimed. When the game ends, Maker wins if she has claimed all the vertices of some edge of H; otherwise, Breaker wins. Playing this game in real life can be done by placing tokens on the vertices of the board. In this paper, we study the unfortunate case in which one or both players do not have enough tokens to cover all the vertices and, as such, will have to move their tokens around at some point instead of placing new ones. There may be a bias, in that Maker and Breaker do not necessarily have the same amount of tokens. The present paper initiates the study of this generalization of positional games, called token positional games. A particularly interesting case is when Maker has a winning strategy in the classical game: what is the lowest number of tokens with which she still wins against Breaker's unlimited stock? We notably show that, for k-uniform hypergraphs on an arbitrarily large number n of vertices, this number equals k if 2 ≤ k ≤ 3 but can vary from k to Omega(n) if k ≤ 4. From an algorithmic point of view, PSPACE-hardness in general is inherited from classical positional games, but we get a polynomial-time algorithm to solve the case where Breaker only has one token. We also establish EXPTIME-completeness for a token sliding variation of the game.

We pursue the study of edge-irregulators of graphs, which were recently introduced in [Fioravantes et al. Parametrised Distance to Local Irregularity. IPEC, 2024]. That is, we are interested in the parameter Ie(G), which, for a given graph G, denotes the smallest k >= 0 such that G can be made locally irregular (i.e., with no two adjacent vertices having the same degree) by deleting k edges. We exhibit notable properties of interest of the parameter Ie, in general and for particular classes of graphs, together with parameterized algorithms for several natural graph parameters. Despite the computational hardness previously exhibited by this problem (NP-hard, W[1]-hard w.r.t. feedback vertex number, W[1]-hard w.r.t. solution size), we present two FPT algorithms, the first w.r.t. the solution size plus Delta and the second w.r.t. the vertex cover number of the input graph. Finally, we take important steps towards better understanding the behaviour of this problem in dense graphs. This is crucial when considering some of the parameters whose behaviour is still uncharted in regards to this problem (e.g., neighbourhood diversity, distance to clique). In particular, we identify a subfamily of complete graphs for which we are able to provide the exact value of Ie(G). These investigations lead us to propose a conjecture that Ie(G) should always be at most m/3 + c, where m is the number of edges of the graph G and c is some constant. This conjecture is verified for various families of graphs, including trees.

Arc-Kayles is a game where two players alternate removing two adjacent vertices until no move is left, the winner being the player who played the last move. Introduced in 1978, its computational complexity is still open. More recently, subtraction games, where the players cannot disconnect the graph while removing vertices, were introduced. In particular, Arc-Kayles admits a non-disconnecting variant that is a subtraction game. We study the computational complexity of subtraction games on graphs, proving that they are PSPACE-complete even on very structured graph classes (split, bipartite of any even girth). We give a quadratic kernel for Non-Disconnecting Arc-Kayles when parameterized by the feedback edge number, as well as polynomial-time algorithms for clique trees and a subclass of threshold graphs. We also show that a sufficient condition for a second player-win on Arc-Kayles is equivalent to the graph isomorphism problem.

Positional games were introduced by Hales and Jewett in 1963, and their study became more popular when Erdős and Selfridge showed their connection to Ramsey theory and hypergraph coloring in 1973. Several conventions of these games exist, and the most popular one, Maker-Breaker was proved to be PSPACE-complete by Schaefer in 1978. The study of their complexity then stopped for decades, until 2017 when Bonnet, Jamain, and Saffidine proved that Maker-Breaker is W[1]-complete when parameterized by the number of moves. The study was then intensified when Rahman and Watson improved Schaefer’s result in 2021 by proving that the PSPACE-hardness holds for 6-uniform hypergraphs. More recently, Galliot, Gravier, and Sivignon proved that computing the winner on rank 3 hypergraphs is in P, and Keopke proved that the PSPACE-hardness also holds for 5-uniform hypergraphs. We focus here on the Client-Waiter and the Waiter-Client conventions. Both were proved to be NP-hard by Csernenszky, Martin, and Pluhár in 2011, but neither completeness nor positive results were known. In this paper, we complete the study of these conventions by proving that the former is PSPACE-complete, even restricted to 6-uniform hypergraphs, and by providing an FPT-algorithm for the latter, parameterized by the size of its largest edge. In particular, the winner of Waiter-Client can be computed in polynomial time in rank k hypergraphs for any fixed integer k. Finally, in search of the exact location of the complexity gap in the Client-Waiter convention, we focus on rank 3 hypergraphs. We provide an algorithm that runs in polynomial time with an oracle in NP.

The study of SAT and its variants has provided numerous NP-complete problems, from which most NP-hardness results were derived. Due to the NP-hardness of SAT, adding constraints to either specify a more precise NP-complete problem or to obtain a tractable one helps better understand the complexity class of several problems. In 1984, Tovey proved that bounded-degree SAT is also NP-complete, thereby providing a tool for performing NP-hardness reductions even with bounded parameters, when the size of the reduction gadget is a function of the variable degree. In this work, we initiate a similar study for QBF, the quantified version of SAT. We prove that, like SAT, the truth value of a maximum degree two quantified formula is polynomial-time computable. However, surprisingly, while the truth value of a 3-regular 3-SAT formula can be decided in polynomial time, it is PSPACE-complete for a 3-regular QBF formula. A direct consequence of these results is that Avoider-Enforcer and Client-Waiter positional games are PSPACE-complete when restricted to bounded-degree hypergraphs. To complete the study, we also show that Maker-Breaker and Maker-Maker positional games are PSPACE-complete for bounded-degree hypergraphs.

Dominating sets in graphs are often used to model some monitoring of the graph: guards are posted on the vertices of the dominating set, and they can thus react to attacks occurring on the unguarded vertices by moving there (yielding a new set of guards, which may not be dominating anymore). A dominating set is eternal if it can endlessly resist to attacks. From the attacker's perspective, if we are given a non-eternal dominating set, the question is to determine how fast can we provoke an attack that cannot be handled by a neighboring guard. We investigate this question from a computational complexity point of view, by showing that this question is PSPACE-hard, even for graph classes where finding a minimum eternal dominating set is in P. We then complement this result by giving polynomial time algorithms for cographs and trees, and showing a connection with tree-depth for the latter. We also investigate the problem from a parameterized complexity perspective, mainly considering two parameters: the number of guards and the number of steps.

We propose a generalization of positional games, supplementing them with a restriction on the order in which the elements of the board are allowed to be claimed. We introduce poset positional games, which are positional games with an additional structure – a poset on the elements of the board. Throughout the game play, based on this poset and the set of the board elements that are claimed up to that point, we reduce the set of available moves for the player whose turn it is – an element of the board can only be claimed if all the smaller elements in the poset are already claimed. We proceed to analyze these games in more detail, with a prime focus on the most studied convention, the Maker-Breaker games. First we build a general framework around poset positional games. Then, we perform a comprehensive study of the complexity of determining the game outcome, conditioned on the structure of the family of winning sets on the one side and the structure of the poset on the other.

Avoidance games are games in which two players claim vertices of a hypergraph and try to avoid some structures. These games have been studied since the introduction of the game of SIM in 1968, but only few complexity results have been found out about them. In 2001, Slany proved some partial results on Avoider-Avoider games complexity, and in 2017 Bonnet et al. proved that short Avoider-Enforcer games are Co-W[1]-hard. More recently, in 2022, Miltzow and Stojaković proved that these games are NP-hard. As these games correspond to the misère version of the well-known Maker-Breaker games, introduced in 1963 and proven PSPACE-complete in 1978, one could expect these games to be PSPACE-complete too, but the question has remained open since then. Here, we prove here that both Avoider-Avoider and Avoider-Enforcer conventions are PSPACE-complete. Using the PSPACE-hardness of Avoider-Enforcer, we provide in appendix proofs that some particular Avoider-Enforcer games also are.

studied positional games on vertices. In this game, two players, Dominator and Staller, alternately claim an unclaimed vertex of a given graph G. If at some point the set of vertices claimed by Dominator is a dominating set, she wins; otherwise, i.e. if Staller manages to isolate a vertex by claiming all its closed neighborhood, Staller wins. Given a graph G and a first player, Dominator or Staller must have a winning strategy. We are interested in the computational complexity of determining which player has such a strategy. This problem is known to be PSPACE-complete on bipartite graphs of bounded degree and split graphs; polynomial on cographs, outerplanar graphs, and block graphs; and in NP for interval graphs. In this paper, we consider the parameterized complexity of this game. We start by considering as a parameter the number of moves of both players. We prove that for the general framework of Maker-Breaker positional games in hypergraphs, determining whether Breaker can claim a transversal of the hypergraph in k moves is W[2]-complete, in contrast to the problem of determining whether Maker can claim all the vertices of a hyperedge in k moves, which is known to be W[1]-complete since 2017. These two hardness results are then applied to the Maker-Breaker domination game, proving that it is W[2]-complete to decide if Dominator can dominate the graph in k moves and W[1]-complete to decide if Staller can isolate a vertex in k moves. Next, we provide FPT algorithms for the Maker-Breaker domination game parameterized by the neighborhood diversity, the modular width, the P4-fewness, the distance to cluster, and the feedback edge number.

For the buffet, the waiter of a restaurant gets a large stack of pancakes from the overworked cook. As usual, one side is burnt, and as the level of batter decreases, the pancakes became smaller and smaller. Hence, the waiter ends up with a stack of one-sided burnt pancakes sorted by size, with the larger at the bottom and burnt side up. However, the waiter cannot serve them this way. He needs to turn all the burnt sides down, without changing the order. Having only a spatula, he can only perform flips to the top of the stack. How can he perform this transformation in a minimum number of flips? Having n pancakes, this problem can be modeled in the burnt pancake graph, having 2^n*n! vertices, where each possible stack of pancakes corresponds to a vertex expressed by a permutation of size n, where the pancakes are ordered by size, and the pancake numbers are multiplied by -1, if the corresponding pancake has the burnt side side up. An edge exists in this graph, if the corresponding stacks can be reached from each other by one flip. Let T(n) be the minimum number of flips to sort the stack of n pancakes (-1,...,-n). General burnt pancake sorting has been introduced by Bill Gates and Papadimitriou. The instance (-1,...,-n) has strong relevance because of its easy structure and as it has been shown to be a worst-case instance for several small n. Heydari and Sudborough gave the currently best upper bound of T(n), namely (3n+3)/2 for n = 3 mod 4, which later has been shown to be exact by a work of Cibulka. Except these two works, no progress regarding lower and upper bounds has been made until now. In our work, we present that (3n+3)/2 is also an upper bound of T(n) for n = 1 mod 4, which again matches the lower bound of Cibulka and thus is exact. The case of even n keeps an open problem, where two possible values for T(n) are possible, namely (3/2)n + 1 or (3/2)n + 2.

We introduce the competitive assignment problem, a two-player version of the well-known assignment problem. Given a set of tasks and a set of agents with different efficiencies for different tasks, Alice and Bob take turns picking agents one by one. Once all agents have been picked, Alice and Bob compute the optimal values s_A and s_B for the assignment problem on their respective sets of agents, i.e. they assign their own agents to tasks (with at most one agent per task and at most one task per agent) so as to maximize the sum of the efficiencies. The score of the game is then defined as s_A-s_B. Alice aims at maximizing the score, while Bob aims at minimizing it. This problem can model drafts in sports and card games, or more generally situations where two entities fight for the same resources and then use them to compete against each other. We show that the problem is PSPACE-complete, even restricted to agents that have at most two nonzero efficiencies. On the other hand, in the case of agents having at most one nonzero efficiency, the problem lies in XP parameterized by the number of tasks, and the optimal score can be computed in linear time when there are only two tasks.