11 Search Results for "Abu-Khzam, Faisal N."

Document
DOI: 10.4230/LIPIcs.STACS.2026.19
A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

Authors: Nicolas Bousquet and Daniel W. Cranston

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Fix a positive integer r, and a graph G that is K_{3,r}-minor-free. Let I_s and I_t be two independent sets in G, each of size k. We begin with a "token" on each vertex of I_s and seek to move all tokens to I_t, by repeated "token jumping", removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size k. Given G, I_s, and I_t, we ask whether there exists a sequence of token jumps that transforms I_s into I_t. When k is part of the input, this problem is known to be PSPACE-complete. But it was shown by Ito, Kamiński, and Ono [Ito et al., 2014] to be fixed-parameter tractable. That is, the problem can be solved in time f(k)⋅ P(n), for some function f and polynomial P, where n denotes the order of G. Here we strengthen the upper bound on the running time in terms of k by showing that the problem has a kernel of size linear in k. More precisely, we transform an arbitrary input problem on a K_{3,r}-minor-free graph (for some fixed positive integer r) into an equivalent problem on a (K_{3,r}-minor-free) graph with order O(k). This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz [Nicolas Bousquet et al., 2022] and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille [Daniel W. Cranston et al., 2024]. For planar graphs, we further strengthen this upper bound to get a kernel of size at most 42k.
Cite as

