Skip to main content

Research Repository

Advanced Search

Outputs (53)

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

Disjunctive Temporal Problems under Structural Restrictions (2021)
Presentation / Conference Contribution
Dabrowski, K. K., Jonsson, P., Ordyniak, S., & Osipov, G. (2021, February). Disjunctive Temporal Problems under Structural Restrictions. Presented at 35th AAAI Conference on Artificial Intelligence (AAAI), Vancouver, Canada

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

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.

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, September). Fine-Grained Complexity of Temporal Problems. Presented at KR 2020, Rhodes, Greece

Expressive 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, England

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.

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.

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.

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.