Professor Daniel Paulusma's Outputs (16)

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.

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.

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.

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.

Independent Feedback Vertex Set for P5-free Graphs (2018)
Journal Article
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent Feedback Vertex Set for P5-free Graphs. Algorithmica, 81(4), 1416-1449. https://doi.org/10.1007/s00453-018-0474-x

The NP-complete problem Feedback Vertex Set is that of deciding whether or not 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... Read More about Independent Feedback Vertex Set for P5-free Graphs.

Surjective H-colouring: New hardness results (2018)
Journal Article
Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42. https://doi.org/10.3233/com-180084

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring p... Read More about Surjective H-colouring: New hardness results.

On colouring (2P2,H)-free and (P5,H)-free graphs (2018)
Journal Article
Dabrowski, K., & Paulusma, D. (2018). On colouring (2P2,H)-free and (P5,H)-free graphs. Information Processing Letters, 134, 35-41. https://doi.org/10.1016/j.ipl.2018.02.003

The Colouring problem asks whether the vertices of a graph can be coloured with at most k colours for a given integer k in such a way that no two adjacent vertices receive the same colour. A graph is (H1,H2)-free if it has no induced subgraph isomorp... Read More about On colouring (2P2,H)-free and (P5,H)-free graphs.

Surjective H-Colouring over Reflexive Digraphs (2018)
Presentation / Conference Contribution
Larose, B., Martin, B., & Paulusma, D. (2023, February). Surjective H-Colouring over Reflexive Digraphs. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France

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.

Colouring Square-Free Graphs without Long Induced Paths (2018)
Presentation / Conference Contribution
Gaspers, S., Huang, S., & Paulusma, D. (2023, February). Colouring Square-Free Graphs without Long Induced Paths. Presented at 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a given integer k such that no two adjacent vertices are coloured alike. The complexity of Colouring is fully understood for graph classes charac... Read More about Colouring Square-Free Graphs without Long Induced Paths.

Disconnected Cuts in Claw-free Graphs (2018)
Presentation / Conference Contribution
Martin, B., Paulusma, D., & van Leeuwen, E. J. (2018, August). Disconnected Cuts in Claw-free Graphs. Presented at 26th Annual European Symposium on Algorithms (ESA 2018)., Helsinki, Finland

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. It is known that Disconnected Cut is NP-hard on general graphs, while polynomial-... Read More about Disconnected Cuts in Claw-free Graphs.

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal (2018)
Presentation / Conference Contribution
Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2018, August). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. Presented at 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK

Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if w... Read More about On the price of independence for vertex cover, feedback vertex set and odd cycle transversal.