12 Search Results for "Feghali, Carl"

Document
DOI: 10.4230/LIPIcs.STACS.2026.73
Colouring Probe H-Free Graphs

Authors: Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen

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

Abstract
The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G,P,N) consists of a graph G = (V,E), together with a set P ⊆ V of probes and an independent set N = V ⧵ P of non-probes, such that G+F is H-free for some edge set F ⊆ binom(N,2). We show the following: - We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. - We fully classify 3-Colouring on partitioned probe P_t-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on P_t-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P₅-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P₅-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P₅-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P₅-free graphs but NP-complete for partitioned probe P₅-free graphs. In particular, unlike the class of 3-colourable P₅-free graphs, the class of 3-colourable probe P₅-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P₅-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P₅-free graphs.
Cite as

Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen. Colouring Probe H-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paulusma_et_al:LIPIcs.STACS.2026.73,
  author =	{Paulusma, Dani\"{e}l and Rauch, Johannes and van Leeuwen, Erik Jan},
  title =	{{Colouring Probe H-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{73:1--73:20},
  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.73},
  URN =		{urn:nbn:de:0030-drops-255621},
  doi =		{10.4230/LIPIcs.STACS.2026.73},
  annote =	{Keywords: colouring, probe graph, forbidden induced subgraph, complexity dichotomy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.33
Coloring Reconfiguration Under Color Swapping

Authors: Janosch Fuchs, Rin Saito, Tatsuhiro Suga, Takahiro Suzuki, and Yuma Tamura

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

Abstract
In the Coloring Reconfiguration problem, we are given two proper k-colorings of a graph and asked to decide whether one can be transformed into the other by repeatedly applying a specified recoloring rule, while maintaining a proper coloring throughout. For this problem, two recoloring rules have been widely studied: single-vertex recoloring and Kempe chain recoloring. In this paper, we introduce a new rule, called color swapping, where two adjacent vertices may exchange their colors, so that the resulting coloring remains proper, and study the computational complexity of the problem under this rule. We first establish a complexity dichotomy with respect to k: the problem is solvable in polynomial time for k ≤ 2, and is PSPACE-complete for k ≥ 3. We further show that the problem remains PSPACE-complete even on restricted graph classes, including bipartite graphs, split graphs, and planar graphs of bounded degree. In contrast, we present polynomial-time algorithms for several graph classes: for paths when k = 3, for split graphs when k is fixed, and for cographs when k is arbitrary.
Cite as

Janosch Fuchs, Rin Saito, Tatsuhiro Suga, Takahiro Suzuki, and Yuma Tamura. Coloring Reconfiguration Under Color Swapping. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fuchs_et_al:LIPIcs.ISAAC.2025.33,
  author =	{Fuchs, Janosch and Saito, Rin and Suga, Tatsuhiro and Suzuki, Takahiro and Tamura, Yuma},
  title =	{{Coloring Reconfiguration Under Color Swapping}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{33:1--33:21},
  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.33},
  URN =		{urn:nbn:de:0030-drops-249411},
  doi =		{10.4230/LIPIcs.ISAAC.2025.33},
  annote =	{Keywords: Combinatorial reconfiguration, graph coloring, PSPACE-complete, graph algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.4
Finding d-Cuts in Claw-Free Graphs

Authors: Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith

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

Abstract
The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets B and R such that the edges between B and R form a matching, that is, every vertex in B has at most one neighbour in R, and vice versa. If for some integer d ≥ 1, we allow every vertex in B to have at most d neighbours in R, and vice versa, we obtain the more general problem d-Cut. It is known that d-Cut is NP-complete for every d ≥ 1. However, for claw-free graphs, it is only known that d-Cut is polynomial-time solvable for d = 1 and NP-complete for d ≥ 3. We resolve the missing case d = 2 by proving NP-completeness. This follows from our more general study, in which we also bound the maximum degree. That is, we prove that for every d ≥ 2, d-Cut, restricted to claw-free graphs of maximum degree p, is constant-time solvable if p ≤ 2d+1 and NP-complete if p ≥ 2d+3. Moreover, in the former case, we can find a d-cut in linear time. We also show how our positive results for claw-free graphs can be generalized to S_{1^t,𝓁}-free graphs where S_{1^t,𝓁} is the graph obtained from a star on t+2 vertices by subdividing one of its edges exactly 𝓁 times.
Cite as

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith. Finding d-Cuts in Claw-Free Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2025.4,
  author =	{Ahn, Jungho and Eagling-Vose, Tala and Lucke, Felicia and Paulusma, Dani\"{e}l and Smith, Siani},
  title =	{{Finding d-Cuts in Claw-Free Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{4:1--4: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.4},
  URN =		{urn:nbn:de:0030-drops-249121},
  doi =		{10.4230/LIPIcs.ISAAC.2025.4},
  annote =	{Keywords: matching cut, d-cut, claw-free, maximum degree}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.7
Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion

Authors: Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A replacement action is a function ℒ that maps each graph H to a collection of graphs of size at most |V(H)|. Given a graph class ℋ, we consider a general family of graph modification problems, called ℒ-Replacement to ℋ, where the input is a graph G and the question is whether it is possible to replace some induced subgraph H₁ of G on at most k vertices by a graph H₂ in ℒ(H₁) so that the resulting graph belongs to ℋ. ℒ-Replacement to ℋ can simulate many graph modification problems including vertex deletion, edge deletion/addition/edition/contraction, vertex identification, subgraph complementation, independent set deletion, (induced) matching deletion/contraction, etc. We present two algorithms. The first one solves ℒ-Replacement to ℋ in time 2^poly(k) ⋅ |V(G)|² for every minor-closed graph class ℋ, where poly is a polynomial whose degree depends on ℋ, under a mild technical condition on ℒ. This generalizes the results of Morelle, Sau, Stamoulis, and Thilikos [ICALP 2020, ICALP 2023] for the particular case of Vertex Deletion to ℋ within the same running time. Our second algorithm is an improvement of the first one when ℋ is the class of graphs embeddable in a surface of Euler genus at most g and runs in time 2^𝒪(k⁹) ⋅ |V(G)|², where the 𝒪(⋅) notation depends on g. To the best of our knowledge, these are the first parameterized algorithms with a reasonable parametric dependence for such a general family of graph modification problems to minor-closed classes.
Cite as

Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos. Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{morelle_et_al:LIPIcs.ESA.2025.7,
  author =	{Morelle, Laure and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Graph Modification of Bounded Size to Minor-Closed Classes as Fast as Vertex Deletion}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.7},
  URN =		{urn:nbn:de:0030-drops-244751},
  doi =		{10.4230/LIPIcs.ESA.2025.7},
  annote =	{Keywords: Graph modification problems, Parameterized complexity, Graph minors, Flat Wall theorem, Irrelevant vertex technique, Algorithmic meta-theorem, Parametric dependence, Dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.29
The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration

Authors: Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, and Théo Pierron

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A dominating set of a graph G = (V,E) is a set of vertices D ⊆ V whose closed neighborhood is V, i.e., N[D] = V. We view a dominating set as a collection of tokens placed on the vertices of D. In the token sliding variant of the Dominating Set Reconfiguration problem (TS-DSR), we seek to transform a source dominating set into a target dominating set in G by sliding tokens along edges, and while maintaining a dominating set all along the transformation. TS-DSR is known to be PSPACE-complete even restricted to graphs of pathwidth w, for some non-explicit constant w and to be XL-complete parameterized by the size k of the solution. The first contribution of this article consists in using a novel approach to provide the first explicit constant for which the TS-DSR problem is PSPACE-complete, a question that was left open in the literature. From a parameterized complexity perspective, the token jumping variant of DSR, i.e., where tokens can jump to arbitrary vertices, is known to be FPT when parameterized by the size of the dominating sets on nowhere dense classes of graphs. But, in contrast, no non-trivial result was known about TS-DSR. We prove that DSR is actually much harder in the sliding model since it is XL-complete when restricted to bounded pathwidth graphs and even when parameterized by k plus the feedback vertex set number of the graph. This gives, for the first time, a difference of behavior between the complexity under token sliding and token jumping for some problem on graphs of bounded treewidth. All our results are obtained using a brand new method, based on the hardness of the so-called Tape Reconfiguration problem, a problem we believe to be of independent interest. We complement these hardness results with a positive result showing that DSR (parameterized by k) in the sliding model is FPT on planar graphs, also answering an open problem from the literature.
Cite as

Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, and Théo Pierron. The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ESA.2025.29,
  author =	{Bousquet, Nicolas and Deschamps, Quentin and Mary, Arnaud and Mouawad, Amer E. and Pierron, Th\'{e}o},
  title =	{{The Tape Reconfiguration Problem and Its Consequences for Dominating Set Reconfiguration}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.29},
  URN =		{urn:nbn:de:0030-drops-244974},
  doi =		{10.4230/LIPIcs.ESA.2025.29},
  annote =	{Keywords: combinatorial reconfiguration, parameterized complexity, structural graph parameters, treewidth, dominating set}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.40
Maximum List r-Colorable Induced Subgraphs in kP₃-Free Graphs

Authors: Esther Galby, Paloma T. Lima, Andrea Munaro, and Amir Nikabadi

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We show that, for every fixed positive integers r and k, Max-Weight List r-Colorable Induced Subgraph admits a polynomial-time algorithm on kP₃-free graphs. This problem is a common generalization of Max-Weight Independent Set, Odd Cycle Transversal and List r-Coloring, among others. Our result has several consequences. First, it implies that, for every fixed r ≥ 5, assuming 𝖯 ≠ NP, Max-Weight List r-Colorable Induced Subgraph is polynomial-time solvable on H-free graphs if and only if H is an induced subgraph of either kP₃ or P₅+kP₁, for some k ≥ 1. Second, it makes considerable progress toward a complexity dichotomy for Odd Cycle Transversal on H-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rzążewski, Saurabh, and Sharma [ACM Trans. Algorithms 2025]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that List r-Coloring on kP₃-free graphs is polynomial-time solvable for every fixed r and k. We also consider two natural distance-d generalizations of Max-Weight Independent Set and List r-Coloring and provide polynomial-time algorithms on kP₃-free graphs for every fixed integers r, k, and d ≥ 6.
Cite as

Esther Galby, Paloma T. Lima, Andrea Munaro, and Amir Nikabadi. Maximum List r-Colorable Induced Subgraphs in kP₃-Free Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.ESA.2025.40,
  author =	{Galby, Esther and Lima, Paloma T. and Munaro, Andrea and Nikabadi, Amir},
  title =	{{Maximum List r-Colorable Induced Subgraphs in kP₃-Free Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{40:1--40:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.40},
  URN =		{urn:nbn:de:0030-drops-245086},
  doi =		{10.4230/LIPIcs.ESA.2025.40},
  annote =	{Keywords: Hereditary classes, list coloring, odd cycle transversal, independent set}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.31
Matching Cuts in Graphs of High Girth and H-Free Graphs

Authors: Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a connected graph has a perfect matching that contains a matching cut. Both Matching Cut and Disconnected Perfect Matching are NP-complete for planar graphs of girth 5, whereas Perfect Matching Cut is known to be NP-complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that Matching Cut and Disconnected Perfect Matching are also NP-complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Our result for Matching Cut resolves a 20-year old open problem. We also show that the more general problem d-Cut, for every fixed d ≥ 1, is NP-complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Furthermore, we show that Matching Cut, Perfect Matching Cut and Disconnected Perfect Matching are NP-complete for H-free graphs whenever H contains a connected component with two vertices of degree at least 3. Afterwards, we update the state-of-the-art summaries for H-free graphs and compare them with each other, and with a known and full classification of the Maximum Matching Cut problem, which is to determine a largest matching cut of a graph G. Finally, by combining existing results, we obtain a complete complexity classification of Perfect Matching Cut for H-subgraph-free graphs where H is any finite set of graphs.
Cite as

Carl Feghali, Felicia Lucke, Daniël Paulusma, and Bernard Ries. Matching Cuts in Graphs of High Girth and H-Free Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{feghali_et_al:LIPIcs.ISAAC.2023.31,
  author =	{Feghali, Carl and Lucke, Felicia and Paulusma, Dani\"{e}l and Ries, Bernard},
  title =	{{Matching Cuts in Graphs of High Girth and H-Free Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.31},
  URN =		{urn:nbn:de:0030-drops-193332},
  doi =		{10.4230/LIPIcs.ISAAC.2023.31},
  annote =	{Keywords: matching cut, perfect matching, girth, H-free graph}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.82
Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs

Authors: Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that both problems are polynomial-time solvable for sP₃-free graphs for every integer s ≥ 1; here, the graph sP₃ denotes the disjoint union of s paths on three vertices. Our results show that both problems exhibit the same behaviour on H-free graphs (subject to some open cases). This is in part explained by a new general algorithm we design for finding in a graph G a largest induced subgraph whose blocks belong to some finite class C of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on H-free graphs.
Cite as

Giacomo Paesani, Daniël Paulusma, and Paweł Rzążewski. Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 82:1-82:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{paesani_et_al:LIPIcs.MFCS.2021.82,
  author =	{Paesani, Giacomo and Paulusma, Dani\"{e}l and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{82:1--82:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.82},
  URN =		{urn:nbn:de:0030-drops-145224},
  doi =		{10.4230/LIPIcs.MFCS.2021.82},
  annote =	{Keywords: Feedback vertex set, even cycle transversal, odd cactus, forest, block}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.16
Cyclability in Graph Classes

Authors: Christophe Crespelle, Carl Feghali, and Petr A. Golovach

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
A subset T subseteq V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every subset of vertices of G of size at most k is cyclable. The Terminal Cyclability problem asks, given a graph G and a set T of vertices, whether T is cyclable, and the k-Cyclability problem asks, given a graph G and a positive integer k, whether G is k-cyclable. These problems are generalizations of the classical Hamiltonian Cycle problem. We initiate the study of these problems for graph classes that admit polynomial algorithms for Hamiltonian Cycle. We show that Terminal Cyclability can be solved in linear time for interval graphs, bipartite permutation graphs and cographs. Moreover, we construct certifying algorithms that either produce a solution, that is, a cycle, or output a graph separator that certifies a no-answer. We use these results to show that k-Cyclability can be solved in polynomial time when restricted to the aforementioned graph classes.
Cite as

Christophe Crespelle, Carl Feghali, and Petr A. Golovach. Cyclability in Graph Classes. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{crespelle_et_al:LIPIcs.ISAAC.2019.16,
  author =	{Crespelle, Christophe and Feghali, Carl and Golovach, Petr A.},
  title =	{{Cyclability in Graph Classes}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{16:1--16:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.16},
  URN =		{urn:nbn:de:0030-drops-115128},
  doi =		{10.4230/LIPIcs.ISAAC.2019.16},
  annote =	{Keywords: Cyclability, interval graphs, bipartite permutation graphs, cographs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.5
Colouring (P_r+P_s)-Free Graphs

Authors: Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, and Veronika Slívová

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u) subseteq {1,...,k}, then we obtain the List k-Colouring problem. A graph G is H-free if G does not contain H as an induced subgraph. We continue an extensive study into the complexity of these two problems for H-free graphs. We prove that List 3-Colouring is polynomial-time solvable for (P_2+P_5)-free graphs and for (P_3+P_4)-free graphs. Combining our results with known results yields complete complexity classifications of 3-Colouring and List 3-Colouring on H-free graphs for all graphs H up to seven vertices. We also prove that 5-Colouring is NP-complete for (P_3+P_5)-free graphs.
Cite as

Tereza Klimošová, Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (P_r+P_s)-Free Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{klimosova_et_al:LIPIcs.ISAAC.2018.5,
  author =	{Klimo\v{s}ov\'{a}, Tereza and Mal{\'\i}k, Josef and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Novotn\'{a}, Jana and Paulusma, Dani\"{e}l and Sl{\'\i}vov\'{a}, Veronika},
  title =	{{Colouring (P\underliner+P\underlines)-Free Graphs}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.5},
  URN =		{urn:nbn:de:0030-drops-99533},
  doi =		{10.4230/LIPIcs.ISAAC.2018.5},
  annote =	{Keywords: vertex colouring, H-free graph, linear forest}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.16
Independent Feedback Vertex Set for P_5-free Graphs

Authors: Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k>=0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding if a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P_4-free graphs. We show that it remains in P for P_5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks if a graph has an independent odd cycle transversal of size at most k for a given integer k>=0.
Cite as

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent Feedback Vertex Set for P_5-free Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.ISAAC.2017.16,
  author =	{Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l},
  title =	{{Independent Feedback Vertex Set for P\underline5-free Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.16},
  URN =		{urn:nbn:de:0030-drops-82308},
  doi =		{10.4230/LIPIcs.ISAAC.2017.16},
  annote =	{Keywords: feedback vertex set, odd cycle transversal, independent set, H-free graph}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.70
Recognizing Graphs Close to Bipartite Graphs

Authors: Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We continue research into a well-studied family of problems that ask if the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We let G be the class of k-degenerate graphs. The problem is known to be polynomial-time solvable if k=0 (bipartite graphs) and NP-complete if k=1 (near-bipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomial-time solvability for graphs of diameter 2. We show that recognizing near-bipartite graphs of diameter 3 is NP-complete resolving their open problem. To answer another open problem, we consider graphs of maximum degree D on n vertices. We show how to find A and B in O(n) time for k=1 and D=3, and in O(n^2) time for k >= 2 and D >= 4. These results also provide an algorithmic version of a result of Catlin [JCTB, 1979] and enable us to complete the complexity classification of another problem: finding a path in the vertex colouring reconfiguration graph between two given k-colourings of a graph of bounded maximum degree.
Cite as

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Recognizing Graphs Close to Bipartite Graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.MFCS.2017.70,
  author =	{Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l},
  title =	{{Recognizing Graphs Close to Bipartite Graphs}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.70},
  URN =		{urn:nbn:de:0030-drops-80740},
  doi =		{10.4230/LIPIcs.MFCS.2017.70},
  annote =	{Keywords: degenerate graphs, near-bipartite graphs, reconfiguration graphs}
}
  • Refine by Type
  • 12 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 5 2025
  • 1 2023
  • 1 2021
  • 1 2019
  • Show More...

  • Refine by Author
  • 7 Paulusma, Daniël
  • 4 Feghali, Carl
  • 2 Bonamy, Marthe
  • 2 Dabrowski, Konrad K.
  • 2 Johnson, Matthew
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Graph algorithms analysis
  • 3 Mathematics of computing → Graph algorithms
  • 3 Mathematics of computing → Graph theory
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 3 H-free graph
  • 2 independent set
  • 2 matching cut
  • 2 odd cycle transversal
  • 1 Algorithmic meta-theorem
  • 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