Skip to main content

Research Repository

Advanced Search

Outputs (287)

Computing balanced solutions for large international kidney exchange schemes (2024)
Journal Article
Benedek, M., Biró, P., Paulusma, D., & Ye, X. (2024). Computing balanced solutions for large international kidney exchange schemes. Autonomous Agents and Multi-Agent Systems, 38(1), Article 18. https://doi.org/10.1007/s10458-024-09645-w

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient–donor pools. We consider a recently introduced credit system. In each round, countr... Read More about Computing balanced solutions for large international kidney exchange schemes.

Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius (2023)
Presentation / Conference Contribution
Lucke, F., Paulusma, D., & Ries, B. (2023). Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (64:1-64:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.64

The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of G. Both Matching Cut and Perfect Matching Cut are known to be NP-complete, leading to many complexity re... Read More about Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius.

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs (2023)
Presentation / Conference Contribution
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57

For any finite set H = {H1,. .. , Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,. .. , Hp as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed... Read More about Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.

The Complexity of Matching Games: A Survey (2023)
Journal Article
Benedek, M., Biro, P., Johnson, M., Paulusma, D., & Ye, X. (2023). The Complexity of Matching Games: A Survey. Journal of Artificial Intelligence Research, 77, 459-485. https://doi.org/10.1613/jair.1.14281

Matching games naturally generalize assignment games, a well-known class of cooperative games. Interest in matching games has grown recently due to some breakthrough results and new applications. This state-of-the-art survey provides an overview of m... Read More about The Complexity of Matching Games: A Survey.

Finding Matching Cuts in H-Free Graphs (2023)
Journal Article
Lucke, F., Paulusma, D., & Ries, B. (2023). Finding Matching Cuts in H-Free Graphs. Algorithmica, https://doi.org/10.1007/s00453-023-01137-9

The well-known NP-complete problem MATCHING CUT is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for MATCHING CUT restricted to H-free graphs, that is, graphs that do not contain some fixed... Read More about Finding Matching Cuts in H-Free Graphs.

The Complexity of L(p, q)-Edge-Labelling (2023)
Journal Article
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, https://doi.org/10.1007/s00453-023-01120-4

The L(p, q)-EDGE-LABELLING problem is the edge variant of the well-known L(p, q)-LABELLING problem. It is equivalent to the L(p, q)-LABELLING problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p, q)-Edge-Labelling.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2023)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Finding matching cuts in H-free graphs (2022)
Presentation / Conference Contribution
Lucke, F., Paulusma, D., & Ries, B. (2022). Finding matching cuts in H-free graphs. In S. W. Bae, & H. Park (Eds.), 33rd International Symposium on Algorithms and Computation (ISAAC 2022) (22:1-22:16). https://doi.org/10.4230/lipics.isaac.2022.22

The well-known NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed... Read More about Finding matching cuts in H-free graphs.

Few induced disjoint paths for H-free graphs (2022)
Presentation / Conference Contribution
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Few induced disjoint paths for H-free graphs. In I. Ljubić, F. Barahona, S. S. Dey, & A. Ridha Mahjoub (Eds.), Combinatorial Optimization 7th International Symposium, ISCO 2022 (89-101). https://doi.org/10.1007/978-3-031-18530-4_7

Paths P 1 , . . . , P k in a graph G = (V, E) are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs... Read More about Few induced disjoint paths for H-free graphs.

Few induced disjoint paths for H-free graphs (2022)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024

Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices contains k mutu... Read More about Few induced disjoint paths for H-free graphs.

Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs (2022)
Journal Article
Paesani, G., Paulusma, D., & Rzążwski, P. (2022). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs. SIAM Journal on Discrete Mathematics, 36(4), 2453-2472. https://doi.org/10.1137/22m1468864

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 for every s \geq 1, both problems are pol... Read More about Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs.

Classifying Subset Feedback Vertex Set for H-free graphs (2022)
Presentation / Conference Contribution
Paesani, G., Paulusma, D., & Rzążewski, P. (2022). Classifying Subset Feedback Vertex Set for H-free graphs. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022 (412-424). https://doi.org/10.1007/978-3-031-15914-5_30

In the FEEDBACK VERTEX SET problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The SUBSET FEEDBACK VERTEX SET problem requires S to intersect only those cycles that include a vertex of some specified set T. We also... Read More about Classifying Subset Feedback Vertex Set for H-free graphs.

An algorithmic framework for locally constrained homomorphisms (2022)
Presentation / Conference Contribution
Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2022). An algorithmic framework for locally constrained homomorphisms. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022 (114-128). https://doi.org/10.1007/978-3-031-15914-5_9

A homomorphism ϕ from a guest graph G to a host graph H is locally bijective, injective or surjective if for every u∈V(G), the restriction of ϕ to the neighbourhood of u is bijective, injective or surjective, respectively. The corresponding decision... Read More about An algorithmic framework for locally constrained homomorphisms.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2022)
Presentation / Conference Contribution
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers (398-411). https://doi.org/10.1007/978-3-031-15914-5_29

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

On the complexity of matching cut for graphs of bounded radius and H-free graphs (2022)
Journal Article
Lucke, F., Paulusma, D., & Ries, B. (2022). On the complexity of matching cut for graphs of bounded radius and H-free graphs. Theoretical Computer Science, 936, 33-42. https://doi.org/10.1016/j.tcs.2022.09.014

For a connected graph G = (V , E), a matching M ⊆ E is a matching cut of G if G − M is disconnected. It is known that for an integer d, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most d if d... Read More about On the complexity of matching cut for graphs of bounded radius and H-free graphs.

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter (2022)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034

For a fixed integer, the k-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 ind... Read More about Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter.

Partitioning H-free graphs of bounded diameter (2022)
Journal Article
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science, 930, 37-52. https://doi.org/10.1016/j.tcs.2022.07.009

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ide... Read More about Partitioning H-free graphs of bounded diameter.

Acyclic, Star, and Injective Colouring: Bounding the diameter (2022)
Journal Article
Brause, C., Golovach, P., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2022). Acyclic, Star, and Injective Colouring: Bounding the diameter. Electronic Journal of Combinatorics, 29(2), https://doi.org/10.37236/10738

We examine the effect of bounding the diameter for a number of natural and well-studied variants of the COLOURING problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices... Read More about Acyclic, Star, and Injective Colouring: Bounding the diameter.

Computing Balanced Solutions for Large International Kidney Exchange Schemes (2022)
Presentation / Conference Contribution
Benedek, M., Biró, P., Kern, W., & Paulusma, D. (2022). Computing Balanced Solutions for Large International Kidney Exchange Schemes. In AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (82-90)

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient–donor pools. We consider a recently introduced credit system. In each round, countr... Read More about Computing Balanced Solutions for Large International Kidney Exchange Schemes.

Computing weighted subset odd cycle transversals in H-free graphs (2022)
Journal Article
Brettell, N., Johnson, M., & Paulusma, D. (2022). Computing weighted subset odd cycle transversals in H-free graphs. Journal of Computer and System Sciences, 128, 71-85. https://doi.org/10.1016/j.jcss.2022.03.002

For the Odd Cycle Transversal problem, the task is to find a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal problem requires S to intersect only those odd cycles that include a vertex of... Read More about Computing weighted subset odd cycle transversals in H-free graphs.

QCSP on reflexive tournaments (2022)
Journal Article
Larose, B., Martin, B., Markovic, P., Paulusma, D., Smith, S., & Zivny, S. (2022). QCSP on reflexive tournaments. ACM Transactions on Computational Logic, 23(3), 1-22. https://doi.org/10.1145/3508069

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components H1,…,Hn so that ther... Read More about QCSP on reflexive tournaments.

Colouring graphs of bounded diameter in the absence of small cycles (2022)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring graphs of bounded diameter in the absence of small cycles. Discrete Applied Mathematics, 314, 150-161. https://doi.org/10.1016/j.dam.2022.02.026

For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two adjacent vertices u and v. The k-Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is H-f... Read More about Colouring graphs of bounded diameter in the absence of small cycles.

The Complexity of L(p,q)-Edge-Labelling (2022)
Presentation / Conference Contribution
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022). The Complexity of L(p,q)-Edge-Labelling. In P. Mutzel, M. . S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings (175-186). https://doi.org/10.1007/978-3-030-96731-4_15

The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p,q)-Edge-Labelling.

Computing subset transversals in H-free graphs (2021)
Journal Article
Brettell, N., Johnson, M., Paesani, G., & Paulusma, D. (2022). Computing subset transversals in H-free graphs. Theoretical Computer Science, 902, 76-92. https://doi.org/10.1016/j.tcs.2021.12.010

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.

Tree pivot-minors and linear rank-width (2021)
Journal Article
Dabrowski, K., Dross, F., Jeong, J., Kante, M., Kwon, O., Oum, S., & Paulusma, D. (2021). Tree pivot-minors and linear rank-width. SIAM Journal on Discrete Mathematics, 35(4), 2922-2945. https://doi.org/10.1137/21m1402339

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree T, the class of graphs that do not contain T as a minor has bounded path-width. For... Read More about Tree pivot-minors and linear rank-width.

Partitioning H-free graphs of bounded diameter (2021)
Presentation / Conference Contribution
Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021). Partitioning H-free graphs of bounded diameter. In H. Ahn, & K. Sadakane (Eds.), . https://doi.org/10.4230/lipics.isaac.2021.21

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ide... Read More about Partitioning H-free graphs of bounded diameter.

Induced disjoint paths in AT-free graphs (2021)
Journal Article
Golovach, P., Paulusma, D., & van Leeuwen, E. (2022). Induced disjoint paths in AT-free graphs. Journal of Computer and System Sciences, 124, 170-191. https://doi.org/10.1016/j.jcss.2021.10.003

Paths P1, . . . , Pk in a graph G = (V, E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph G with k... Read More about Induced disjoint paths in AT-free graphs.

Disjoint paths and connected subgraphs for H-free graphs (2021)
Journal Article
Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Disjoint paths and connected subgraphs for H-free graphs. Theoretical Computer Science, 898, 59-68. https://doi.org/10.1016/j.tcs.2021.10.019

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct vertex pairs. We determine, with an exception of two cases, the complexity of the Dis... Read More about Disjoint paths and connected subgraphs for H-free graphs.

Hard problems that quickly become very easy (2021)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Hard problems that quickly become very easy. Information Processing Letters, 174, https://doi.org/10.1016/j.ipl.2021.106213

A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable for every hereditary graph class that is not equal to the class of all g... Read More about Hard problems that quickly become very easy.

Acyclic, star and injective colouring: bounding the diameter (2021)
Presentation / Conference Contribution
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, star and injective colouring: bounding the diameter. In Ł. Kowalik, M. Pilipczuk, & P. Rzążewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers (336-348). https://doi.org/10.1007/978-3-030-86838-3_26

We examine the effect of bounding the diameter for wellstudied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively.... Read More about Acyclic, star and injective colouring: bounding the diameter.

QCSP on reflexive tournaments (2021)
Presentation / Conference Contribution
Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021). QCSP on reflexive tournaments. In P. Mutzel, R. Pagh, & G. Herman (Eds.), . https://doi.org/10.4230/lipics.esa.2021.58

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H1, . . . , Hn so th... Read More about QCSP on reflexive tournaments.

Bounding the mim-width of hereditary graph classes (2021)
Journal Article
Brettell, N., Horsfield, J., Munaro, A., Paesani, G., & Paulusma, D. (2022). Bounding the mim-width of hereditary graph classes. Journal of Graph Theory, 99(1), 117-151. https://doi.org/10.1002/jgt.22730

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.

Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs (2021)
Presentation / Conference Contribution
Paesani, G., Paulusma, D., & Rzążewski, P. (2021). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs. In F. Bonchi, & S. J. Puglisi (Eds.), . https://doi.org/10.4230/lipics.mfcs.2021.82

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 solvabl... Read More about Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs.

Computing weighted subset transversals in H-free graphs (2021)
Presentation / Conference Contribution
Brettell, N., Johnson, M., & Paulusma, D. (2021). Computing weighted subset transversals in H-free graphs. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (229-242). https://doi.org/10.1007/978-3-030-83508-8_17

For the Odd Cycle Transversal problem, the task is to nd a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal requires S to intersect only those odd cycles that include a vertex of a disting... Read More about Computing weighted subset transversals in H-free graphs.

Solving problems on generalized convex graphs via mim-width (2021)
Presentation / Conference Contribution
Bonomo-Braberman, F., Brettell, N., Munaro, A., & Paulusma, D. (2021). Solving problems on generalized convex graphs via mim-width. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures: 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (200-214). https://doi.org/10.1007/978-3-030-83508-8_15

A bipartite graph G = (A, B, E) is H-convex, for some family of graphs H, if there exists a graph H ∈ H with V (H) = A such that the set of neighbours in A of each b ∈ B induces a connected subgraph of H. Many NP-complete problems become polynomial-t... Read More about Solving problems on generalized convex graphs via mim-width.

List k-colouring P-free graphs: a mim-width perspective (2021)
Journal Article
Brettell, N., Horsfield, J., Munaro, A., & Paulusma, D. (2022). List k-colouring P-free graphs: a mim-width perspective. Information Processing Letters, 173, Article 106168. https://doi.org/10.1016/j.ipl.2021.106168

A colouring of a graph G = (V, E) is a mapping c : V → {1, 2, . . .} such that c(u) 6= c(v) for every two adjacent vertices u and v of G. The List k-Colouring problem is to decide whether a graph G = (V, E) with a list L(u) ⊆ {1, . . . , k} for each... Read More about List k-colouring P-free graphs: a mim-width perspective.

Disjoint paths and connected subgraphs for H-free graphs (2021)
Presentation / Conference Contribution
Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2021). Disjoint paths and connected subgraphs for H-free graphs. In P. Flocchini, & L. Moura (Eds.), Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings (414-427). https://doi.org/10.1007/978-3-030-79987-8_29

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint P... Read More about Disjoint paths and connected subgraphs for H-free graphs.

Injective colouring for H-free graphs (2021)
Presentation / Conference Contribution
Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective colouring for H-free graphs.

