Skip to main content

Research Repository

Advanced Search

Professor Daniel Paulusma's Outputs (315)

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.

Filling the complexity gaps for colouring planar and bounded degree graphs (2019)
Journal Article
Dabrowski, K., Dross, F., Johnson, M., & Paulusma, D. (2019). Filling the complexity gaps for colouring planar and bounded degree graphs. Journal of Graph Theory, 92(4), 377-393. https://doi.org/10.1002/jgt.22459

A colouring of a graphGVE=( ,)is a function→cV:{1, 2,...}such that≠cucv() ()for every∈uvE.Ak‐regular list assignment ofGis a functionLwith domainVsuch that for every∈uV,Lu()is asubset of{1, 2,...}of sizek. A colouringcofGrespects ak‐regular list assi... Read More about Filling the complexity gaps for colouring planar and bounded degree graphs.

Using contracted solution graphs for solving reconfiguration problems (2019)
Journal Article
Bonsma, P., & Paulusma, D. (2019). Using contracted solution graphs for solving reconfiguration problems. Acta Informatica, 56(7-8), 619-648. https://doi.org/10.1007/s00236-019-00336-8

We introduce in a general setting a dynamic programming method for solving reconfiguration problems. Our method is based on contracted solution graphs, which are obtained from solution graphs by performing an appropriate series of edge contractions t... Read More about Using contracted solution graphs for solving reconfiguration problems.

Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 (2019)
Journal Article
Golovach, P., Heggernes, P., Kratch, D., Lima, P., & Paulusma, D. (2019). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Algorithmica, 81(7), 2795-2828. https://doi.org/10.1007/s00453-019-00555-y

Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity... Read More about Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2.

Classifying k-Edge Colouring for H-free Graphs (2019)
Journal Article
Galby, E., Lima, P., Paulusma, D., & Ries, B. (2019). Classifying k-Edge Colouring for H-free Graphs. Information Processing Letters, 146, 39-43. https://doi.org/10.1016/j.ipl.2019.02.006

A graph is H-free if it does not contain an induced subgraph isomorphic to H. For every integer k and every graph H, we determine the computational complexity of k-Edge Colouring for H-free graphs.

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy (2019)
Presentation / Conference Contribution
Bonamy, M., Dabrowski, K. K., Johnson, M., & Paulusma, D. (2019, December). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Presented at WADS 2019, Edmonton, Canada

We almost completely resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs H1 and H2. Schweitzer settled the complexity of this problem restricted to (H1;H2)-free graphs for a... Read More about Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy.

Finding a small number of colourful components (2019)
Presentation / Conference Contribution
Bulteau, L., Dabrowski, K., Fertin, G., Johnson, M., Paulusma, D., & Vialette, S. (2019, December). Finding a small number of colourful components. Presented at CPM 2019, Pisa, Italy

Surjective H-Colouring over reflexive digraphs (2018)
Journal Article
Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431

The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality,... Read More about Surjective H-Colouring over reflexive digraphs.

Hereditary graph classes: when the complexities of coloring and clique cover coincide (2018)
Journal Article
Blanché, A., Dabrowski, K., Johnson, M., & Paulusma, D. (2019). Hereditary graph classes: when the complexities of coloring and clique cover coincide. Journal of Graph Theory, 91(3), 267-289. https://doi.org/10.1002/jgt.22431

graph is (H1;H2)-free for a pair of graphs H1;H2 if it contains no induced subgraph isomorphic to H1 or H2. In 2001, Král’, Kratochvíl, Tuza, and Woeginger initiated a study into the complexity of Colouring for (H1;H2)-free graphs. Since then, others... Read More about Hereditary graph classes: when the complexities of coloring and clique cover coincide.

On the parameterized complexity of (k,s)-SAT (2018)
Journal Article
Paulusma, D., & Szeider, S. (2019). On the parameterized complexity of (k,s)-SAT. Information Processing Letters, 43, 34-36. https://doi.org/10.1016/j.ipl.2018.11.005

Let (k, s)-SAT be the k-SAT problem restricted to formulas in which each variable occurs in at most s clauses. It is well known that (3, 3)-SAT is trivial and (3, 4)-SAT is NP-complete. Answering a question posed by Iwama and Takaki (DMTCS 1997), Ber... Read More about On the parameterized complexity of (k,s)-SAT.

Colouring (Pr+Ps)-free graphs (2018)
Presentation / Conference Contribution
Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2018, December). Colouring (Pr+Ps)-free graphs. Presented at 29th International Symposium on Algorithms and Computation (ISAAC 2018)., Jiaoxi, Yilan County, Taiwan

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.

Critical vertices and edges in H-free graphs (2018)
Journal Article
Paulusma, D., Picouleau, C., & Ries, B. (2019). Critical vertices and edges in H-free graphs. Discrete Applied Mathematics, 257, 361-367. https://doi.org/10.1016/j.dam.2018.08.016

A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of deciding whether a graph has a critical vertex or edge, respectively. We give a complexity dichotomy for both proble... Read More about Critical vertices and edges in H-free graphs.

Computing small pivot-minors (2018)
Presentation / Conference Contribution
Dabrowski, K. K., Dross, F., Jeong, J., Kanté, M. M., Kwon, O., Oum, S., & Paulusma, D. (2018, June). Computing small pivot-minors. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany

A graph G contains a graph H as a pivot-minor if H can be obtained from G by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. However, so far, pivot-minors have only been studied... Read More about Computing small pivot-minors.

Connected Vertex Cover for (sP1+P5)-free graphs (2018)
Presentation / Conference Contribution
Johnson, M., Paesani, G., & Paulusma, D. (2018, June). Connected Vertex Cover for (sP1+P5)-free graphs. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany

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.

Simple games versus weighted voting games (2018)
Presentation / Conference Contribution
Hof, F., Kern, W., Kurz, S., & Paulusma, D. (2018, September). Simple games versus weighted voting games. Presented at 11th International Symposium on Algorithmic Game Theory (SAGT 2018)., Beijing, China

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 v(W)=1 . Simple games with α=minp≥0maxW∈W,L... Read More about Simple games versus weighted voting games.

Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs (2018)
Journal Article
Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2018). Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs. Theoretical Computer Science, 746, 49-72. https://doi.org/10.1016/j.tcs.2018.06.023

We study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter π of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number χ, clique number ω and... Read More about Contraction and Deletion Blockers for Perfect Graphs and H -free Graphs.