9 citations · 11 across the 17 of their papers we have counts for
4 papers · 1 filter
On the Complexity of Vertex-Splitting Into an Interval Graph
Faisal N. Abu-Khzam, Dipayan Chakraborty, Lucas Isenmann +1
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 orig…
Bounded degree QBF and positional games
Nacim Oijid
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…
On the Parameterized Complexity of Relaxations of Clique
Ambroise Baril, Antoine Castillon, Nacim Oijid
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 suff…
Complexity of Maker-Breaker Games on Edge Sets of Graphs
Eric Duchêne, Valentin Gledel, Fionn Mc Inerney +4
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 -game. Maker wins if s…