A function c : V (G) → {1, 2, . . . , k} is a k-colouring of a graph G if c(u) 6= c(v) whenever u and v are adjacent. If any two colour classes induce the disjoint union of vertices and edges, then c is called injective. Injective colourings are also... Read More about Injective colouring for H-free graphs.

Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration (2021)
Journal Article
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2021). Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration. Journal of Graph Theory, 98(1), 81-109. https://doi.org/10.1002/jgt.22683

We continue research into a well-studied family of problems that ask whether the vertices of a given 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 consider the ca... Read More about Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration.

Colouring graphs of bounded diameter in the absence of small cycles (2021)
Presentation / Conference Contribution
Martin, B., Paulusma, D., & Smith, S. (2021). Colouring graphs of bounded diameter in the absence of small cycles. In T. Calamoneri, & F. Corò (Eds.), . https://doi.org/10.1007/978-3-030-75242-2_26

For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two non-adjacent vertices u and v. The k-Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is... Read More about Colouring graphs of bounded diameter in the absence of small cycles.

What graphs are 2-dot product graphs? (2021)
Journal Article
Johnson, M., Paulusma, D., & van Leeuwen, E. (2021). What graphs are 2-dot product graphs?. International Journal of Computational Geometry and Applications, 31(01), 1-16. https://doi.org/10.1142/s0218195921500011

Let d ≥ 1 be an integer. From a set of d-dimensional vectors, we obtain a d-dot product graph by letting each vector a u correspond to a vertex u and by adding an edge between two vertices u and v if and only if their dot product a u · a v ≥ t, for s... Read More about What graphs are 2-dot product graphs?.

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective (2021)
Journal Article
Bodlaender, H., Brettell, N., Johnson, M., Paesani, G., Paulusma, D., & van Leeuwen, E. (2021). Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective. Theoretical Computer Science, 867, 30-39. https://doi.org/10.1016/j.tcs.2021.03.012

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: a Treewidth Perspective.

Bounding the mim-width of hereditary graph classes (2020)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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)
Presentation / Conference Contribution
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.

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). Colouring H-free graphs of bounded diameter. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) (14:1-14:14). https://doi.org/10.4230/lipics.mfcs.2019.14

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.

Independent transversals versus transversals (2019)
Presentation / Conference Contribution
Dabrowski, K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2019). Independent transversals versus transversals.

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.

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). Tree pivot-minors and linear rank-width.

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.

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). On cycle transversals and their connected variants in the absence of a small linear forest. In L. A. Gąsieniec, J. Jansson, & C. Levcopoulos (Eds.), Fundamentals of computation theory ; 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14 2019 ; proceedings (258-273). https://doi.org/10.1007/978-3-030-25027-0_18

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.

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.

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.

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.

Generalized matching games for international kidney exchange (2019)
Presentation / Conference Contribution
Biro, P., Kern, W., Palvolgyi, D., & Paulusma, D. (2019). Generalized matching games for international kidney exchange. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (413-421)

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). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. In Z. Friggstad, J. Sack, & M. R. Salavatipour (Eds.), Algorithms and data structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5–7, 2019, proceedings (181-195). https://doi.org/10.1007/978-3-030-24766-9_14

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). Finding a small number of colourful components. In 30th Annual Symposium on Combinatorial Pattern Matching

Clique-width for hereditary graph classes (2019)
Journal Article
Dabrowski, K., Johnson, M., & Paulusma, D. (2019). 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.

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). Colouring (Pr+Ps)-free graphs. In W. Hsu, D. Lee, & C. Liao (Eds.), 29th International Symposium on Algorithms and Computation (ISAAC 2018) (5:1-5:13). https://doi.org/10.4230/lipics.isaac.2018.5

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). Connected Vertex Cover for (sP1+P5)-free graphs. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings (279-291). https://doi.org/10.1007/978-3-030-00256-5_23

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). Computing small pivot-minors. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018 ; proceedings (125-138). https://doi.org/10.1007/978-3-030-00256-5_11

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). Simple games versus weighted voting games. In X. Deng (Ed.), Algorithmic game theory : 11th International Symposium, SAGT 2018, Beijing, China, September 11-14, 2018, Proceedings (69-81). https://doi.org/10.1007/978-3-319-99660-8_7

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. (2018). Surjective H-Colouring over Reflexive Digraphs. In R. Niedermeier, & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France (49:1-49:14). https://doi.org/10.4230/lipics.stacs.2018.49

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. (2018). Colouring Square-Free Graphs without Long Induced Paths. In R. Niedermeier, & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France (35:1-35:15). https://doi.org/10.4230/lipics.stacs.2018.35

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). Disconnected Cuts in Claw-free Graphs. In Y. Azar, H. Bast, & G. Herman (Eds.), 26th Annual European Symposium on Algorithms (ESA 2018) (61:1-61:14). https://doi.org/10.4230/lipics.esa.2018.61

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). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. In I. Potapov, P. Spirakis, & J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) (63:1-63:15). https://doi.org/10.4230/lipics.mfcs.2018.63

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.

Clique-Width for Graph Classes Closed under Complementation (2017)
Presentation / Conference Contribution
Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017). Clique-Width for Graph Classes Closed under Complementation. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.73

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 initiate a systematic study i... Read More about Clique-Width for Graph Classes Closed under Complementation.

Finding cactus roots in polynomial time (2017)
Journal Article
Golovach, P., Kratsch, D., Stewart, A., & Paulusma, D. (2018). Finding cactus roots in polynomial time. Theory of Computing Systems, 62(6), 1409-1426. https://doi.org/10.1007/s00224-017-9825-2

A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The SQUARE ROOT problem is that of deciding whether a given graph admi... Read More about Finding cactus roots in polynomial time.

Independent feedback vertex sets for graphs of bounded diameter (2017)
Journal Article
Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131, 26-32. https://doi.org/10.1016/j.ipl.2017.11.004

The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a forest. The set A in such a partition is said to be an independent feedback... Read More about Independent feedback vertex sets for graphs of bounded diameter.

Clique-width and well-quasi ordering of triangle-free graph classes (2017)
Presentation / Conference Contribution
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2017). Clique-width and well-quasi ordering of triangle-free graph classes. In H. L. Bodlaender, & G. J. Woeginger (Eds.), Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers (220-233). https://doi.org/10.1007/978-3-319-68705-6_17

Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev (WG 2015) gave a negative answer to this question, but their count... Read More about Clique-width and well-quasi ordering of triangle-free graph classes.

Reducing the chromatic number by vertex or edge deletions (2017)
Presentation / Conference Contribution
Picouleau, C., Paulusma, D., & Ries, B. (2017). Reducing the chromatic number by vertex or edge deletions. Electronic Notes in Discrete Mathematics, 62, 243-248. https://doi.org/10.1016/j.endm.2017.10.042

A vertex or an edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of testing whether a graph has a critical vertex or a critical edge, respectively. We give a complete classification... Read More about Reducing the chromatic number by vertex or edge deletions.

Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity (2017)
Journal Article
Chiarelli, N., Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2018). Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity. Theoretical Computer Science, 705, 75-83. https://doi.org/10.1016/j.tcs.2017.09.033

We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. Just like their original counterparts, these variants are NP-c... Read More about Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity.

Contracting bipartite graphs to paths and cycles (2017)
Presentation / Conference Contribution
Dabrowski, K., & Paulusma, D. (2017). Contracting bipartite graphs to paths and cycles. Electronic Notes in Discrete Mathematics, 61, 309-315. https://doi.org/10.1016/j.endm.2017.06.053

Testing if a given graph G contains the k-vertex path Pk as a minor or as an induced minor is trivial for every fixed integer k≥1. The situation changes for the problem of checking if a graph can be modified into Pk by using only edge contractions. I... Read More about Contracting bipartite graphs to paths and cycles.

Contracting Bipartite Graphs to Paths and Cycles (2017)
Journal Article
Dabrowski, K., & Paulusma, D. (2017). Contracting Bipartite Graphs to Paths and Cycles. Information Processing Letters, 127, 37-42. https://doi.org/10.1016/j.ipl.2017.06.013

Testing if a given graph G contains the k -vertex path Pk as a minor or as an induced minor is trivial for every fixed integer k≥1. However, the situation changes for the problem of checking if a graph can be modified into Pk by using only edge contr... Read More about Contracting Bipartite Graphs to Paths and Cycles.

Well-quasi-ordering versus clique-width: new results on bigenic classes (2017)
Journal Article
Dabrowski, K., Lozin, V., & Paulusma, D. (2018). Well-quasi-ordering versus clique-width: new results on bigenic classes. Order, 35(2), 253-274. https://doi.org/10.1007/s11083-017-9430-7

Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this is not true for classes defined by infinitely ma... Read More about Well-quasi-ordering versus clique-width: new results on bigenic classes.

Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 (2017)
Presentation / Conference Contribution
Golovach, P., Heggernes, P., Kratsch, D., Lima, P., & Paulusma, D. (2017). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. In H. L. Bodlaender, & G. J. Woeginger (Eds.), Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers (275-288). https://doi.org/10.1007/978-3-319-68705-6_21

Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem is NP-complete in general, and consequently substantial effort has been... Read More about Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2.

Recognizing Graphs Close to Bipartite Graphs (2017)
Presentation / Conference Contribution
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Recognizing Graphs Close to Bipartite Graphs. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.70

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-de... Read More about Recognizing Graphs Close to Bipartite Graphs.

Colouring Diamond-free Graphs (2017)
Journal Article
Dabrowski, K., Dross, F., & Paulusma, D. (2017). Colouring Diamond-free Graphs. Journal of Computer and System Sciences, 89, 410-431. https://doi.org/10.1016/j.jcss.2017.06.005

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof i... Read More about Colouring Diamond-free Graphs.

A linear kernel for finding square roots of almost planar graphs (2017)
Journal Article
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2017). A linear kernel for finding square roots of almost planar graphs. Theoretical Computer Science, 689, 36-47. https://doi.org/10.1016/j.tcs.2017.05.008

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are at distance 2 from each other. The Square Root problem is that of deciding whether a given graph admits a square root.... Read More about A linear kernel for finding square roots of almost planar graphs.

Computing square roots of graphs with low maximum degree (2017)
Journal Article
Cochefert, M., Couturier, J., Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2018). Computing square roots of graphs with low maximum degree. Discrete Applied Mathematics, 248, 93-101. https://doi.org/10.1016/j.dam.2017.04.041

A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is known... Read More about Computing square roots of graphs with low maximum degree.

Surjective H-Colouring: new hardness results (2017)
Presentation / Conference Contribution
Golovach, P. A., Johnson, M., Martin, M., Paulusma, D., & Stewart, A. (2017). Surjective H-Colouring: new hardness results. In J. Kari, F. Manea, & I. Petre (Eds.), Unveiling dynamics an complexity (270-281). https://doi.org/10.1007/978-3-319-58741-7_26

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.

Blocking independent sets for H-free graphs via edge contractions and vertex deletions (2017)
Presentation / Conference Contribution
Paulusma, D., Picouleau, C., & Ries, B. (2017). Blocking independent sets for H-free graphs via edge contractions and vertex deletions. In T. Gopal, G. Jäger, & S. Steila (Eds.), Theory and Applications of Models of Computation, 14th Annual Conference (TAMC 2017) : Bern, Switzerland, April 20-22, 2017 ; proceedings (470-483). https://doi.org/10.1007/978-3-319-55911-7_34

Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be c... Read More about Blocking independent sets for H-free graphs via edge contractions and vertex deletions.

Bounding the Clique-Width of H-free Chordal Graphs (2017)
Journal Article
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2017). Bounding the Clique-Width of H-free Chordal Graphs. Journal of Graph Theory, 86(1), 42-77. https://doi.org/10.1002/jgt.22111

A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le, and Mosca erroneously claime... Read More about Bounding the Clique-Width of H-free Chordal Graphs.

The Stable Fixtures Problem with Payments (2017)
Journal Article
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2018). The Stable Fixtures Problem with Payments. Games and Economic Behavior, 108, 245-268. https://doi.org/10.1016/j.geb.2017.02.002

We consider multiple partners matching games (G,b,w), where G is a graph with an integer vertex capacity function b and an edge weighting w. If G is bipartite, these games are called multiple partners assignment games. We give a polynomial-time algor... Read More about The Stable Fixtures Problem with Payments.

Independent Feedback Vertex Set for P5-free Graphs (2017)
Presentation / Conference Contribution
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Independent Feedback Vertex Set for P5-free Graphs. In Y. Okamoto, & T. Tokuyama (Eds.), 28th International Symposium on Algorithms and Computation (ISAAC 2017) ; proceedings (16:1-16:12). https://doi.org/10.4230/lipics.isaac.2017.16

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 independen... Read More about Independent Feedback Vertex Set for P5-free Graphs.

Editing to a Planar Graph of Given Degrees (2016)
Journal Article
Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2016). Editing to a Planar Graph of Given Degrees. Journal of Computer and System Sciences, 85, 168-182. https://doi.org/10.1016/j.jcss.2016.11.009

We consider the following graph modification problem. Let the input consist of a graph G=(V,E), a weight function w:V∪E→N, a cost function c:V∪E→N0 and a degree function δ:V→N0, together with three integers kv,ke and C . The question is whether we ca... Read More about Editing to a Planar Graph of Given Degrees.

Squares of low clique number (2016)
Presentation / Conference Contribution
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2016). Squares of low clique number. Electronic Notes in Discrete Mathematics, 55, 195-198. https://doi.org/10.1016/j.endm.2016.10.048

The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number... Read More about Squares of low clique number.

The price of connectivity for feedback vertex set (2016)
Journal Article
Belmonte, R., van ’t Hof, P., Kamiński, M., & Paulusma, D. (2017). The price of connectivity for feedback vertex set. Discrete Applied Mathematics, 217(Part B), 132-143. https://doi.org/10.1016/j.dam.2016.08.011

Let View the MathML source and View the MathML source denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. The price of connectivity for feedback vertex set (poc-fvs) for a... Read More about The price of connectivity for feedback vertex set.