Nicolas Bousquet and Daniel W. Cranston. A Linear Kernel for Independent Set Reconfiguration in Planar Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2026.19,
  author =	{Bousquet, Nicolas and Cranston, Daniel W.},
  title =	{{A Linear Kernel for Independent Set Reconfiguration in Planar Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.19},
  URN =		{urn:nbn:de:0030-drops-255081},
  doi =		{10.4230/LIPIcs.STACS.2026.19},
  annote =	{Keywords: Reconfiguration, Independent Set, Kernel, Planar graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.50
A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs

Authors: Thekla Hamm, Sukanya Pandey, and Krisztina Szilágyi

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Given a planar graph, a subset of its vertices called terminals, and k ∈ ℕ, the Face Cover Number problem asks whether the terminals lie on the boundaries of at most k faces of some embedding of the input graph. When a plane graph is given in the input, the problem is known to have a polynomial kernel [Valentin Garnero et al., 2017]. In this paper, we present the first polynomial kernel for Face Cover Number when the input is a planar graph (without a fixed embedding). Our approach overcomes the challenge of not having a predefined set of face boundaries by building a kernel bottom-up on an SPR-tree while preserving the essential properties of the face cover along the way.
Cite as

Thekla Hamm, Sukanya Pandey, and Krisztina Szilágyi. A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hamm_et_al:LIPIcs.STACS.2026.50,
  author =	{Hamm, Thekla and Pandey, Sukanya and Szil\'{a}gyi, Krisztina},
  title =	{{A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{50:1--50:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.50},
  URN =		{urn:nbn:de:0030-drops-255392},
  doi =		{10.4230/LIPIcs.STACS.2026.50},
  annote =	{Keywords: Kernelization, Planar Graphs, SPQR-tree}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.23
Enumeration Kernels for Vertex Cover and Feedback Vertex Set

Authors: Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos, and Ignasi Sau

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creignou et al. [Theory Comput. Syst., 2017], and development in the area has started to accelerate with the work of Golovach et al. [J. Comput. Syst. Sci., 2022]. The latter introduced polynomial-delay enumeration kernels and applied them in the study of structural parameterizations of the Matching Cut problem and some variants. Few other results, mostly on Longest Path and some generalizations of Matching Cut, have also been developed. However, little success has been seen in enumeration versions of Vertex Cover and Feedback Vertex Set, some of the most studied problems in kernelization. In this paper, we address this shortcoming. Our first result is a polynomial-delay enumeration kernel with 2k vertices for Enum Vertex Cover, where we wish to list all solutions with at most k vertices. This is obtained by developing a non-trivial lifting algorithm for the classical crown decomposition reduction rule, and directly improves upon the kernel with 𝒪(k²) vertices derived from the work of Creignou et al. Our other result is a polynomial-delay enumeration kernel with 𝒪(k³) vertices and edges for Enum Feedback Vertex Set; the proof is inspired by some ideas of Thomassé [TALG, 2010], but with a weaker bound on the kernel size due to difficulties in applying the q-expansion technique.
Cite as

Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos, and Ignasi Sau. Enumeration Kernels for Vertex Cover and Feedback Vertex Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.IPEC.2025.23,
  author =	{Bougeret, Marin and C. M. Gomes, Guilherme and dos Santos, Vinicius F. and Sau, Ignasi},
  title =	{{Enumeration Kernels for Vertex Cover and Feedback Vertex Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.23},
  URN =		{urn:nbn:de:0030-drops-251552},
  doi =		{10.4230/LIPIcs.IPEC.2025.23},
  annote =	{Keywords: Kernelization, Enumeration, Vertex cover, Crown decomposition, Feedback vertex set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.48
Quadratic Kernel for Cliques or Trees Vertex Deletion

Authors: Soh Kumabe

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We consider Cliques or Trees Vertex Deletion, which is a hybrid of two fundamental parameterized problems: Cluster Vertex Deletion and Feedback Vertex Set. In this problem, we are given an undirected graph G and an integer k, and asked to find a vertex subset X of size at most k such that each connected component of G-X is either a clique or a tree. Jacob et al. (ISAAC, 2024) provided a kernel of O(k⁵) vertices for this problem, which was recently improved to O(k⁴) by Tsur (IPL, 2025). Our main result is a kernel of O(k²) vertices. This result closes the gap between the kernelization result for Feedback Vertex Set, which corresponds to the case where each connected component of G-X must be a tree. Although both cluster vertex deletion number and feedback vertex set number are well-studied structural parameters, little attention has been given to parameters that generalize both of them. In fact, the lowest common well-known generalization of them is clique-width, which is a highly general parameter. To fill the gap here, we initiate the study of the cliques or trees vertex deletion number as a structural parameter. We prove that Longest Cycle, which is a fundamental problem that does not admit o(n^k)-time algorithm unless ETH fails when k is the clique-width, becomes fixed-parameter tractable when parameterized by the cliques or trees vertex deletion number.
Cite as

Soh Kumabe. Quadratic Kernel for Cliques or Trees Vertex Deletion. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kumabe:LIPIcs.ISAAC.2025.48,
  author =	{Kumabe, Soh},
  title =	{{Quadratic Kernel for Cliques or Trees Vertex Deletion}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.48},
  URN =		{urn:nbn:de:0030-drops-249568},
  doi =		{10.4230/LIPIcs.ISAAC.2025.48},
  annote =	{Keywords: Fixed-Parameter Tractability, Kernelization, Deletion to Scattered Graph Classes, Cluster Vertex Deletion, Feedback Vertex Set}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.15
Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs

Authors: Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with the best known algorithm due to Golovach, Heggernes, Kanté, Kratsch, Sæther, and Villanger running in incremental-polynomial time. We improve on this result by providing a polynomial delay and space algorithm enumerating minimal dominating sets in chordal bipartite graphs. Additionally, we show that the total and connected variants admit polynomial and incremental-polynomial delay algorithms, respectively, within the same class. This provides an alternative proof of a result by Golovach et al. for total dominating sets, and answers an open question for the connected variant. Finally, we give evidence that the techniques used in this paper cannot be generalized to bipartite graphs for (total) minimal dominating sets, unless P = NP, and show that enumerating minimal connected dominating sets in bipartite graphs is harder than enumerating minimal transversals in general hypergraphs.
Cite as

Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes. Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{castelo_et_al:LIPIcs.WADS.2025.15,
  author =	{Castelo, Emanuel and Defrain, Oscar and C. M. Gomes, Guilherme},
  title =	{{Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.15},
  URN =		{urn:nbn:de:0030-drops-242467},
  doi =		{10.4230/LIPIcs.WADS.2025.15},
  annote =	{Keywords: algorithmic enumeration, minimal dominating sets, connected dominating sets, total dominating sets, chordal bipartite graphs, sequential method, polynomial delay}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.20
Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components

Authors: Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, and Saket Saurabh

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Motivated by the growing interest in graph clustering and the framework proposed during the Dagstuhl Seminar 23331, we consider a natural specialization of this general approach (as also suggested during the seminar). The seminar introduced a broad perspective on clustering, where the goal is to partition a graph into connected components (or "clusters") that satisfy simple structural integrity constraints - not necessarily limited to cliques. In our work, we focus on the case where each cluster is required to have bounded vertex cover number. Specifically, a connected component C satisfies this condition if there exists a set S ⊆ V(C) with |S| ≤ d such that C - S is an independent set. We study this within the framework of the {Vertex Deletion to d-Vertex Cover Components} ({Vertex Deletion to d-VCC}) problem: given a graph G and an integer k, the task is to determine whether there exists a vertex set S ⊆ V(G) of size at most k such that every connected component of G - S has vertex cover number at most d. We also examine the edge-deletion variant, {Edge Deletion to d-Vertex Cover Components} ({Edge Deletion to d-VCC}), where the goal is to delete at most k edges so that each connected component of the resulting graph has vertex cover number at most d. We obtain following results. 1) {Vertex Deletion to d-VCC} admits a kernel with {𝒪}(d⁶k³) vertices and {𝒪}(d⁹k⁴) edges. 2) {Edge Deletion to d-VCC}, admits a kernel with {𝒪}(d⁴k) vertices and {𝒪}(d⁵k) edges. Both of our kernelization algorithms run in time 𝒪(1.253^d ⋅ (kd)^{𝒪(1)} ⋅ n log n). It is important to note that, unless the Exponential Time Hypothesis (ETH) fails, the dependence on d cannot be improved to 2^{o(d)}, as the case k = 0 reduces to solving the classical Vertex Cover problem, which is known to require 2^{Ω(d)} time under ETH. A key ingredient in our kernelization algorithms is a structural result about the hereditary graph class 𝒢_d, consisting of graphs in which every connected component has vertex cover number at most d. We show that 𝒢_d admits a finite obstruction set (with respect to the induced subgraph relation) of size 2^{𝒪(d²)}, where each obstruction graph has at most 3d + 2 vertices. This combinatorial result may be of independent interest.
Cite as

Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, and Saket Saurabh. Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhyravarapu_et_al:LIPIcs.MFCS.2025.20,
  author =	{Bhyravarapu, Sriram and Kumar, Pritesh and Kundu, Madhumita and Roy, Shivesh K. and Sahiba and Saurabh, Saket},
  title =	{{Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.20},
  URN =		{urn:nbn:de:0030-drops-241276},
  doi =		{10.4230/LIPIcs.MFCS.2025.20},
  annote =	{Keywords: Parameterized complexity, Polynomial Kernels, Vertex Cover, Finite Forbidden Characterization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.16
Isometric-Universal Graphs for Trees

Authors: Edgar Baucher, François Dross, and Cyril Gavoille

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We consider the problem of finding the smallest graph that contains two input trees each with at most n vertices preserving their distances. In other words, we look for an isometric-universal graph with the minimum number of vertices for two given trees. We prove that this problem can be solved in time O(n^{5/2}log{n}). We extend this result to forests instead of trees, and propose an algorithm with running time O(n^{7/2}log{n}). As a key ingredient, we show that a smallest isometric-universal graph of two trees essentially is a tree. Furthermore, we prove that these results cannot be extended. Firstly, we show that deciding whether there exists an isometric-universal graph with t vertices for three forests is NP-complete. Secondly, we show that any smallest isometric-universal graph cannot be a tree for some families of three trees. This latter result has implications for greedy strategies solving the smallest isometric-universal graph problem.
Cite as

Edgar Baucher, François Dross, and Cyril Gavoille. Isometric-Universal Graphs for Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baucher_et_al:LIPIcs.MFCS.2025.16,
  author =	{Baucher, Edgar and Dross, Fran\c{c}ois and Gavoille, Cyril},
  title =	{{Isometric-Universal Graphs for Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.16},
  URN =		{urn:nbn:de:0030-drops-241237},
  doi =		{10.4230/LIPIcs.MFCS.2025.16},
  annote =	{Keywords: tree, forest, isometric subgraph, universal graph, distance-preserving}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.22
Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem

Authors: Ernestine Großmann, Kenneth Langedal, and Christian Schulz

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
The Maximum Weight Independent Set problem is a fundamental NP-hard problem in combinatorial optimization with several real-world applications. Given an undirected vertex-weighted graph, the problem is to find a subset of the vertices with the highest possible weight under the constraint that no two vertices in the set can share an edge. This work presents a new iterated local search heuristic called CHILS (Concurrent Hybrid Iterated Local Search). The implementation of CHILS is specifically designed to handle large graphs of varying densities. CHILS outperforms the current state-of-the-art on commonly used benchmark instances, especially on the largest instances. As an added benefit, CHILS can run in parallel to leverage the power of multicore processors. The general technique used in CHILS is a new concurrent metaheuristic called Concurrent Difference-Core Heuristic that can also be applied to other combinatorial problems.
Cite as

Ernestine Großmann, Kenneth Langedal, and Christian Schulz. Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gromann_et_al:LIPIcs.SEA.2025.22,
  author =	{Gro{\ss}mann, Ernestine and Langedal, Kenneth and Schulz, Christian},
  title =	{{Concurrent Iterated Local Search for the Maximum Weight Independent Set Problem}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.22},
  URN =		{urn:nbn:de:0030-drops-232600},
  doi =		{10.4230/LIPIcs.SEA.2025.22},
  annote =	{Keywords: Randomized Local Search, Heuristics, Maximum Weight Independent Set, Algorithm Engineering, Parallel Computing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.64
Cluster Editing on Cographs and Related Classes

Authors: Manuel Lafond, Alitzel López Sánchez, and Weidong Luo

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In the Cluster Editing problem, sometimes known as (unweighted) Correlation Clustering, we must insert and delete a minimum number of edges to achieve a graph in which every connected component is a clique. Owing to its applications in computational biology, social network analysis, machine learning, and others, this problem has been widely studied for decades and is still undergoing active research. There exist several parameterized algorithms for general graphs, but little is known about the complexity of the problem on specific classes of graphs. Among the few important results in this direction, if only deletions are allowed, the problem can be solved in polynomial time on cographs, which are the P₄-free graphs. However, the complexity of the broader editing problem on cographs is still open. We show that even on a very restricted subclass of cographs, the problem is NP-hard, W[1]-hard when parameterized by the number p of desired clusters, and that time n^o(p/log p) is forbidden under the ETH. This shows that the editing variant is substantially harder than the deletion-only case, and that hardness holds for the many superclasses of cographs (including graphs of clique-width at most 2, perfect graphs, circle graphs, permutation graphs). On the other hand, we provide an almost tight upper bound of time n^O(p), which is a consequence of a more general n^O(cw⋅p) time algorithm, where cw is the clique-width. Given that forbidding P₄s maintains NP-hardness, we look at {P₄, C₄}-free graphs, also known as trivially perfect graphs, and provide a cubic-time algorithm for this class.
Cite as

Manuel Lafond, Alitzel López Sánchez, and Weidong Luo. Cluster Editing on Cographs and Related Classes. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 64:1-64:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lafond_et_al:LIPIcs.STACS.2025.64,
  author =	{Lafond, Manuel and L\'{o}pez S\'{a}nchez, Alitzel and Luo, Weidong},
  title =	{{Cluster Editing on Cographs and Related Classes}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{64:1--64:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.64},
  URN =		{urn:nbn:de:0030-drops-228895},
  doi =		{10.4230/LIPIcs.STACS.2025.64},
  annote =	{Keywords: Cluster editing, cographs, parameterized algorithms, clique-width, trivially perfect graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.6
Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes

Authors: Faisal N. Abu-Khzam, Henning Fernau, and Kevin Mann

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
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.
Cite as

Faisal N. Abu-Khzam, Henning Fernau, and Kevin Mann. Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abukhzam_et_al:LIPIcs.MFCS.2023.6,
  author =	{Abu-Khzam, Faisal N. and Fernau, Henning and Mann, Kevin},
  title =	{{Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.6},
  URN =		{urn:nbn:de:0030-drops-185400},
  doi =		{10.4230/LIPIcs.MFCS.2023.6},
  annote =	{Keywords: special graph classes, counting problems, enumeration problems, domination problems, Roman domination}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.1
Enumerating Minimal Connected Dominating Sets

Authors: Faisal N. Abu-Khzam, Henning Fernau, Benjamin Gras, Mathieu Liedloff, and Kevin Mann

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
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.
Cite as

Faisal N. Abu-Khzam, Henning Fernau, Benjamin Gras, Mathieu Liedloff, and Kevin Mann. Enumerating Minimal Connected Dominating Sets. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abukhzam_et_al:LIPIcs.ESA.2022.1,
  author =	{Abu-Khzam, Faisal N. and Fernau, Henning and Gras, Benjamin and Liedloff, Mathieu and Mann, Kevin},
  title =	{{Enumerating Minimal Connected Dominating Sets}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{1:1--1:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.1},
  URN =		{urn:nbn:de:0030-drops-169390},
  doi =		{10.4230/LIPIcs.ESA.2022.1},
  annote =	{Keywords: enumeration problems, connected domination, degenerate graphs}
}
  • Refine by Type
  • 11 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 7 2025
  • 1 2023
  • 1 2022

  • Refine by Author
  • 2 Abu-Khzam, Faisal N.
  • 2 C. M. Gomes, Guilherme
  • 2 Fernau, Henning
  • 2 Mann, Kevin
  • 1 Baucher, Edgar
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Theory of computation → Design and analysis of algorithms
  • 2 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Enumeration
  • Show More...

  • Refine by Keyword
  • 3 Kernelization
  • 2 enumeration problems
  • 1 Algorithm Engineering
  • 1 Cluster Vertex Deletion
  • 1 Cluster editing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact