**Solving Infinite-Domain CSPs Using the Patchwork Property**
(2023)

Presentation / Conference Contribution

Dabrowski, K. K., Jonsson, P., Ordyniak, S., & Osipov, G. (2021, December). Solving Infinite-Domain CSPs Using the Patchwork Property. Presented at 35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada

# All Outputs (27)

Disjunctive Temporal Problems under Structural Restrictions(2021)

Presentation / Conference Contribution

Dabrowski, K. K., Jonsson, P., Ordyniak, S., & Osipov, G. (2021). Disjunctive Temporal Problems under Structural Restrictions. . https://doi.org/10.1609/aaai.v35i5.16489The disjunctive temporal problem (DTP) is an expressive temporal formalism that extends Dechter et al.’s simple temporal problem. The DTP is well studied in the literature and has many important applications. It is known that deciding satisfiability... Read More about Disjunctive Temporal Problems under Structural Restrictions.

Fine-Grained Complexity of Temporal Problems(2020)

Presentation / Conference Contribution

Dabrowski, K., Jonsson, P., Ordyniak, S., Osipov, G., Calvanese, D., Erdem, E., & Thielscher, M. (2020). Fine-Grained Complexity of Temporal Problems. . https://doi.org/10.24963/kr.2020/29Expressive temporal reasoning formalisms are essential for AI. One family of such formalisms consists of disjunctive extensions of the simple temporal problem (STP). Such extensions are well studied in the literature and they have many important appl... Read More about Fine-Grained Complexity of Temporal Problems.

Clique-Width: Harnessing the Power of Atoms(2020)

Presentation / Conference Contribution

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

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.

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy(2019)

Presentation / Conference Contribution

Bonamy, M., Dabrowski, K. K., Johnson, M., & Paulusma, D. (2019, December). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Presented at WADS 2019, Edmonton, CanadaWe 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

Computing small pivot-minors(2018)

Presentation / Conference Contribution

Dabrowski, K. K., Dross, F., Jeong, J., Kanté, M. M., Kwon, O., Oum, S., & Paulusma, D. (2018, June). Computing small pivot-minors. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, GermanyA 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.

On the price of independence for vertex cover, feedback vertex set and odd cycle transversal(2018)

Presentation / Conference Contribution

Dabrowski, K. K., Johnson, M., Paesani, G., Paulusma, D., & Zamaraev, V. (2018, August). On the price of independence for vertex cover, feedback vertex set and odd cycle transversal. Presented at 43nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UKLet 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.73Clique-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.

Clique-width and well-quasi ordering of triangle-free graph classes(2017)

Presentation / Conference Contribution

Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2017, June). Clique-width and well-quasi ordering of triangle-free graph classes. Presented at WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, Eindhoven, The NetherlandsDaligault, 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.

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.053Testing 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.

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.70We 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.

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.16The 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.

On the (Parameterized) Complexity of Recognizing Well-covered (r,l)-graphs(2016)

Presentation / Conference Contribution

Alves, S. R., Dabrowski, K. K., Faria, L., Klein, S., Sau, I., dos Santos Souza, U., Chan, T.-H. H., Li, M., & Wang, L. (2016, December). On the (Parameterized) Complexity of Recognizing Well-covered (r,l)-graphs. Presented at 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), Hong Kong, ChinaAn (r,ℓ)(r,ℓ)-partition of a graph G is a partition of its vertex set into r independent sets and ℓℓ cliques. A graph is (r,ℓ)(r,ℓ) if it admits an (r,ℓ)(r,ℓ)-partition. A graph is well-covered if every maximal independent set is also maximum. A grap... Read More about On the (Parameterized) Complexity of Recognizing Well-covered (r,l)-graphs.

Well-quasi-ordering versus clique-width: new results on bigenic classes(2016)

Presentation / Conference Contribution

Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016, August). Well-quasi-ordering versus clique-width: new results on bigenic classes. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, FinlandDaligault, 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.

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.16The 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.

Filling the complexity gaps for colouring planar and bounded degree graphs(2016)

Presentation / Conference Contribution

Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2015, October). Filling the complexity gaps for colouring planar and bounded degree graphs. Presented at 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), Verona, ItalyWe 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.069A 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.