Reducing the clique and chromatic number via edge contractions and vertex deletions (2016)
Presentation / Conference Contribution
Paulusma, D., Picouleau, C., & Ries, B. (2016). Reducing the clique and chromatic number via edge contractions and vertex deletions. In R. Cerulli, S. Fujishige, & A. R. Mahjoub (Eds.), Combinatorial optimization : 4th International Symposium, ISCO 2016, Vietri sul Mare, Italy, May 16-18, 2016. Revised selected papers (38-49). https://doi.org/10.1007/978-3-319-45587-7_4

We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the c... Read More about Reducing the clique and chromatic number via edge contractions and vertex deletions.

Finding cactus roots in polynomial time (2016)
Presentation / Conference Contribution
Golovach, P. A., Kratsch, D., Paulusma, D., & Stewart, A. (2016). Finding cactus roots in polynomial time. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings (361-372). https://doi.org/10.1007/978-3-319-44543-4_28

A cactus is a connected graph in which each edge belongs to at most one cycle. A graph H is a cactus root of a graph G if H is a cactus and G can be obtained from H by adding an edge between any two vertices in H that are of distance 2 in H. We show... Read More about Finding cactus roots in polynomial time.

Well-quasi-ordering versus clique-width: new results on bigenic classes (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016). Well-quasi-ordering versus clique-width: new results on bigenic classes. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings (253-265). https://doi.org/10.1007/978-3-319-44543-4_20

Daligault, Rao and Thomassé conjectured that if a hereditary class of graphs is well-quasi-ordered by the induced subgraph relation then it has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this conjecture is not true for infi... Read More about Well-quasi-ordering versus clique-width: new results on bigenic classes.

Minimal Disconnected Cuts in Planar Graphs (2016)
Journal Article
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. (2016). Minimal Disconnected Cuts in Planar Graphs. Networks, 68(4), 250-259. https://doi.org/10.1002/net.21696

The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity was not known for planar grap... Read More about Minimal Disconnected Cuts in Planar Graphs.

Open problems on graph coloring for special graph classes (2016)
Presentation / Conference Contribution
Paulusma, D. (2016). Open problems on graph coloring for special graph classes. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (16-30). https://doi.org/10.1007/978-3-662-53174-7_2

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c:V→{1,2,…}c:V→{1,2,…} such that c(u)≠c(v)c(u)≠c(v) for every edge uv∈Euv∈E. We survey known results... Read More about Open problems on graph coloring for special graph classes.

The stable fixtures problem with payments (2016)
Presentation / Conference Contribution
Biró, P., Kern, W., Paulusma, D., & Wojuteczky, P. (2016). The stable fixtures problem with payments. In E. W. Mayr (Ed.), Graph-theoretic concepts in computer science : 41st international workshop, WG 2015, Garching, Germany, June 17-19, 2015 ; revised papers (49-63). https://doi.org/10.1007/978-3-662-53174-7_4

We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph G=(N,E)G=(N,E), with an integer vertex capacity function b and an edge weighting w. The set N consists of a number of players that... Read More about The stable fixtures problem with payments.

Using contracted solution graphs for solving reconfiguration problems (2016)
Presentation / Conference Contribution
Bonsma, P., & Paulusma, D. (2016). Using contracted solution graphs for solving reconfiguration problems. In P. Faliszewski, A. Muscholl, & R. Niedermeier (Eds.), 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22–26, 2016, Kraków, Poland. https://doi.org/10.4230/lipics.mfcs.2016.20

We introduce a dynamic programming method for solving reconfiguration problems, based on contracted solution graphs, which are obtained from solution graphs by performing an appropriate series of edge contractions that decrease the graph size without... Read More about Using contracted solution graphs for solving reconfiguration problems.

Kempe equivalence of colourings of cubic graphs (2016)
Journal Article
Feghali, C., Johnson, M., & Paulusma, D. (2017). Kempe equivalence of colourings of cubic graphs. European Journal of Combinatorics, 59, 1-10. https://doi.org/10.1016/j.ejc.2016.06.008

Given a graph G=(V,E) and a proper vertex colouring of G, a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by ex... Read More about Kempe equivalence of colourings of cubic graphs.

Bounding clique-width via perfect graphs (2016)
Journal Article
Dabrowski, K., Huang, S., & Paulusma, D. (2019). Bounding clique-width via perfect graphs. Journal of Computer and System Sciences, 104, 202-215. https://doi.org/10.1016/j.jcss.2016.06.007

We continue the study into the clique-width of graph classes defined by two forbidden induced graphs. We present three new classes of bounded clique-width and one of unbounded clique-width. The four new graph classes have in common that one of their... Read More about Bounding clique-width via perfect graphs.

The price of connectivity for cycle transversals (2016)
Journal Article
Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2016). The price of connectivity for cycle transversals. European Journal of Combinatorics, 58, 203-224. https://doi.org/10.1016/j.ejc.2016.06.003

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and View the MathML source be... Read More about The price of connectivity for cycle transversals.

A linear kernel for finding square roots of almost planar graphs (2016)
Presentation / Conference Contribution
Golovach, P., Kratsch, D., Paulusma, D., & Stewart, A. (2016). A linear kernel for finding square roots of almost planar graphs. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). https://doi.org/10.4230/lipics.swat.2016.4

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 of each other. The Square Root problem is that of deciding whether a given graph admits a square root. W... Read More about A linear kernel for finding square roots of almost planar graphs.

Colouring diamond-free graphs (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Dross, F., & Paulusma, D. (2016). Colouring diamond-free graphs. In R. Pagh (Ed.), 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). https://doi.org/10.4230/lipics.swat.2016.16

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof i... Read More about Colouring diamond-free graphs.

Induced disjoint paths in circular-arc graphs in linear time (2016)
Journal Article
Golovach, P., Paulusma, D., & van Leeuwen, E. (2016). Induced disjoint paths in circular-arc graphs in linear time. Theoretical Computer Science, 640, 70-83. https://doi.org/10.1016/j.tcs.2016.06.003

The Induced Disjoint Paths problem is to test whether an graph G on n vertices with k distinct pairs of vertices (si,ti) contains paths P1,…,Pk such that Pi connects si and ti for i=1,…,k, and Pi and Pj have neither common vertices nor adjacent verti... Read More about Induced disjoint paths in circular-arc graphs in linear time.

Bounding the clique-width of H-free split graphs (2016)
Journal Article
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2016). Bounding the clique-width of H-free split graphs. Discrete Applied Mathematics, 211, 30-39. https://doi.org/10.1016/j.dam.2016.04.003

A graph is H-free if it has no induced subgraph isomorphic to H. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of H-free split graphs whose clique-width is bounded. Our main res... Read More about Bounding the clique-width of H-free split graphs.

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs (2016)
Journal Article
Golovach, P., Johnson, M., Paulusma, D., & Song., J. (2017). A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs. Journal of Graph Theory, 84(4), 331-363. https://doi.org/10.1002/jgt.22028

For a positive integer k, a k-coloring of a graph inline image is a mapping inline image such that inline image whenever inline image. The COLORING problem is to decide, for a given G and k, whether a k-coloring of G exists. If k is fixed (i.e., it i... Read More about A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs.

Filling the complexity gaps for colouring planar and bounded degree graphs (2016)
Presentation / Conference Contribution
Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2016). Filling the complexity gaps for colouring planar and bounded degree graphs. In Z. Lipták, & W. F. Smyth (Eds.), Combinatorial Algorithms : 26th International Workshop, Iwoca 2015, Verona, Italy, October 5-7, 2015, Revised selected papers (100-111). https://doi.org/10.1007/978-3-319-29516-9_9

We consider a natural restriction of the List Colouring problem, k-Regular List Colouring, which corresponds to the List Colouring problem where every list has size exactly k. We give a complete classification of the complexity of k-Regular List Colo... Read More about Filling the complexity gaps for colouring planar and bounded degree graphs.

Bounding the clique-width of H-free split graphs (2015)
Presentation / Conference Contribution
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015). Bounding the clique-width of H-free split graphs. . https://doi.org/10.1016/j.endm.2015.06.069

A graph is H-free if it has no induced subgraph isomorphic to H. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of H-free split graphs whose clique-width is bounded. Our main res... Read More about Bounding the clique-width of H-free split graphs.

Kempe equivalence of colourings of cubic graphs (2015)
Presentation / Conference Contribution
Feghali, C., Johnson, M., & Paulusma, D. (2015). Kempe equivalence of colourings of cubic graphs. . https://doi.org/10.1016/j.endm.2015.06.034

Given a graph G = (V,E) and a proper vertex colouring of G, a Kempe chain is a subset of V that induces a maximal connected subgraph of G in which every vertex has one of two colours. To make a Kempe change is to obtain one colouring from another by... Read More about Kempe equivalence of colourings of cubic graphs.

What graphs are 2-dot product graphs? (2015)
Presentation / Conference Contribution
Johnson, M., van Leeuwen, E., & Paulusma, D. (2015). What graphs are 2-dot product graphs?. . https://doi.org/10.1016/j.endm.2015.06.095

From a set of d-dimensional vectors for some integer d ≥ 1, we obtain a d-dot product graph by letting each vector au correspond to a vertex u and by adding an edge between two vertices u and v if and only if their dot product au · av ≥ t, for some f... Read More about What graphs are 2-dot product graphs?.

Editing to Eulerian graphs (2015)
Journal Article
Dabrowski, K., Golovach, P., van 't Hof, P., & Paulusma, D. (2016). Editing to Eulerian graphs. Journal of Computer and System Sciences, 82(2), 213-228. https://doi.org/10.1016/j.jcss.2015.10.003

The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and dir... Read More about Editing to Eulerian graphs.

Clique-width of graph classes defined by two forbidden induced subgraphs (2015)
Journal Article
Dabrowski, K., & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, https://doi.org/10.1093/comjnl/bxv096

The class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of the 4-vertex path P4. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs H1 and H2. Prior to our... Read More about Clique-width of graph classes defined by two forbidden induced subgraphs.

Narrowing the complexity gap for colouring (Cs, Pt)-free graphs (2015)
Journal Article
Huang, S., Johnson, M., & Paulusma, D. (2015). Narrowing the complexity gap for colouring (Cs, Pt)-free graphs. The Computer Journal, 58(11), 3074-3088. https://doi.org/10.1093/comjnl/bxv039

For a positive integer k and graph G=(V,E), a k-colouring of G is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv∈E. The k-Colouring problem is to decide, for a given G, whether a k-colouring of G exists. The k-Precolouring Extension problem... Read More about Narrowing the complexity gap for colouring (Cs, Pt)-free graphs.

A Reconfigurations Analogue of Brooks' Theorem and Its Consequences (2015)
Journal Article
Feghali, C., Johnson, M., & Paulusma, D. (2016). A Reconfigurations Analogue of Brooks' Theorem and Its Consequences. Journal of Graph Theory, 83(4), 340-358. https://doi.org/10.1002/jgt.22000

Let G be a simple undirected connected graph on n vertices with maximum degree Δ. Brooks' Theorem states that G has a proper Δ-coloring unless G is a complete graph, or a cycle with an odd number of vertices. To recolor G is to obtain a new proper co... Read More about A Reconfigurations Analogue of Brooks' Theorem and Its Consequences.

Knocking out P_k-free graphs (2015)
Journal Article
Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108. https://doi.org/10.1016/j.dam.2015.04.010

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Paralle... Read More about Knocking out P_k-free graphs.

Bounding the Clique-Width of H-free Chordal Graphs (2015)
Presentation / Conference Contribution
Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2015). Bounding the Clique-Width of H-free Chordal Graphs. In Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II (139-150). https://doi.org/10.1007/978-3-662-48054-0_12

A graph is H-free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le and Mosca erroneously claimed... Read More about Bounding the Clique-Width of H-free Chordal Graphs.

The price of connectivity for cycle transversals (2015)
Presentation / Conference Contribution
Hartinger, T., Johnson, M., Milanič, M., & Paulusma, D. (2015). The price of connectivity for cycle transversals. In Mathematical foundations of computer science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, proceedings, part II (395-406). https://doi.org/10.1007/978-3-662-48054-0_33

For a family of graphs F, an F-transversal of a graph G is a subset S⊆V(G) that intersects every subset of V(G) that induces a subgraph isomorphic to a graph in F. Let tF(G) be the minimum size of an F-transversal of G, and ctF(G) be the minimum size... Read More about The price of connectivity for cycle transversals.

Minimal disconnected cuts in planar graphs (2015)
Presentation / Conference Contribution
Kamiński, M., Paulusma, D., Stewart, A., & Thilikos, D. M. (2015). Minimal disconnected cuts in planar graphs. In A. Kosowski, & I. Walukiewicz (Eds.), Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, proceedings (243-254). https://doi.org/10.1007/978-3-319-22177-9_19

The problem of finding a disconnected cut in a graph is NP-hard in general but polynomial-time solvable on planar graphs. The problem of finding a minimal disconnected cut is also NP-hard but its computational complexity is not known for planar graph... Read More about Minimal disconnected cuts in planar graphs.

Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree (2015)
Journal Article
Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesař, M. (2015). Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical Computer Science, 590, 86-95. https://doi.org/10.1016/j.tcs.2015.01.028

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether... Read More about Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree.

Model counting for CNF formulas of bounded modular treewidth (2015)
Journal Article
Paulusma, D., Slivovsky, S., & Szeider, S. (2016). Model counting for CNF formulas of bounded modular treewidth. Algorithmica, 76(1), 168-194. https://doi.org/10.1007/s00453-015-0030-x

We define the modular treewidth of a graph as its treewidth after contraction of modules. This parameter properly generalizes treewidth and is itself properly generalized by clique-width. We show that the number of satisfying assignments can be compu... Read More about Model counting for CNF formulas of bounded modular treewidth.

Classifying the clique-width of H-free bipartite graphs (2015)
Journal Article
Dabrowski, K., & Paulusma, D. (2016). Classifying the clique-width of H-free bipartite graphs. Discrete Applied Mathematics, 200, 43-51. https://doi.org/10.1016/j.dam.2015.06.030

