All Outputs (153)

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

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

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

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

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

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

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.

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.

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.

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.

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)
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.

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.

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.