Skip to main content

Research Repository

Advanced Search

Professor Daniel Paulusma's Outputs (311)

Bounding the mim-width of hereditary graph classes (2020)
Presentation / Conference Contribution
Brettell, N., Horsfield, J., Munaro, A., Paesani, G., & Paulusma, D. (2020, December). Bounding the mim-width of hereditary graph classes. Presented at IPEC 2020

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.

Steiner trees for hereditary graph classes (2020)
Presentation / Conference Contribution
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. J. (2020, May). Steiner trees for hereditary graph classes. Presented at LATIN 2020, São Paulo

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)
Presentation / Conference Contribution
Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2020, June). Clique-Width: Harnessing the Power of Atoms. Presented at WG 2020, Leeds, England

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)
Presentation / Conference Contribution
Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2020, December). Computing subset transversals in H-free graphs. Presented at WG 2020, Leeds, England

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)
Presentation / Conference Contribution
Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020, September). Acyclic, star and injective colouring: a complexity picture for H-free graphs. Presented at ESA 2020, Pisa, Italy (Virtual Event)

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.

Simple games versus weighted voting games: bounding the critical threshold value (2019)
Journal Article
Hof, F., Kern, W., Kurz, S., Pashkovich, K., & Paulusma, D. (2020). Simple games versus weighted voting games: bounding the critical threshold value. Social Choice and Welfare, 54(4), 609-621. https://doi.org/10.1007/s00355-019-01221-6

A simple game (N; v) is given by a set N of n players and a partition of 2N into a set L of losing coalitions L with value v(L) = 0 that is closed under taking subsets and a set W of winning coalitions W with value v(W) = 1. We let = minp>0;p6=0 maxW... Read More about Simple games versus weighted voting games: bounding the critical threshold value.

Clique-width and well-quasi ordering of triangle-free graph classes (2019)
Journal Article
Dabrowski, K., Lozin, V., & Paulusma, D. (2020). Clique-width and well-quasi ordering of triangle-free graph classes. Journal of Computer and System Sciences, 108, 64-91. https://doi.org/10.1016/j.jcss.2019.09.001

We obtain a complete classification of graphs H for which the class of -free graphs is well-quasi-ordered by the induced subgraph relation and an almost complete classification of graphs H for which the class of -free graphs has bounded clique-width.... Read More about Clique-width and well-quasi ordering of triangle-free graph classes.

Colouring H-free graphs of bounded diameter (2019)
Presentation / Conference Contribution
Martin, B., Paulusma, D., & Smith, S. (2019, August). Colouring H-free graphs of bounded diameter. Presented at MFCS 2019, Aachen, Germany

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is kn... Read More about Colouring H-free graphs of bounded diameter.

Tree pivot-minors and linear rank-width (2019)
Presentation / Conference Contribution
Dabrowski, K., Dross, F., Jeong, J., Kanté, M., Kwon, O., Oum, S., & Paulusma, D. (2019, July). Tree pivot-minors and linear rank-width. Presented at EuroComb 2019, Bratislava, Slovakia

Treewidth and its linear variant path-width play a central role for the graph minor relation. Rank-width and linear rank-width do the same for the graph pivot-minor relation. Robertson and Seymour (1983) proved that for every tree T there exists a co... Read More about Tree pivot-minors and linear rank-width.

Independent transversals versus transversals (2019)
Presentation / Conference Contribution
Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019, December). Independent transversals versus transversals. Presented at EuroComb 2019, Bratislava, Slovakia

We compare the minimum size of a vertex cover, feedback vertex set and odd cycle transversal of a graph with the minimum size of the corresponding variants in which the transversal must be an independent set. We investigate for which graphs H the two... Read More about Independent transversals versus transversals.

On cycle transversals and their connected variants in the absence of a small linear forest (2019)
Presentation / Conference Contribution
Feghali, C., Johnson, M., Paesani, G., & Paulusma, D. (2019, August). On cycle transversals and their connected variants in the absence of a small linear forest. Presented at FCT 2019, Copenhagen, Denmark

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.

Clique-width for hereditary graph classes (2019)
Journal Article
Dabrowski, K., Johnson, M., & Paulusma, D. (online). Clique-width for hereditary graph classes. https://doi.org/10.1017/9781108649094.002

Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class G is bounded by a constant, a wide range of problems that are NP-complete in general can be shown to be po... Read More about Clique-width for hereditary graph classes.

Colouring Square-Free Graphs without Long Induced Paths (2019)
Journal Article
Gaspers, S., Huang, S., & Paulusma, D. (2019). Colouring Square-Free Graphs without Long Induced Paths. Journal of Computer and System Sciences, 106, 60-79. https://doi.org/10.1016/j.jcss.2019.06.002

The complexity of Colouring is fully understood for H-free graphs, but there are still major complexity gaps if two induced subgraphs and are forbidden. Let be the s-vertex cycle and be the t-vertex path . We show that Colouring is polynomial-time so... Read More about Colouring Square-Free Graphs without Long Induced Paths.

Connected vertex cover for (sP1+P5)-free graphs (2019)
Journal Article
Johnson, M., Paesani, G., & Paulusma, D. (2020). Connected vertex cover for (sP1+P5)-free graphs. Algorithmica, 82(1), 20-40. https://doi.org/10.1007/s00453-019-00601-9

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-... Read More about Connected vertex cover for (sP1+P5)-free graphs.