Let GG be a bipartite graph, and let HH be a bipartite graph with a fixed bipartition (BH,WH)(BH,WH). We consider three different, natural ways of forbidding HH as an induced subgraph in GG. First, GG is HH-free if it does not contain HH as an induce... Read More about Classifying the clique-width of H-free bipartite graphs.

Editing to a planar graph of given degrees (2015)
Presentation / Conference Contribution
Dabrowski, K., Golovach, P., van 't Hof, P., Paulusma, D., & Thilikos, D. (2015). Editing to a planar graph of given degrees. In Computer science - theory and applications : 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, proceedings (143-156). https://doi.org/10.1007/978-3-319-20297-6_10

We consider the following graph modification problem. Let the input consist of a graph G=(V,E), a weight function w:V∪E→N, a cost function c:V∪E→N and a degree function δ:V→N0, together with three integers kv, ke and C. The question is whether we can... Read More about Editing to a planar graph of given degrees.

Contraction blockers for graphs with forbidden induced paths (2015)
Presentation / Conference Contribution
Diner, Ö., Paulusma, D., Picouleau, C., & Ries, B. (2015). Contraction blockers for graphs with forbidden induced paths. In V. T. Paschos, & P. Widmayer (Eds.), Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings (194-207). https://doi.org/10.1007/978-3-319-18173-8_14

We consider the following problem: can a certain graph parameter of some given graph be reduced by at least d for some integer d via at most k edge contractions for some given integer k? We examine three graph parameters: the chromatic number, clique... Read More about Contraction blockers for graphs with forbidden induced paths.

Clique-width of graph classes defined by two forbidden induced subgraphs (2015)
Presentation / Conference Contribution
Dabrowski, K. K., & Paulusma, D. (2015). Clique-width of graph classes defined by two forbidden induced subgraphs. In V. T. Paschos, & P. Widmayer (Eds.), Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings (167-181). https://doi.org/10.1007/978-3-319-18173-8_12

If a graph has no induced subgraph isomorphic to any graph in a finite family {H1,…,Hp}, it is said to be (H1,…,Hp)-free. The class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of the 4-vertex path P4. We study th... Read More about Clique-width of graph classes defined by two forbidden induced subgraphs.

Finding Shortest Paths Between Graph Colourings (2015)
Journal Article
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica, 75(2), 295-321. https://doi.org/10.1007/s00453-015-0009-7

The k-colouring reconguration problem asks whether, for a given graph G, two proper k-colourings and of G, and a positive integer `, there exists a sequence of at most ` + 1 proper k-colourings of G which starts with and ends with and where successiv... Read More about Finding Shortest Paths Between Graph Colourings.

Algorithms for diversity and clustering in social networks through dot product graphs (2015)
Journal Article
Johnson, M., Paulusma, D., & van Leeuwen, E. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks, 41, 48-55. https://doi.org/10.1016/j.socnet.2015.01.001

In this paper, we investigate a graph-theoretical model of social networks. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d -dimensional vector View... Read More about Algorithms for diversity and clustering in social networks through dot product graphs.

Bounding clique-width via perfect graphs (2015)
Presentation / Conference Contribution
Dabrowski, K. K., Huang, S., & Paulusma, D. (2015). Bounding clique-width via perfect graphs. In A. Dediu, E. Formenti, C. Martín-Vide, & B. Truthe (Eds.), Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015 ; proceedings (676-688). https://doi.org/10.1007/978-3-319-15579-1_53

Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no subgraph isomorphic to H1 or H2. We continue a recent study into the clique-width of (H1,H2)-free graphs and present three new classes of (H1,H2)-free graphs that have bounded cl... Read More about Bounding clique-width via perfect graphs.

Coloring graphs characterized by a forbidden subgraph (2015)
Journal Article
Golovach, P., Paulusma, D., & Ries, B. (2015). Coloring graphs characterized by a forbidden subgraph. Discrete Applied Mathematics, 180, 101-110. https://doi.org/10.1016/j.dam.2014.08.008

The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an in... Read More about Coloring graphs characterized by a forbidden subgraph.

Induced disjoint paths in claw-free graphs (2015)
Journal Article
Golovach, P., Paulusma, D., & van Leeuwen, E. (2015). Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics, 29(1), 348-375. https://doi.org/10.1137/140963200

Paths P1; : : : ; Pk in a graph G = (V;E) are said to be mutually induced if for any 1 i < j k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a... Read More about Induced disjoint paths in claw-free graphs.

Parameterized algorithms for finding square roots (2014)
Journal Article
Cochefert, M., Couturier, J., Golovach, P., & Paulusma, D. (2014). Parameterized algorithms for finding square roots. Algorithmica, https://doi.org/10.1007/s00453-014-9967-4

We show that the following two problems are fixed-parameter tractable with parameter k: testing whether a connected n-vertex graph with m edges has a square root with at most n−1+k edges and testing whether such a graph has a square root with at leas... Read More about Parameterized algorithms for finding square roots.

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs (2014)
Journal Article
Broersma, H., Fiala, J., Golovach, P., Kaiser, T., Paulusma, D., & Proskurowski, A. (2015). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Journal of Graph Theory, 79(4), 282-299. https://doi.org/10.1002/jgt.21832

We prove that for all inline image an interval graph is inline image-Hamilton-connected if and only if its scattering number is at most k. This complements a previously known fact that an interval graph has a nonnegative scattering number if and only... Read More about Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.

Closing complexity gaps for coloring problems on H-free graphs (2014)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2014). Closing complexity gaps for coloring problems on H-free graphs. Information and Computation, 237, 204-214. https://doi.org/10.1016/j.ic.2014.02.004

If a graph G contains no subgraph isomorphic to some graph H , then G is called H -free. A coloring of a graph G=(V,E) is a mapping c:V→{1,2,…} such that no two adjacent vertices have the same color, i.e., c(u)≠c(v) if uv∈E; if |c(V)|⩽k then c is a k... Read More about Closing complexity gaps for coloring problems on H-free graphs.

The computational complexity of disconnected cut and 2K2-partition (2014)
Journal Article
Martin, B., & Paulusma, D. (2015). The computational complexity of disconnected cut and 2K2-partition. Journal of Combinatorial Theory, Series B, 111, 17-37. https://doi.org/10.1016/j.jctb.2014.09.002

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This pr... Read More about The computational complexity of disconnected cut and 2K2-partition.

Graph editing to a fixed target (2014)
Journal Article
Golovach, P., Paulusma, D., & Stewart, I. (2017). Graph editing to a fixed target. Discrete Applied Mathematics, 216(Part 1), 181-190. https://doi.org/10.1016/j.dam.2014.07.008

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex di... Read More about Graph editing to a fixed target.

Detecting fixed patterns in chordal graphs in polynomial time (2014)
Journal Article
Belmonte, R., Golovach, P., Heggernes, P., van 't Hof, P., Kaminski, M., & Paulusma, D. (2014). Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica, 69(3), 501-521. https://doi.org/10.1007/s00453-013-9748-5

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows b... Read More about Detecting fixed patterns in chordal graphs in polynomial time.

Solutions for the stable roommates problem with payments (2014)
Journal Article
Biró, P., Bomhoff, M., Golovach, P., Kern, W., & Paulusma, D. (2014). Solutions for the stable roommates problem with payments. Theoretical Computer Science, 540-541, 53-61. https://doi.org/10.1016/j.tcs.2013.03.027

The stable roommates problem with payments has as input a graph G=(V,E)G=(V,E) with an edge weighting w:E→R≥0w:E→R≥0 and the problem is to find a stable solution. A solution is a matching MM with a vector p∈R≥0V that satisfies pu+pv=w(uv)pu+pv=w(uv)... Read More about Solutions for the stable roommates problem with payments.

Packing bipartite graphs with covers of complete bipartite graphs (2014)
Journal Article
Chalopin, J., & Paulusma, D. (2014). Packing bipartite graphs with covers of complete bipartite graphs. Discrete Applied Mathematics, 168, 40-50. https://doi.org/10.1016/j.dam.2012.08.026

For a set SS of graphs, a perfect SS-packing (SS-factor) of a graph GG is a set of mutually vertex-disjoint subgraphs of GG that each are isomorphic to a member of SS and that together contain all vertices of GG. If GG allows a covering (locally bije... Read More about Packing bipartite graphs with covers of complete bipartite graphs.

Coloring graphs without short cycles and long induced paths (2014)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2014). Coloring graphs without short cycles and long induced paths. Discrete Applied Mathematics, 167, 107-120. https://doi.org/10.1016/j.dam.2013.12.008

For an integer k≥1, a graph G is k-colorable if there exists a mapping c:VG→{1,…,k} such that c(u)≠c(v) whenever u and v are two adjacent vertices. For a fixed integer k≥1, the k-Coloring problem is that of testing whether a given graph is k-colorabl... Read More about Coloring graphs without short cycles and long induced paths.

List coloring in the absence of two subgraphs (2014)
Journal Article
Golovach, P., & Paulusma, D. (2014). List coloring in the absence of two subgraphs. Discrete Applied Mathematics, 166, 123-130. https://doi.org/10.1016/j.dam.2013.10.010

A list assignment of a graph G=(V,E) is a function L that assigns a list L(u) of so-called admissible colors to each u∈V. The List Coloring problem is that of testing whether a given graph G=(V,E) has a coloring c that respects a given list assignmen... Read More about List coloring in the absence of two subgraphs.

Colouring of graphs with Ramsey-type forbidden subgraphs (2014)
Journal Article
Dabrowski, K., Golovach, P., & Paulusma, D. (2014). Colouring of graphs with Ramsey-type forbidden subgraphs. Theoretical Computer Science, 522, 34-43. https://doi.org/10.1016/j.tcs.2013.12.004

A colouring of a graph G=(V,E) is a mapping c:V→{1,2,…} such that c(u)≠c(v) if uv∈E; if |c(V)|⩽k then c is a k -colouring. The Colouring problem is that of testing whether a given graph has a k -colouring for some given integer k . If a graph contain... Read More about Colouring of graphs with Ramsey-type forbidden subgraphs.

Obtaining Online Ecological Colourings by Generalizing First-Fit (2014)
Journal Article
Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2014). Obtaining Online Ecological Colourings by Generalizing First-Fit. Theory of Computing Systems, 54(2), 244-260. https://doi.org/10.1007/s00224-013-9513-9

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vert... Read More about Obtaining Online Ecological Colourings by Generalizing First-Fit.

Knocking Out P_k-free Graphs (2014)
Presentation / Conference Contribution
Johnson, M., Paulusma, D., & Stewart, A. (2014). Knocking Out P_k-free Graphs. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29August 2014 ; proceedings, Part II (396-407). https://doi.org/10.1007/978-3-662-44465-8_34

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Paralle... Read More about Knocking Out P_k-free Graphs.

A Reconfigurations Analogue of Brooks’ Theorem (2014)
Presentation / Conference Contribution
Feghali, C., Johnson, M., & Paulusma, D. (2014). A Reconfigurations Analogue of Brooks’ Theorem. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29 August 2014 ; proceedings, Part II (287-298). https://doi.org/10.1007/978-3-662-44465-8_25

Let G be a simple undirected graph on n vertices with maximum degree Δ. Brooks’ Theorem states that G has a Δ-colouring unless G is a complete graph, or a cycle with an odd number of vertices. To recolour G is to obtain a new proper colouring by chan... Read More about A Reconfigurations Analogue of Brooks’ Theorem.

Editing to Eulerian Graphs (2014)
Presentation / Conference Contribution
Dabrowski, K. K., Golovach, P. A., Hof, V. P., & Paulusma, D. (2014). Editing to Eulerian Graphs. In V. Raman, & S. P. Suresh (Eds.), 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) (97-108). https://doi.org/10.4230/lipics.fsttcs.2014.97

We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and vertex deletion respectively.... Read More about Editing to Eulerian Graphs.

Classifying the Clique-Width of H-Free Bipartite Graphs (2014)
Presentation / Conference Contribution
Dabrowski, K. K., & Paulusma, D. (2014). Classifying the Clique-Width of H-Free Bipartite Graphs. In Z. Cai, A. Zelikovsky, & A. G. Bourgeois (Eds.), 20th International Conference, COCOON 2014, Atlanta, GA, USA, 4-6 August 2014 ; proceedings (489-500). https://doi.org/10.1007/978-3-319-08783-2_42

Let G be a bipartite graph, and let H be a bipartite graph with a fixed bipartition (B H ,W H ). We consider three different, natural ways of forbidding H as an induced subgraph in G. First, G is H-free if it does not contain H as an induced subgraph... Read More about Classifying the Clique-Width of H-Free Bipartite Graphs.

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time (2014)
Presentation / Conference Contribution
Golovach, P., Paulusma, D., & van Leeuwen, E. (2014). Induced Disjoint Paths in Circular-Arc Graphs in Linear Time. In 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, 25-27 June 2014 ; revised selected papers (225-237). https://doi.org/10.1007/978-3-319-12340-0_19

The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (si,ti) contains paths P1,…,Pk such that Pi connects si and ti for i=1,…,k, and Pi and Pj have neither common vertices nor adjacent vertices (except per... Read More about Induced Disjoint Paths in Circular-Arc Graphs in Linear Time.

Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs (2014)
Presentation / Conference Contribution
Huang, S., Johnson, M., & Paulusma, D. (2014). Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs. In Q. Gu, P. Hell, & B. Yang (Eds.), 10th International Conference, AAIM 2014, Vancouver, BC, Canada, 8-11 July 2014 ; proceedings (162-173). https://doi.org/10.1007/978-3-319-07956-1_15

Let k be a positive integer. The k-Colouring problem is to decide whether a graph has a k-colouring. The k-Precolouring Extension problem is to decide whether a colouring of a subset of a graph’s vertex set can be extended to a k-colouring of the who... Read More about Narrowing the Complexity Gap for Colouring (C_s,P_t)-Free Graphs.

Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set (2014)
Presentation / Conference Contribution
Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2014). Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), 39th International Symposium, MFCS 2014, Budapest, Hungary, 26-29 August 2014 ; proceedings, Part II (57-68). https://doi.org/10.1007/978-3-662-44465-8_6

