Bounding the mim-width of hereditary graph classes (2020)
Conference Proceeding
Brettell, N., Horsfield, J., Munaro, A., Paesani, G., & Paulusma, D. (2020). Bounding the mim-width of hereditary graph classes. In Y. Cao, & M. Pilipczuk (Eds.), 15th International Symposium on Parameterized and Exact Computation (187-199). https://doi.org/10.4230/lipics.ipec.2020.6

A large number of NP-hard graph problems are solvable in XP time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In thi... Read More about Bounding the mim-width of hereditary graph classes.

Contracting to a longest path in H-free graphs (2020)
Conference Proceeding
Kern, W., & Paulusma, D. (2020). Contracting to a longest path in H-free graphs. In Y. Cao, S. Cheng, & M. Li (Eds.), 31st International Symposium on Algorithms and Computation (ISAAC 2020) (22:1-22:18). https://doi.org/10.4230/lipics.isaac.2020.22

The Path Contraction problem has as input a graph G and an integer k and is to decide if G can be modified to the k-vertex path P_k by a sequence of edge contractions. A graph G is H-free for some graph H if G does not contain H as an induced subgrap... Read More about Contracting to a longest path in H-free graphs.

Steiner trees for hereditary graph classes (2020)
Conference Proceeding
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2021). Steiner trees for hereditary graph classes. In Y. Kohayakawa, & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (613-624). https://doi.org/10.1007/978-3-030-61792-9_48

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (... Read More about Steiner trees for hereditary graph classes.

Clique-Width: Harnessing the Power of Atoms (2020)
Conference Proceeding
Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2020). Clique-Width: Harnessing the Power of Atoms. In I. Adler, & H. Müller (Eds.), Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers (119-133). https://doi.org/10.1007/978-3-030-60440-0_10

Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class G if they are so on the atoms (graphs with no clique cut-set) of... Read More about Clique-Width: Harnessing the Power of Atoms.

Computing subset transversals in H-free graphs (2020)
Conference Proceeding
Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2020). Computing subset transversals in H-free graphs. In I. Adler, & H. Müller (Eds.), WG 2020: Graph-Theoretic Concepts in Computer Science (187-199). https://doi.org/10.1007/978-3-030-60440-0_15

We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph... Read More about Computing subset transversals in H-free graphs.

Acyclic, star and injective colouring: a complexity picture for H-free graphs (2020)
Conference Proceeding
Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020). Acyclic, star and injective colouring: a complexity picture for H-free graphs. . https://doi.org/10.4230/lipics.esa.2020.22

A k-colouring c of a graph G is a mapping V(G) → {1,2,… k} such that c(u) ≠ c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. A colouring is acyclic, star, or injective if any two colour classes induce a forest, sta... Read More about Acyclic, star and injective colouring: a complexity picture for H-free graphs.

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy (2020)
Journal Article
Bonamy, M., Bousquet, N., Dabrowski, K., Johnson, M., Paulusma, D., & Pierron, T. (2021). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Algorithmica, 83(3), 822-852. https://doi.org/10.1007/s00453-020-00747-x

We resolve the computational complexity of GRAPH ISOMORPHISM for classes of graphs characterized by two forbidden induced subgraphs H_{1} and H_2 for all but six pairs (H_1,H_2). Schweitzer had previously shown that the number of open cases was finit... Read More about Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy.

Disconnected cuts in claw-free graphs (2020)
Journal Article
Martin, B., Paulusma, D., & van Leeuwen, E. (2020). Disconnected cuts in claw-free graphs. Journal of Computer and System Sciences, 113, 60-75. https://doi.org/10.1016/j.jcss.2020.04.005

A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called Disconnected Cut. This problem is known to be NP-hard on general graphs. We prove that it is polyno... Read More about Disconnected cuts in claw-free graphs.

Clique-width for graph classes closed under complementation (2020)
Journal Article
Blanché, A., Dabrowski, K., Johnson, M., Lozin, V., Paulusma, D., & Zamaraev, V. (2020). Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics, 34(2), 1107-1147. https://doi.org/10.1137/18m1235016

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We study the boundedness of cliq... Read More about Clique-width for graph classes closed under complementation.

Colouring (Pr + Ps)-Free Graphs (2020)
Journal Article
Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2020). Colouring (Pr + Ps)-Free Graphs. Algorithmica, 82(7), 1833-1858. https://doi.org/10.1007/s00453-020-00675-w

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)... Read More about Colouring (Pr + Ps)-Free Graphs.

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest (2020)
Journal Article
Dabrowski, K., Feghali, C., Johnson, M., Paesani, G., Paulusma, D., & Rzążewski, P. (2020). On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. Algorithmica, 82(10), 2841-2866. https://doi.org/10.1007/s00453-020-00706-6

A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problems FEEDBACK VERTEX SET and ODD CYCLE TRANSVERSAL by showing that they can be solved in polynomial time... Read More about On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest.