Skip to main content

Research Repository

Advanced Search

Outputs (52)

Disjunctive Temporal Problems under Structural Restrictions (2021)
Conference Proceeding
Dabrowski, K. K., Jonsson, P., Ordyniak, S., & Osipov, G. (2021). Disjunctive Temporal Problems under Structural Restrictions. . https://doi.org/10.1609/aaai.v35i5.16489

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)
Conference Proceeding
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/29

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

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.

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.