Let fvs(G) and cfvs(G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. For a graph class G, the price of connectivity for feedback vertex set (poc-fvs) for G is defined... Read More about Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set.

Lift-contractions (2014)
Journal Article
Golovach, P., Paulusma, D., Kaminski, M., & Thilikos, D. (2014). Lift-contractions. European Journal of Combinatorics, 35, 286-296. https://doi.org/10.1016/j.ejc.2013.06.026

We introduce and study a partial order on graphs—lift-contractions. A graph H is a lift-contraction of a graph G if H can be obtained from G by a sequence of edge lifts and edge contractions. We give sufficient conditions for a connected graph to con... Read More about Lift-contractions.

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs (2014)
Journal Article
Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2014). Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, 27(1), 132-143. https://doi.org/10.1007/s10878-012-9490-y

A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if t... Read More about Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs.

Modifying a Graph Using Vertex Elimination (2013)
Journal Article
Golovach, P., Heggernes, P., Hof, V. '. P., Manne, F., Paulusma, D., & Pilipczuk, M. (2015). Modifying a Graph Using Vertex Elimination. Algorithmica, 72(1), 99-125. https://doi.org/10.1007/s00453-013-9848-2

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the Elimination problem as follows: given two g... Read More about Modifying a Graph Using Vertex Elimination.

Characterizing graphs of small carving-width (2013)
Journal Article
Belmonte, R., Hof, V. '. P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13-14), 1888-1893. https://doi.org/10.1016/j.dam.2013.02.036

We characterize all graphs that have carving-width at most k for k=1,2,3. In particular, we show that a graph has carving-width at most 3 if and only if it has maximum degree at most 3 and treewidth at most 2. This enables us to identify the immersio... Read More about Characterizing graphs of small carving-width.

Detecting induced minors in AT-free graphs (2013)
Journal Article
Golovach, P., Kratsch, D., & Paulusma, D. (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science, 482, 20-32. https://doi.org/10.1016/j.tcs.2013.02.029

The Induced Minor problem is that of testing whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. If only edge contractions are permitted, we obtain the Contractibility problem. We prove that Induc... Read More about Detecting induced minors in AT-free graphs.

List Coloring in the Absence of a Linear Forest (2013)
Journal Article
Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2015). List Coloring in the Absence of a Linear Forest. Algorithmica, 71(1), 21-35. https://doi.org/10.1007/s00453-013-9777-0

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The Listk-Coloring problem requires in addition that every vertex u must receive a color from some giv... Read More about List Coloring in the Absence of a Linear Forest.

Increasing the minimum degree of a graph by contractions (2013)
Journal Article
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Increasing the minimum degree of a graph by contractions. Theoretical Computer Science, 481, 74-84. https://doi.org/10.1016/j.tcs.2013.02.030

The Degree Contractibility problem is to test whether a given graph G can be modified to a graph of minimum degree at least d by using at most k contractions. We prove the following three results. First, Degree Contractibility is NP-complete even whe... Read More about Increasing the minimum degree of a graph by contractions.

Satisfiability of acyclic and almost acyclic CNF formulas (2013)
Journal Article
Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85-99. https://doi.org/10.1016/j.tcs.2012.12.039

We show that the Satisfiability (SAT) problem for CNF formulas with ββ-acyclic hypergraphs can be solved in polynomial time by using a special type of Davis–Putnam resolution in which each resolvent is a subset of a parent clause. We extend this clas... Read More about Satisfiability of acyclic and almost acyclic CNF formulas.

Three complexity results on coloring Pk-free graphs (2013)
Journal Article
Broersma, H., Fomin, F., Golovach, P., & Paulusma, D. (2013). Three complexity results on coloring Pk-free graphs. European Journal of Combinatorics, 34(3), 609-619. https://doi.org/10.1016/j.ejc.2011.12.008

We prove three complexity results on vertex coloring problems restricted to PkPk-free graphs, i.e., graphs that do not contain a path on kk vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring r... Read More about Three complexity results on coloring Pk-free graphs.

Obtaining planarity by contracting few edges (2013)
Journal Article
Golovach, P., van 't Hof, P., & Paulusma, D. (2013). Obtaining planarity by contracting few edges. Theoretical Computer Science, 476, 38-46. https://doi.org/10.1016/j.tcs.2012.12.041

The Planar Contraction problem is to test whether a given graph can be made planar by using at most kk edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by kk.

Choosability on H-free graphs (2013)
Journal Article
Golovach, P., Heggernes, P., van 't Hof, P., & Paulusma, D. (2013). Choosability on H-free graphs. Information Processing Letters, 113(4), 107-110. https://doi.org/10.1016/j.ipl.2012.12.003

A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the Choosability problem restricted to H-free graphs for every graph H that does not belong to {K1,3,P1+P2,P1+P3,P4}{K1,3,P1+P2,P1+P3,P4}. W... Read More about Choosability on H-free graphs.

Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree (2013)
Presentation / Conference Contribution
Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesar, M. (2013). Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree. In L. Gąsieniec, & F. Wolter (Eds.), Fundamentals of computation theory : 19th International Symposium, FCT 2013, 19-21 August 2013, Liverpool, UK ; proceedings (121-132). https://doi.org/10.1007/978-3-642-40164-0_14

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether... Read More about Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree.

Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints (2013)
Presentation / Conference Contribution
Belmonte, R., Golovach, P., Hof, V. '. P., & Paulusma, D. (2013). Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. In 8th International Symposium, IPEC 2013, 4-6 September 2013, Sophia Antipolis, France ; revised selected papers (16-27). https://doi.org/10.1007/978-3-319-03898-8_3

Motivated by recent results of Mathieson and Szeider (J. Comput. Syst. Sci. 78(1): 179–191, 2012), we study two graph modification problems where the goal is to obtain a graph whose vertices satisfy certain degree constraints. The Regular Contraction... Read More about Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints.

Colouring of Graphs with Ramsey-Type Forbidden Subgraphs (2013)
Presentation / Conference Contribution
Dabrowski, K. K., Golovach, P. A., & Paulusma, D. (2013). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.), Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers (201-212). https://doi.org/10.1007/978-3-642-45043-3_18

A colouring of a graph G = (V;E) is a mapping c : V ! f1; 2; : : :g such that c(u) 6= c(v) if uv 2 E; if jc(V )j k then c is a k-colouring. The Colouring problem is that of testing whether a given graph has a k-colouring for some given integer k. If... Read More about Colouring of Graphs with Ramsey-Type Forbidden Subgraphs.

Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs (2013)
Presentation / Conference Contribution
Johnson, M., Paulusma, D., & van Leeuwen, E. (2013). Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs. In L. Cai, S. Cheng, & T. Lam (Eds.), Algorithms and computation : 24th International Symposium, ISAAC 2013, Hong Kong, China, 16-18 December 2013 ; proceedings (130-140). https://doi.org/10.1007/978-3-642-45030-3_13

Social networks are often analyzed through a graph model of the network. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d-dimensional vector a v repr... Read More about Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs.

List Coloring in the Absence of Two Subgraphs (2013)
Presentation / Conference Contribution
Golovach, P. A., & Paulusma, D. (2013). List Coloring in the Absence of Two Subgraphs. In P. G. Spirakis, & M. Serna (Eds.), Algorithms and complexity : 8th International Conference, CIAC 2013, 22-24 May 2013, Barcelona, Spain ; proceedings (288-299). https://doi.org/10.1007/978-3-642-38233-8_24

list assignment of a graph G = (V;E) is a function L that assigns a list L(u) of so-called admissible colors to each u 2 V . The List Coloring problem is that of testing whether a given graph G = (V;E) has a coloring c that respects a given list assi... Read More about List Coloring in the Absence of Two Subgraphs.

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs (2013)
Presentation / Conference Contribution
Broersma, H. J., Fiala, J., Golovach, P. A., Kaiser, T., Paulusma, D., & Proskurowski, A. (2013). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.), Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, 19-21 June 2013, Lübeck, Germany ; revised papers (127-138). https://doi.org/10.1007/978-3-642-45043-3_12

We show that for all k ≤ − 1 an interval graph is − (k + 1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(n + m) time algorithm for computing the scattering number of an interval graph with n vertices and m e... Read More about Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.

Sparse Square Roots (2013)
Presentation / Conference Contribution
Cochefert, M., Couturier, J., Golovach, P. A., Kratsch, D., & Paulusma, D. (2013). Sparse Square Roots. In A. Brandstädt, K. Jansen, & R. Reischuk (Eds.), Graph-theoretic concepts in computer science : 39th International Workshop, WG 2013, Lübeck, Germany, 19-21 June 2013 ; revised papers (177-188). https://doi.org/10.1007/978-3-642-45043-3_16

We show that it can be decided in polynomial time whether a graph of maximum degree 6 has a square root; if a square root exists, then our algorithm finds one with minimum number of edges. We also show that it is FPT to decide whether a connected n-v... Read More about Sparse Square Roots.

The price of connectivity for feedback vertex set (2013)
Presentation / Conference Contribution
Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2013). The price of connectivity for feedback vertex set. In J. Nešetřil, & M. Pellegrini (Eds.), The seventh European conference on combinatorics, graph theory and applications (123-128). https://doi.org/10.1007/978-88-7642-475-5_20

Let fvs(G) and cfvs(G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. In general graphs, the ratio cfvs(G)/fvs(G) can be arbitrarily large. We study the interdependenc... Read More about The price of connectivity for feedback vertex set.

Model counting for CNF formuals of bounded module treewidth (2013)
Presentation / Conference Contribution
Paulusma, D., Slivovksy, F., & Szeider, S. (2013). Model counting for CNF formuals of bounded module treewidth. In N. Portier, & T. Wilke (Eds.), 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) (55-66). https://doi.org/10.4230/lipics.stacs.2013.55

The modular treewidth of a graph is its treewidth after the contraction of modules. Modular treewidth properly generalizes treewidth and is itself properly generalized by clique-width. We show that the number of satisfying assignments of a CNF formul... Read More about Model counting for CNF formuals of bounded module treewidth.

Graph editing to a fixed target (2013)
Presentation / Conference Contribution
Golovach, P., Paulusma, D., & Stewart, I. A. (2013). Graph editing to a fixed target. In T. Lecroq, & L. Mouchard (Eds.), Combinatorial algorithms : 24th International Workshop, IWOCA 2013, 10-12 July 2013, Rouen, France ; revised selected papers (192-205). https://doi.org/10.1007/978-3-642-45278-9_17

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex di... Read More about Graph editing to a fixed target.

A note on contracting claw-free graphs (2013)
Journal Article
Fiala, J., Kaminski, M., & Paulusma, D. (2013). A note on contracting claw-free graphs. Discrete Mathematics & Theoretical Computer Science, 15(2), 223-232

A graph containment problem is to decide whether one graph called the host graph can be modified into some other graph called the target graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex dele... Read More about A note on contracting claw-free graphs.

4-Coloring H-free graphs when H is small (2013)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2013). 4-Coloring H-free graphs when H is small. Discrete Applied Mathematics, 161(1-2), 140-150. https://doi.org/10.1016/j.dam.2012.08.022

The kk-Coloring problem is to test whether a graph can be colored with at most kk colors such that no two adjacent vertices receive the same color. If a graph GG does not contain a graph HH as an induced subgraph, then GG is called HH-free. For any f... Read More about 4-Coloring H-free graphs when H is small.

Exact algorithms for finding longest cycles in claw-free graphs (2013)
Journal Article
Broersma, H., Fomin, F., Hof van 't, P., & Paulusma, D. (2013). Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica, 65(1), 129 -145. https://doi.org/10.1007/s00453-011-9576-4

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in O*(an)(n) time for some co... Read More about Exact algorithms for finding longest cycles in claw-free graphs.

Characterizing graphs of small carving-width (2012)
Presentation / Conference Contribution
Belmonte, R., van 't Hof, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Characterizing graphs of small carving-width. In G. Lin (Ed.), Combinatorial optimization and applications : 6th International Conference, COCOA 2012, 5-9 August 2012, Banff, AB, Canada ; proceedings (360-370). https://doi.org/10.1007/978-3-642-31770-5_32

We characterize all graphs that have carving-width at most k for k = 1,2,3. In particular, we show that a graph has carving-width at most 3 if and only if it has maximum degree at most 3 and treewidth at most 2. This enables us to identify the immers... Read More about Characterizing graphs of small carving-width.

How to eliminate a graph (2012)
Presentation / Conference Contribution
Golovach, P., Heggernes, P., van 't Hof, P., Manne, F., Paulusma, D., & Pilipczuk, M. (2012). How to eliminate a graph. In M. C. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science: 38th international workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, revised selected papers (320-331). https://doi.org/10.1007/978-3-642-34611-8_32

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the Elimination problem as follows: given two g... Read More about How to eliminate a graph.

4-Coloring H-free graphs when H is small (2012)
Presentation / Conference Contribution
Golovach, P., Paulusma, D., & Song, J. (2012). 4-Coloring H-free graphs when H is small. In M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, & G. Turán (Eds.), Theory and practice of computer science : 38th Conference on Current trends in theory and practice of computer science, SOFSEM 2012, Špindlerův Mlýn, Czech Republic, 21-27 January 2012 ; proceedings (289-300). https://doi.org/10.1007/978-3-642-27660-6_24

The k-Coloring problem is to test whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. If a graph G does not contain a graph H as an induced subgraph, then G is called H-free. For any fixed g... Read More about 4-Coloring H-free graphs when H is small.

Coloring graphs characterized by a forbidden subgraph (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Ries, B. (2012). Coloring graphs characterized by a forbidden subgraph. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical foundations of computer science 2012 : 37th International Symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings (443-454). https://doi.org/10.1007/978-3-642-32589-2_40

The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an in... Read More about Coloring graphs characterized by a forbidden subgraph.

Solutions for the stable rommates problem with payments (2012)
Presentation / Conference Contribution
Biró, P., Bomhoff, M., Golovach, P. A., Kern, W., & Paulusma, D. (2012). Solutions for the stable rommates problem with payments. In M. C. Golumbic, M. Stern, A. Levy, & G. Morgenstern (Eds.), Graph-theoretic concepts in computer science : 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 June 2012 ; revised selected papers (69-80). https://doi.org/10.1007/978-3-642-34611-8_10

The stable roommates problem with payments has as input a graph G = (V,E) with an edge weighting w: E → ℝ +  and the problem is to find a stable solution. A solution is a matching M with a vector p∈R V + that satisfies pu + pv = w(uv) for all uv ∈ M... Read More about Solutions for the stable rommates problem with payments.

Induced disjoint paths in AT-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012). Induced disjoint paths in AT-free graphs. In F. V. Fomin, & P. Kaski (Eds.), Algorithm Theory : 13th Scandinavian Symposium and Workshops, SWAT 2012, Helsinki, Finland, 4-6 July 2012 ; proceedings (153-164). https://doi.org/10.1007/978-3-642-31155-0_14

Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i 

Induced disjoint paths in claw-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012). Induced disjoint paths in claw-free graphs. In L. Epstein, & P. Ferragina (Eds.), Algorithms, 20th Annual European Symposium, ESA 2012, Ljubljana, Slovenia, 10-12 September 2012 ; proceedings (515-526). https://doi.org/10.1007/978-3-642-33090-2_45

Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i 

Closing complexity gaps for coloring problems on H-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Song, J. (2012). Closing complexity gaps for coloring problems on H-free graphs. In K. Chao, T. Hsu, & D. Lee (Eds.), Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings (14-23). https://doi.org/10.1007/978-3-642-35261-4_5

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then... Read More about Closing complexity gaps for coloring problems on H-free graphs.

Finding vertex-surjective graph homomorphisms (2012)
Presentation / Conference Contribution
Golovach, P. A., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. In E. A. Hirsch, J. Karhumäki, A. Lepistö, & M. Prilutskii (Eds.), Computer science : theory and applications : 7th International Computer Science Symposium in Russia, CSR 2012, 3-7 July 2012, Nizhny Novgorod, Russia ; proceedings (160-171). https://doi.org/10.1007/978-3-642-30642-6_16

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulat... Read More about Finding vertex-surjective graph homomorphisms.

Obtaining planarity by contracting few edges (2012)
Presentation / Conference Contribution
Golovach, P. A., van 't Hog, P., & Paulusma, D. (2012). Obtaining planarity by contracting few edges. In B. Rovan, V. Sassone, & P. Widmayer (Eds.), Mathematical foundations of computer science 2012 : 37th international symposium, MFCS 2012, Bratislava, Slovakia, 27-31 August 2012 ; proceedings (455-466). https://doi.org/10.1007/978-3-642-32589-2_41

The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k.

Detecting induced minors in AT-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Kratsch, D., & Paulusma, D. (2012). Detecting induced minors in AT-free graphs. In K. Chao, T. Hsu, & D. Lee (Eds.), Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings (495-505). https://doi.org/10.1007/978-3-642-35261-4_52

The problem Induced Minor is to test whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. We prove that Induced Minor is polynomial-time solvable when G is AT-free, and H is fixed, i.e., not part o... Read More about Detecting induced minors in AT-free graphs.

Detecting induced star-like minors in polynomial time (2012)
Journal Article
Fiala, J., Kaminksi, M., & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of discrete algorithms, 17, 74-85. https://doi.org/10.1016/j.jda.2012.11.002

The Induced Minor problem is to test whether a graph G contains a graph H as an induced minor, i.e., if G can be modified into H by a sequence of vertex deletions and edge contractions. When H is fixed, i.e., not part of the input, this problem is de... Read More about Detecting induced star-like minors in polynomial time.

Computing vertex-surjective homomorphisms to partially reflexive trees (2012)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2012). Computing vertex-surjective homomorphisms to partially reflexive trees. Theoretical Computer Science, 457, 86-100. https://doi.org/10.1016/j.tcs.2012.06.039

A homomorphism from a graph GG to a graph HH is a vertex mapping f:VG→VHf:VG→VH such that f(u)f(u) and f(v)f(v) form an edge in HH whenever uu and vv form an edge in GG. The HH-Coloring problem is that of testing whether a graph GG allows a homomorph... Read More about Computing vertex-surjective homomorphisms to partially reflexive trees.

Finding vertex-surjective graph homomorphisms (2012)
Journal Article
Golovach, P., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. Acta Informatica, 49(6), 381-394. https://doi.org/10.1007/s00236-012-0164-0

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulat... Read More about Finding vertex-surjective graph homomorphisms.

On the parameterized complexity of coloring graphs in the absence of a linear forest (2012)
Journal Article
Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2012). On the parameterized complexity of coloring graphs in the absence of a linear forest. Journal of discrete algorithms, 15, 56-62. https://doi.org/10.1016/j.jda.2012.04.008

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The Listk-Coloring problem requires in addition that every vertex u must receive a color from some giv... Read More about On the parameterized complexity of coloring graphs in the absence of a linear forest.

Computing role assignments of proper interval graphs in polynomial time (2012)
Journal Article
Heggernes, P., van 't Hof, P., & Paulusma, D. (2012). Computing role assignments of proper interval graphs in polynomial time. Journal of discrete algorithms, 14, 173-188. https://doi.org/10.1016/j.jda.2011.12.004

An R-role assignment of a graph G is a locally surjective homomorphism from G to graph R. For a fixed graph R, the R-Role Assignment problem is to decide, for an input graph G, whether G has an R-role assignment. When both graphs G and R are given as... Read More about Computing role assignments of proper interval graphs in polynomial time.

On graph contractions and induced minors (2012)
Journal Article
Hof, P. V. '., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. (2012). On graph contractions and induced minors. Discrete Applied Mathematics, 160(6), 799-809. https://doi.org/10.1016/j.dam.2010.05.005

The Induced Minor Containment problem takes as input two graphs G and H, and asks whether G has H as an induced minor. We show that this problem is fixed parameter tractable in |VH| if G belongs to any nontrivial minor-closed graph class and H is a p... Read More about On graph contractions and induced minors.

Distance three labelings of trees (2012)
Journal Article
Fiala, J., Golovach, P., Kratochvil, J., Lidický, B., & Paulusma, D. (2012). Distance three labelings of trees. Discrete Applied Mathematics, 160(6), 764-779. https://doi.org/10.1016/j.dam.2011.02.004

An L(2,1,1)-labeling of a graph G assigns nonnegative integers to the vertices of G in such a way that labels of adjacent vertices differ by at least two, while vertices that are at distance at most three are assigned different labels. The maximum la... Read More about Distance three labelings of trees.

Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time (2012)
Journal Article
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. Theoretical Computer Science, 423, 1-10. https://doi.org/10.1016/j.tcs.2011.12.076

Let 2P3 denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H-free. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. Its computational comp... Read More about Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time.

Induced packing of odd cycles in planar graphs (2012)
Journal Article
Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2012). Induced packing of odd cycles in planar graphs. Theoretical Computer Science, 420, 28-35. https://doi.org/10.1016/j.tcs.2011.11.004

An induced packing of odd cycles in a graph is a packing such that there is no edge in the graph between any two odd cycles in the packing. We prove that an induced packing of k odd cycles in an n-vertex graph can be found (if it exists) in time 2O(k... Read More about Induced packing of odd cycles in planar graphs.

The k-in-a-path problem for claw-free graphs (2012)
Journal Article
Fiala, J., Kamiński, M., Lidický, B., & Paulusma, D. (2012). The k-in-a-path problem for claw-free graphs. Algorithmica, 62(1-2), 499-519. https://doi.org/10.1007/s00453-010-9468-z

The k-in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbit... Read More about The k-in-a-path problem for claw-free graphs.

Finding induced paths of given parity in claw-free graphs (2012)
Journal Article
Hof van 't, P., Kamiński, M., & Paulusma, D. (2012). Finding induced paths of given parity in claw-free graphs. Algorithmica, 62(1-2), 537-563. https://doi.org/10.1007/s00453-010-9470-5

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determ... Read More about Finding induced paths of given parity in claw-free graphs.

Updating the complexity status of coloring graphs without a fixed induced linear forest (2012)
Journal Article
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoretical Computer Science, 414(1), 9-19. https://doi.org/10.1016/j.tcs.2011.10.005

A graph is H-free if it does not contain an induced subgraph isomorphic to the graph H. The graph Pk denotes a path on k vertices. The ℓ-Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent... Read More about Updating the complexity status of coloring graphs without a fixed induced linear forest.

Computing solutions for matching games (2012)
Journal Article
Biro, P., Kern, W., & Paulusma, D. (2012). Computing solutions for matching games. International Journal of Game Theory, 41(1), 75-90. https://doi.org/10.1007/s00182-011-0273-y

A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting w: E® \mathbb R+w:ER+. The player set is N and the value of a coalition S Í NSN is defined as the maximum weight of a matching in the subgraph induced b... Read More about Computing solutions for matching games.

Containment relations in split graphs (2012)
Journal Article
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2012). Containment relations in split graphs. Discrete Applied Mathematics, 160(1-2), 155-163. https://doi.org/10.1016/j.dam.2011.10.004

A graph containment problem is to decide whether one graph can be modified into some other graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible grap... Read More about Containment relations in split graphs.

Lift Contractions (2011)
Presentation / Conference Contribution
Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Lift Contractions. Electronic Notes in Discrete Mathematics, 38(1), 407-412. https://doi.org/10.1016/j.endm.2011.09.066

We introduce and study a new containment relation in graphs – lift contractions. H is a lift contraction of G if H can be obtained from G by a sequence of edge lifts and edge contractions. We show that a graph contains every n-vertex graph as a lift... Read More about Lift Contractions.

On the diameter of reconfiguration graphs for vertex colourings (2011)
Presentation / Conference Contribution
Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2011). On the diameter of reconfiguration graphs for vertex colourings. Electronic Notes in Discrete Mathematics, 38(1), 161-166. https://doi.org/10.1016/j.endm.2011.09.028

The reconfiguration graph of the k-colourings of a graph G contains as its vertex set the proper vertex k-colourings of G, and two colourings are joined by an edge in the reconfiguration graph if they differ in colour on just one vertex of G. We prov... Read More about On the diameter of reconfiguration graphs for vertex colourings.

On partitioning a graph into two connected subgraphs (2011)
Journal Article
Paulusma, D., & Rooij van, J. (2011). On partitioning a graph into two connected subgraphs. Theoretical Computer Science, 412(48), 6761-6769. https://doi.org/10.1016/j.tcs.2011.09.001

Suppose a graph G is given with two vertex-disjoint sets of vertices Z1 and Z2. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z1 and Z2, respectively? This problem is known... Read More about On partitioning a graph into two connected subgraphs.

Parameterizing cut sets in a graph by the number of their components (2011)
Journal Article
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). Parameterizing cut sets in a graph by the number of their components. Theoretical Computer Science, 412(45), 6340-6350. https://doi.org/10.1016/j.tcs.2011.07.005

For a connected graph G=(V,E), a subset U⊆V is a disconnected cut if U disconnects G and the subgraph G[U] induced by U is disconnected as well. A cut U is a k-cut if G[U] contains exactly k(≥1) components. More specifically, a k-cut U is a (k,ℓ)-cut... Read More about Parameterizing cut sets in a graph by the number of their components.

Contracting planar graphs to contractions of triangulations (2011)
Journal Article
Kamiński, M., Paulusma, D., & Thilikos, D. (2011). Contracting planar graphs to contractions of triangulations. Journal of discrete algorithms, 9(3), 299-306. https://doi.org/10.1016/j.jda.2011.03.010

For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs C such that for every fixed H∈C, ther... Read More about Contracting planar graphs to contractions of triangulations.

On disconnected cuts and separators (2011)
Journal Article
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. (2011). On disconnected cuts and separators. Discrete Applied Mathematics, 159(13), 1345-1351. https://doi.org/10.1016/j.dam.2011.04.027

For a connected graph G=(V,E), a subset U⊆V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u∈U, the subgraph induced by (V∖U)∪{u} is connec... Read More about On disconnected cuts and separators.

Computing Role Assignments of Proper Interval Graphs in Polynomial Time (2011)
Presentation / Conference Contribution
Heggernes, P., Hof, V. P., & Paulusma, D. (2011). Computing Role Assignments of Proper Interval Graphs in Polynomial Time. In C. S. Iliopoulos, & W. F. Smyth (Eds.), Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, July 26-28, 2010, revised selected papers (167-180). https://doi.org/10.1007/978-3-642-19222-7_18

A homomorphism from a graph G to a graph R is locally surjective if its restriction to the neighborhood of each vertex of G is surjective. Such a homomorphism is also called an R-role assignment of G. Role assignments have applications in distributed... Read More about Computing Role Assignments of Proper Interval Graphs in Polynomial Time.

Satisfiability of acyclic and almost acyclic CNF formulas (II) (2011)
Presentation / Conference Contribution
Ordyniak, S., Paulusma, D., & Szeider, S. (2011). Satisfiability of acyclic and almost acyclic CNF formulas (II). In K. A. Sakallah, & L. Simons (Eds.), Theory and Applications of Satisfiability Testing - SAT 2011, 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011 ; proceedings (47-60). https://doi.org/10.1007/978-3-642-21581-0_6

In the first part of this work (FSTTCS’10) we have shown that the satisfiability of CNF formulas with β-acyclic hypergraphs can be decided in polynomial time. In this paper we continue and extend this work. The decision algorithm for β-acyclic formul... Read More about Satisfiability of acyclic and almost acyclic CNF formulas (II).

Contracting a chordal graph to a split graph or a tree (2011)
Presentation / Conference Contribution
Golovach, P. A., Kaminski, M., & Paulusma, D. (2011). Contracting a chordal graph to a split graph or a tree. In F. Murlak, & P. Sankowski (Eds.), Mathematical Foundations of Computer Science 2011, 36th International Symposium, MFCS 2011, Warsaw, Poland, August 22-26, 2011 ; proceedings (339-350). https://doi.org/10.1007/978-3-642-22993-0_32

The problems Contractibility and Induced Minor are to test whether a graph G contains a graph H as a contraction or as an induced minor, respectively. We show that these two problems can be solved in |VG|f(|VH|)VGf(VH) time if G is a chordal input gr... Read More about Contracting a chordal graph to a split graph or a tree.

The computational complexity of Disconnected Cut and 2K2-Partition (2011)
Presentation / Conference Contribution
Martin, B., & Paulusma, D. (2011). The computational complexity of Disconnected Cut and 2K2-Partition. In J. Lee (Ed.), Principles and practice of constraint programming, 17th International Conference, CP 2011, 12-16 September 2011, Perugia, Italy ; proceedings (561-575). https://doi.org/10.1007/978-3-642-23786-7_43

For a connected graph G = (V,E), a subset U ⊆ V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. Thi... Read More about The computational complexity of Disconnected Cut and 2K2-Partition.

List coloring in the absence of a linear forest (2011)
Presentation / Conference Contribution
Couturier, J. F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2011). List coloring in the absence of a linear forest. In P. Kolman, & J. Kratochvil (Eds.), Graph-theoretic concepts in computer science, 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011 ; revised papers (119-130). https://doi.org/10.1007/978-3-642-25870-1_12

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k -Coloring problem requires in addition that every vertex u must receive a color from some g... Read More about List coloring in the absence of a linear forest.

Computing vertex-surjective homomorphisms to partially reflexive trees (2011)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Song, J. (2011). Computing vertex-surjective homomorphisms to partially reflexive trees. In A. Kulikov, & N. Vereshchagin (Eds.), Computer Science : Theory and Applications, 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011 ; proceedings (261-274). https://doi.org/10.1007/978-3-642-20712-9_20

Coloring graphs without short cycles and long induced paths (2011)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Song, J. (2011). Coloring graphs without short cycles and long induced paths. In O. Owe, M. Steffen, & J. A. Telle (Eds.), Fundamentals of computation theory, 18th International Symposium (FCT 2011), 22-25 August 2011, Oslo, Norway ; proceedings (193-204). https://doi.org/10.1007/978-3-642-22953-4_17

The girth of a graph G is the length of a shortest cycle in G. For any fixed girth g ≥ 4 we determine a lower bound ℓ(g) such that every graph with girth at least g and with no induced path on ℓ(g) vertices is 3-colorable. In contrast, we show the ex... Read More about Coloring graphs without short cycles and long induced paths.

Finding contractions and induced minors in chordal graphs via disjoint paths (2011)
Presentation / Conference Contribution
Belmonte, R., Golovach, P. A., Heggernes, P., Hof van 't, P., Kaminski, M., & Paulusma, D. (2011). Finding contractions and induced minors in chordal graphs via disjoint paths. In T. Asano, S. Nakano, Y. Okamoto, & O. Watanabe (Eds.), Algorithms and Computation, 22nd International Symposium, ISAAC 2011, Yokohama, Japan, 5-8 December 2011 ; proceedings (110-119). https://doi.org/10.1007/978-3-642-25591-5_13

The k-Disjoint Paths problem, which takes as input a graph G and k pairs of specified vertices (s i ,t i ), asks whether G contains k mutually vertex-disjoint paths P i such that P i connects s i and t i , for i = 1,…,k. We study a natural variant of... Read More about Finding contractions and induced minors in chordal graphs via disjoint paths.

Obtaining online ecological colourings by generalizing first-fit (2010)
Presentation / Conference Contribution
Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010). Obtaining online ecological colourings by generalizing first-fit. . https://doi.org/10.1007/978-3-642-13182-0_22

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vert... Read More about Obtaining online ecological colourings by generalizing first-fit.

Computing role assignments of chordal graphs (2010)
Journal Article
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2010). Computing role assignments of chordal graphs. Theoretical Computer Science, 411(40-42), 3601-3613. https://doi.org/10.1016/j.tcs.2010.05.041

In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,…,k}, called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles a... Read More about Computing role assignments of chordal graphs.

Computing sharp 2-factors in claw-free graphs (2010)
Journal Article
Broersma, H., & Paulusma, D. (2010). Computing sharp 2-factors in claw-free graphs. Journal of discrete algorithms, 8(3), 321-329. https://doi.org/10.1016/j.jda.2009.07.001

In a previous paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we... Read More about Computing sharp 2-factors in claw-free graphs.

Path factors and parallel knock-out schemes of almost claw-free graphs (2010)
Journal Article
Johnson, M., Paulusma, D., & Wood, C. (2010). Path factors and parallel knock-out schemes of almost claw-free graphs. Discrete Mathematics, 310(9), 1413-1423. https://doi.org/10.1016/j.disc.2009.04.022

An H1,{H2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H1 and all other components (if there are any) isomorphic to the graph H2. We completely characterise the class of connected almost claw-fre... Read More about Path factors and parallel knock-out schemes of almost claw-free graphs.

Comparing universal covers in polynomial time (2010)
Journal Article
Fiala, J., & Paulusma., D. (2010). Comparing universal covers in polynomial time. Theory of Computing Systems, 46(4), 620-635. https://doi.org/10.1007/s00224-009-9200-z

The universal cover T G of a connected graph G is the unique (possibly infinite) tree covering G, i.e., that allows a locally bijective homomorphism from T G to G. It is well-known that if a graph G covers a graph H, then their universal covers are i... Read More about Comparing universal covers in polynomial time.

A new characterization of P6-free graphs (2010)
Journal Article
Hof, P. V. '., & Paulusma, D. (2010). A new characterization of P6-free graphs. Discrete Applied Mathematics, 158(7), 731-740. https://doi.org/10.1016/j.dam.2008.08.025

We study P6-free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph G is P6-free if and only if each connected induced subgraph of G on more than one vertex... Read More about A new characterization of P6-free graphs.

Path factors and parallel knock-out schemes of almost claw-free graphs (2010)
Presentation / Conference Contribution
Johnson, M., Paulusma, D., & Wood, C. (2010). Path factors and parallel knock-out schemes of almost claw-free graphs. In M. Miller, & K. Wada (Eds.), Proceedings of the International Workshop on Combinatorial Algorithms 2008 (27-41). https://doi.org/10.1016/j.disc.2009.04.022

An H1, {H2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H1 and all other components (if there are any) isomorphic to the graph H2.We completely characterise the class of connected almost claw-fre... Read More about Path factors and parallel knock-out schemes of almost claw-free graphs.

L(2,1,1)-labeling is NP-complete for trees (2010)
Presentation / Conference Contribution
Golovach, P. A., Lidicky, B., & Paulusma, D. (2010). L(2,1,1)-labeling is NP-complete for trees. In J. Kratochvíl, A. Li, J. Fiala, & P. Kolman (Eds.), Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings (211-221). https://doi.org/10.1007/978-3-642-13562-0_20

An L(p 1,p 2,p 3)-labeling of a graph G with span λ is a mapping f that assigns each vertex u of G an integer label 0 ≤ f(u) ≤ λ such that |f(u) − f(v)| ≥ p i whenever vertices u and v are of distance i for i ∈ {1,2,3}. We show that testing whether a... Read More about L(2,1,1)-labeling is NP-complete for trees.

On contracting graphs to fixed pattern graphs (2010)
Presentation / Conference Contribution
't, H. P. V., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. M. (2010). On contracting graphs to fixed pattern graphs. In J. van Leeuwen, A. Muscholl, D. Peleg, J. Pokorný, & B. Rumpe (Eds.), Theory and Practice of Computer Science, 36th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2010, Špindleruv Mlýn, Czech Republic, 23-29 January 2010 ; proceedings (503-514). https://doi.org/10.1007/978-3-642-11266-9_42

For a fixed graph H, the H-Contractibility problem asks if a graph is H-contractible, i.e., can be transformed into H via a series of edge contractions. The computational complexity classification of this problem is still open. So far, H has a domina... Read More about On contracting graphs to fixed pattern graphs.

On solution concepts for matching games (2010)
Presentation / Conference Contribution
Biro, P., Kern, W., & Paulusma, D. (2010). On solution concepts for matching games. In J. Kratochvíl, A. Li, J. Fiala, & P. Kolman (Eds.), Theory and applications of mdels of computation, 7th Annual Conference, TAMC 2010, 7-11 June 2010, Prague, Czech Republic ; proceedings (211-221). https://doi.org/10.1007/978-3-642-13562-0_12

A matching game is a cooperative game (N,v) defined on a graph G = (N,E) with an edge weighting . The player set is N and the value of a coalition S ⊆ N is defined as the maximum weight of a matching in the subgraph induced by S. First we present an... Read More about On solution concepts for matching games.

Packing bipartite graphs with covers of complete bipartite graphs (2010)
Presentation / Conference Contribution
Chalopin, J., & Paulusma, D. (2010). Packing bipartite graphs with covers of complete bipartite graphs. In T. Calamoneri, & J. Diaz (Eds.), Algorithms and complexity, 7th International Conference, CIAC 2010, 26-28 May 2010, Rome, Italy ; proceedings (276-287). https://doi.org/10.1007/978-3-642-13073-1_25

For a set of graphs, a perfect -packing (-factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of and that together contain all vertices of G. If G allows a covering (locally bijective homomorp... Read More about Packing bipartite graphs with covers of complete bipartite graphs.

The k-in-a-path problem for claw-free graphs (2010)
Presentation / Conference Contribution
Fiala, J., Kaminski, M., Lidicky, B., & Paulusma, D. (2010). The k-in-a-path problem for claw-free graphs. In J. Marion, & T. Schwentick (Eds.), 27th International symposium on theoretical aspects of computer science, STACS 2010, 4-6 March 2010 ; proceedings (371-382). https://doi.org/10.4230/lipics.stacs.2010.2469

Testing whether there is an induced path in a graph spanning $k$ given vertices is already \NP-complete in general graphs when $k=3$. We show how to solve this problem in polynomial time on claw-free graphs, when $k$ is not part of the input but an a... Read More about The k-in-a-path problem for claw-free graphs.

Contractions of planar graphs in polynomial time (2010)
Presentation / Conference Contribution
Kaminski, M., Paulusma, D., & Thilikos, D. (2010). Contractions of planar graphs in polynomial time. In Algorithms : ESA 2010 : 18th Annual European Symposium, 6-8 September 2010, Liverpool UK ; proceedings part I (122-133). https://doi.org/10.1007/978-3-642-15775-2_11

We prove that for every graph H, there exists a polynomial-time algorithm deciding if a planar graph can be contracted to H. We introduce contractions and topological minors of embedded (plane) graphs and show that a plane graph H is an embedded cont... Read More about Contractions of planar graphs in polynomial time.

Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs (2009)
Presentation / Conference Contribution
Broersma, H. J., Fomin, F. V., Hof van 't, P., & Paulusma, D. (2009). Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs. In M. Habib, & C. Paul (Eds.), Graph-theoretic concepts in computer science : 35th International Workshop, WG 2009, 24-26 June 2009, Montpellier, France ; revised papers (44-53). https://doi.org/10.1007/978-3-642-11409-0_4

The Hamiltonian Cycle problem asks if an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. So far, finding an exact algorithm that solves it in O *(α n ) time for some constant α

Finding Induced Paths of Given Parity in Claw-Free Graphs (2009)
Presentation / Conference Contribution
Hof van 't, P., Kaminski, M., & Paulusma, D. (2009). Finding Induced Paths of Given Parity in Claw-Free Graphs. In C. Paul, & M. Habib (Eds.), Graph-theoretic concepts in computer science (341-352). https://doi.org/10.1007/978-3-642-11409-0_30

The Parity Path problem is to decide if a given graph G contains both an odd length and an even length induced path between two specified vertices s and t. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine wheth... Read More about Finding Induced Paths of Given Parity in Claw-Free Graphs.

On partitioning a graph into two connected subgraphs (2009)
Presentation / Conference Contribution
Paulusma, D., & Rooij van, J. M. M. (2009). On partitioning a graph into two connected subgraphs. In Y. Dong, D. Du, & I. Ibarra (Eds.), Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings (1215-1224). https://doi.org/10.1007/978-3-642-10631-6_122

Suppose a graph G is given with two vertex-disjoint sets of vertices Z₁ and Z₂. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z₁ and Z₂, respectively? This problem is known... Read More about On partitioning a graph into two connected subgraphs.

Parameterizing cut sets in a graph by the number of their components (2009)
Presentation / Conference Contribution
Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009). Parameterizing cut sets in a graph by the number of their components. In Y. Dong, D. Du, & I. Ibarra (Eds.), Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings (605-615). https://doi.org/10.1007/978-3-642-10631-6_62

For a connected graph G = (V,E), a subset U ⊆ V is called a k-cut if U disconnects G, and the subgraph induced by U contains exactly k ( ≥ 1) components. More specifically, a k-cut U is called a (k,ℓ)-cut if V \U induces a subgraph with exactly ℓ ( ≥... Read More about Parameterizing cut sets in a graph by the number of their components.

Three complexity results on coloring Pk-free graphs (2009)
Presentation / Conference Contribution
Broersma, H. J., Fomin, F. V., Golovach, P. A., & Paulusma, D. (2009). Three complexity results on coloring Pk-free graphs. In J. Fiala, J. Kratochvíl, & M. Miller (Eds.), Combinatorial algorithms : 20th InternationalWorkshop, IWOCA 2009, 28 June - 2 July 2009, Hradec nad Moravicí, Czech Republic ; revised selected papers (95-104). https://doi.org/10.1007/978-3-642-10217-2_12

We prove three complexity results on vertex coloring problems restricted to Pk-free graphs, i.e., graphs that do not contain a path on k vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring rema... Read More about Three complexity results on coloring Pk-free graphs.

Partitioning graphs into connected parts (2009)
Journal Article
Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. Theoretical Computer Science, 410(47-49), 4834-4843. https://doi.org/10.1016/j.tcs.2009.06.028

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Pat... Read More about Partitioning graphs into connected parts.

Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs (2009)
Journal Article
Broersma, H., Paulusma, D., & Yoshimoto, K. (2009). Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs. Graphs and Combinatorics, 25(4), 427-460. https://doi.org/10.1007/s00373-009-0855-7

Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 4, then G has a 2-factor with at most (5n − 14)/18 compo... Read More about Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs.

On the core and f-nucleolus of flow games (2009)
Journal Article
Kern, W., & Paulusma, D. (2009). On the core and f-nucleolus of flow games. Mathematics of Operations Research, 34(4), 981-991. https://doi.org/10.1287/moor.1090.0405

Using the ellipsoid method, both Deng et al. [Deng, X., Q. Fang, X. Sun. 2006. Finding nucleolus of flow game. Proc. 17th ACM-SIAM Sympos. Discrete Algorithms. ACM Press, New York, 124–131] and Potters et al. [Potters, J., H. Reijnierse, A. Biswas. 2... Read More about On the core and f-nucleolus of flow games.

λ-backbone colorings along pairwise disjoint stars and matchings (2009)
Journal Article
Broersma, H., Fujisawa, J., Marchal, L., Paulusma, D., Salman, A., & Yoshimoto, K. (2009). λ-backbone colorings along pairwise disjoint stars and matchings. Discrete Mathematics, 309(18), 5596-5609. https://doi.org/10.1016/j.disc.2008.04.007

Given an integer λ≥2, a graph G=(V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring of (G,H) is a proper vertex coloring V→{1,2,…} of G, in which the colors assigned to adjacent vertices in H differ by at least λ. We study... Read More about λ-backbone colorings along pairwise disjoint stars and matchings.

Computing role assignments of chordal graphs (2009)
Presentation / Conference Contribution
Hof, P. V. '., Paulusma, D., & Rooij, J. V. (2009). Computing role assignments of chordal graphs. In Fundamentals of computation theory : 17th International Symposium, FCT 2009, Wrocław, Poland, September 2-4, 2009. Proceedings (193-204). https://doi.org/10.1007/978-3-642-03409-1_18

In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,...,k} called a role to each vertex of G such that any two vertices with the same role have the same sets of roles a... Read More about Computing role assignments of chordal graphs.

Partitioning graphs into connected parts (2009)
Presentation / Conference Contribution
Hof, P. V. '., Paulusma, D., & Woeginger, G. (2009). Partitioning graphs into connected parts. In Computer science - theory and applications (143-154). https://doi.org/10.1007/978-3-642-03351-3_15

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing pre-specified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Pa... Read More about Partitioning graphs into connected parts.

Covering graphs with few complete bipartite subgraphs (2009)
Journal Article
Fleischner, H., Mujuni, E., Paulusma, D., & Szeider, S. (2009). Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23), 2045-2053. https://doi.org/10.1016/j.tcs.2008.12.059

We consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the bicliq... Read More about Covering graphs with few complete bipartite subgraphs.

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number (2009)
Journal Article
Broersma, H., Marchal, L., Paulusma, D., & Salman, A. (2009). Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number. Discussiones Mathematicae. Graph Theory, 29(1), 143-162. https://doi.org/10.7151/dmgt.1437

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a l-backbone coloring for G and H is a proper vertex col... Read More about Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number.

Upper bounds and algorithms for parallel knock-out numbers (2009)
Journal Article
Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the... Read More about Upper bounds and algorithms for parallel knock-out numbers.

The computational complexity of graph contractions II: two tough polynomially solvable cases (2008)
Journal Article
Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions II: two tough polynomially solvable cases. Networks, 52(1), 32-56. https://doi.org/10.1002/net.20249

For a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This article is part II of our study on the computational complexity of the H-CONTRACTIBILITY problem. In the first ar... Read More about The computational complexity of graph contractions II: two tough polynomially solvable cases.

A new characterization of P6-free graphs (2008)
Presentation / Conference Contribution
Hof, P. V., & Paulusma, D. (2008). A new characterization of P6-free graphs. In X. Hu, & J. Wang (Eds.), Computing and combinatorics, 14th Annual International Conference, COCOON 2008, 27-29 June 2008 Dalian, China ; proceedings (415-424). https://doi.org/10.1007/978-3-540-69733-6_41

We study P 6-free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph G is P 6-free if and only if each connected induced subgraph of G on more than one vert... Read More about A new characterization of P6-free graphs.

The computational complexity of graph contractions I: polynomially solvable and NP-complete cases (2008)
Journal Article
Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. Networks, 51(3), 178-189. https://doi.org/10.1002/net.20214

For a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This paper is part I of our study on the computational complexity of the H-CONTRACTIBILITY problem. We continue a line... Read More about The computational complexity of graph contractions I: polynomially solvable and NP-complete cases.

Locally constrained graph homomorphisms and equitable partitions (2008)
Journal Article
Fiala, J., Paulusma, D., & Telle, J. (2008). Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics, 29(4), 850-880. https://doi.org/10.1016/j.ejc.2007.11.006

We explore the connection between locally constrained graph homomorphisms and degree matrices arising from an equitable partition of a graph. We provide several equivalent characterizations of degree matrices. As a consequence we can efficiently chec... Read More about Locally constrained graph homomorphisms and equitable partitions.

Relative length of longest paths and longest cycles in triangle-free graphs (2008)
Journal Article
Paulusma, D., & Yoshimoto, K. (2008). Relative length of longest paths and longest cycles in triangle-free graphs. Discrete Mathematics, 308(7), 1222-1229. https://doi.org/10.1016/j.disc.2007.03.070

In this paper, we study triangle-free graphs. Let G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ4(G)|V(G)|+2. We first show that either for any path P in G there exists a cycle C such that |VPVC|1, or G is isomorph... Read More about Relative length of longest paths and longest cycles in triangle-free graphs.

The computational complexity of the parallel knock-out problem (2008)
Journal Article
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2008). The computational complexity of the parallel knock-out problem. Theoretical Computer Science, 393(1-3), 182-195. https://doi.org/10.1016/j.tcs.2007.11.021

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.

A new algorithm for on-line coloring bipartite graphs (2008)
Journal Article
Broersma, H., Capponi, A., & Paulusma, D. (2008). A new algorithm for on-line coloring bipartite graphs. SIAM Journal on Discrete Mathematics, 22(1), 72-91. https://doi.org/10.1137/060668675

We first show that for any bipartite graph $H$ with at most five vertices there exists an on-line competitive algorithm for the class of $H$-free bipartite graphs. We then analyze the performance of an on-line algorithm for coloring bipartite graphs... Read More about A new algorithm for on-line coloring bipartite graphs.

Computing sharp 2-factors in claw-free graphs (2008)
Presentation / Conference Contribution
Broersma, H. J., & Paulusma, D. (2008). Computing sharp 2-factors in claw-free graphs. In E. Ochmanski, & J. Tyszkiewicz (Eds.), Mathematical foundations of computer science 2008, 33rd International Symposium, MFCS 2008, 25-29 August 2008, Toru´n, Poland ; proceedings (193-204). https://doi.org/10.1007/978-3-540-85238-4_15

In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this... Read More about Computing sharp 2-factors in claw-free graphs.

Comparing universal covers in polynomial time (2008)
Presentation / Conference Contribution
Fiala, J., & Paulusma, D. (2008). Comparing universal covers in polynomial time. In E. A. Hirsch, A. A. Razboro, A. Semenov, & A. Slissenko (Eds.), Computer science – theory and applications, Third International Computer Science Symposium in Russia, CSR 2008, 7-12 June 2008, Moscow, Russia ; proceedings (158-167). https://doi.org/10.1007/978-3-540-79709-8_18

The universal cover T G of a connected graph G is the unique (possible infinite) tree covering G, i.e., that allows a locally bijective homomorphism from T G to G. Universal covers have major applications in the area of distributed computing. It is w... Read More about Comparing universal covers in polynomial time.

On components of 2-factors in claw-free graphs (2007)
Presentation / Conference Contribution
Broersma, H., Paulusma, D., & Yoshimoto, K. (2007). On components of 2-factors in claw-free graphs. Electronic Notes in Discrete Mathematics, 29, 289-293. https://doi.org/10.1016/j.endm.2007.07.050

For a non-hamiltonian claw-free graph G with order n and minimum degree δ we show the following. If δ=4, then G has a 2-factor with at most (5n−14)/18 components, unless G belongs to a finite class of exceptional graphs. If δ⩾5, then G has a 2-factor... Read More about On components of 2-factors in claw-free graphs.

Cycles through specified vertices in triangle-free graphs (2007)
Journal Article
Paulusma, D., & Yoshimito, K. (2007). Cycles through specified vertices in triangle-free graphs. Discussiones Mathematicae. Graph Theory, 27(1), 179-191. https://doi.org/10.7151/dmgt.1354

Let G be a triangle-free graph with δ(G) ≥ 2 and σ4(G) ≥ |V(G)|+2. Let S ⊂ V(G) consist of less than σ4/4+ 1 vertices. We prove the following. If all vertices of S have degree at least three, then there exists a cycle C containing S. Both the upper b... Read More about Cycles through specified vertices in triangle-free graphs.

The computational complexity of the parallel knock-out problem (2006)
Presentation / Conference Contribution
Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006). The computational complexity of the parallel knock-out problem. In LATIN 2006 : theoretical informatics: : 7th Latin American symposium, Valdivia, Chile, March 20-24, 2006 : proceedings (250-261). https://doi.org/10.1007/11682462_26

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for... Read More about The computational complexity of the parallel knock-out problem.

A complete complexity classification of the role assignment problem (2005)
Journal Article
Fiala, J., & Paulusma, D. (2005). A complete complexity classification of the role assignment problem. Theoretical Computer Science, 349(1), 67-81. https://doi.org/10.1016/j.tcs.2005.09.029

In social network theory a society is often represented by a simple graph G, where vertices stand for individuals and edges represent relationships between those individuals. The description of the social network is tried to be simplified by assignin... Read More about A complete complexity classification of the role assignment problem.

Matrix and graph orders derived from locally constrained graph homomorphisms (2005)
Presentation / Conference Contribution
Fiala, J., Paulusma, D., & Telle, J. A. (2005). Matrix and graph orders derived from locally constrained graph homomorphisms. In J. Jedrzejowicz, & A. Szepietowski (Eds.), Mathematical foundations of computer science 2005 : 30th International Symposium, MFCS 2005, Gdansk, Poland, 29 August 29-2September 2005 ; proceedings (340-351). https://doi.org/10.1007/11549345_30

We consider three types of locally constrained graph homomorphisms: bijective, injective and surjective. We show that the three orders imposed on graphs by existence of these three types of homomorphisms are partial orders. We extend the well-known c... Read More about Matrix and graph orders derived from locally constrained graph homomorphisms.

The computational complexity of the elimination problem in generalized sports competitions (2004)
Journal Article
Kern, W., & Paulusma, D. (2004). The computational complexity of the elimination problem in generalized sports competitions. Discrete Optimization, 1(2), 205-214. https://doi.org/10.1016/j.disopt.2003.12.003

Consider a sports competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to... Read More about The computational complexity of the elimination problem in generalized sports competitions.

Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture (2004)
Presentation / Conference Contribution
Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004). Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture. In 2004 IEEE International Conference on Field-Programmable Technology: Proceedings: December 6-8, 2004, the University of Queensland, Brisbane, Australia (421-424). https://doi.org/10.1109/fpt.2004.1393315

This work evaluates an algorithm that maps a number of communicating processes to a heterogeneous tiled system on chip (SoC) architecture at run-time. The mapping algorithm minimizes the total amount of energy consumption, while still providing an ad... Read More about Run-time mapping of applications to a heterogeneous reconfigurable tiled system on chip architecture.

Run-time assignment of tasks to multiple heterogeneous processors (2004)
Presentation / Conference Contribution
Smit, L., Smit, G., Hurink, J., Broersma, H., Paulusma, D., & Wolkotte, P. (2004). Run-time assignment of tasks to multiple heterogeneous processors.

This paper describes the implementation and evaluation of an algorithm that maps a number of communicating processes to a heterogeneous tiled System on Chip (SoC) architecture at run-time. The mapping algorithm minimizes the total amount of energy co... Read More about Run-time assignment of tasks to multiple heterogeneous processors.

Matching games : the least core and the nucleolus (2003)
Journal Article
Kern, W., & Paulusma, D. (2003). Matching games : the least core and the nucleolus. Mathematics of Operations Research, 28(2), 294-308. https://doi.org/10.1287/moor.28.2.294.14477

A matching game is a cooperative game defined by a graph G = (V, E). The player set is V and the value of a coalition S # V is defined as the size of a maximum matching in the subgraph induced by S. We show that the nucleolus of such games can be com... Read More about Matching games : the least core and the nucleolus.

Two extensions of the Shapley value for cooperative games (2001)
Journal Article
Driessen, T., & Paulusma, D. (2001). Two extensions of the Shapley value for cooperative games. Mathematical Methods of Operations Research, 53(1), 35-49. https://doi.org/10.1007/s001860000099

Two extensions of the Shapley value are given. First we consider a probabilistic framework in which certain consistent allocation rules such as the Shapley value are characterized. The second generalization of the Shapley value is an extension to the... Read More about Two extensions of the Shapley value for cooperative games.

The new FIFA rules are hard: complexity aspects of sports competitions (2001)
Journal Article
Kern, W., & Paulusma, D. (2001). The new FIFA rules are hard: complexity aspects of sports competitions. Discrete Applied Mathematics, 108(3), 317-323. https://doi.org/10.1016/s0166-218x%2800%2900241-9

Consider a soccer competition among various teams playing against each other in pairs (matches) according to a previously determined schedule. At some stage of the competition one may ask whether a particular team still has a (theoretical) chance to... Read More about The new FIFA rules are hard: complexity aspects of sports competitions.

Note on the computational complexity of least core concepts for min-cost spanning tree games (2000)
Journal Article
Faigle, U., Kern, W., & Paulusma, D. (2000). Note on the computational complexity of least core concepts for min-cost spanning tree games. Mathematical Methods of Operations Research, 52(1), 23-38. https://doi.org/10.1007/s001860000059

Various least core concepts including the classical least core of cooperative games are discussed. By a reduction from minimum cover problems, we prove that computing an element in these least cores is in general NP-hard for minimum cost spanning tre... Read More about Note on the computational complexity of least core concepts for min-cost spanning tree games.