Konrad K. Dabrowski

AAAI Conference 2024 Conference Paper

Learning Small Decision Trees for Data of Low Rank-Width

• Konrad K. Dabrowski
• Eduard Eiben
• Sebastian Ordyniak
• Giacomo Paesani
• Stefan Szeider

We consider the NP-hard problem of finding a smallest decision tree representing a classification instance in terms of a partially defined Boolean function. Small decision trees are desirable to provide an interpretable model for the given data. We show that the problem is fixed-parameter tractable when parameterized by the rank-width of the incidence graph of the given classification instance. Our algorithm proceeds by dynamic programming using an NLC decomposition obtained from a rank-width decomposition. The key to the algorithm is a succinct representation of partial solutions. This allows us to limit the space and time requirements for each dynamic programming step in terms of the parameter.

SODA Conference 2023 Conference Paper

Almost Consistent Systems of Linear Equations

• Konrad K. Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov
• Magnus Wahlström

AIJ Journal 2023 Journal Article

Solving infinite-domain CSPs using the patchwork property

• Konrad K. Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov

The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau (2013) [14] and Huang et al. (2013) [47] proved that CSP(Γ) can be solved in n f ( w ) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Γ. We improve this bound to f ( w ) ⋅ n O ( 1 ), where the function f only depends on the language Γ, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau's algorithm but not by ours, and we begin investigating ways of generalising our results to larger families of languages. We also analyse our algorithm with respect to its running time and show that it is optimal (under the Exponential Time Hypothesis) for certain languages such as Allen's Interval Algebra.

AAAI Conference 2022 Conference Paper

Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach

• Konrad K. Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov

The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AI. We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a maximally large consistent subset of data is NP-hard. In practical instances, it is reasonable to assume that the amount of erroneous data is small. We therefore parameterize by the number of constraints that need to be removed to achieve consistency. Using tools from parameterized complexity we design fixed-parameter tractable algorithms for two large fragments of the STP. Our main algorithmic results employ reductions to the Directed Subset Feedback Arc Set problem and iterative compression combined with an efficient algorithm for the Edge Multicut problem. We complement our algorithmic results with hardness results that rule out fixed-parameter tractable algorithms for all remaining non-trivial fragments of the STP (under standard complexity-theoretic assumptions). Together, our results give a full classification of the classical and parameterized complexity of the problem.

KR Conference 2020 Conference Paper

Fine-Grained Complexity of Temporal Problems

• Konrad K. Dabrowski
• Peter Jonsson
• Sebastian Ordyniak
• George Osipov

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 applications. It is known that deciding satisfiability of disjunctive STPs is NP-hard, while the fine-grained complexity of such problems is virtually unexplored. We present novel algorithms that exploit structural properties of the solution space and prove, assuming the Exponential-Time Hypothesis, that their worst-case time complexity is close to optimal. Among other things, we make progress towards resolving a long-open question concerning whether Allen's interval algebra can be solved in single-exponential time, by giving a 2^{O(nloglog(n))} algorithm for the special case of unit-length intervals.

TCS Journal 2018 Journal Article

On the (parameterized) complexity of recognizing well-covered (r,ℓ)-graph

• Sancrey Rodrigues Alves
• Konrad K. Dabrowski
• Luerbio Faria
• Sulamita Klein
• Ignasi Sau
• Uéverton S. Souza

An ( r, ℓ ) -partition of a graph G is a partition of its vertex set into r independent sets and ℓ cliques. A graph is ( r, ℓ ) if it admits an ( r, ℓ ) -partition. A graph is well-covered if every maximal independent set is also maximum. A graph is ( r, ℓ ) -well-covered if it is both ( r, ℓ ) and well-covered. In this paper we consider two different decision problems. In the ( r, ℓ ) -Well-Covered Graph problem ( ( r, ℓ ) wc-g for short), we are given a graph G, and the question is whether G is an ( r, ℓ ) -well-covered graph. In the Well-Covered ( r, ℓ ) -Graph problem (wc- ( r, ℓ ) g for short), we are given an ( r, ℓ ) -graph G together with an ( r, ℓ ) -partition, and the question is whether G is well-covered. This generates two infinite families of problems, for any fixed non-negative integers r and ℓ, which we classify as being P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases wc- ( r, 0 ) g for r ≥ 3 remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size α of a maximum independent set of the input graph, its neighborhood diversity, its clique-width, or the number ℓ of cliques in an ( r, ℓ ) -partition. In particular, we show that the parameterized problem of determining whether every maximal independent set of an input graph G has cardinality equal to k can be reduced to the wc- ( 0, ℓ ) g problem parameterized by ℓ. In addition, we prove that both problems are coW[2]-hard but can be solved in XP-time.

MFCS Conference 2018 Conference Paper

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

• Konrad K. Dabrowski
• Matthew Johnson 0002
• Giacomo Paesani
• Daniël Paulusma
• Viktor Zamaraev

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 we require that they are independent; that is, what is the price of independence? If G has a vertex cover, feedback vertex set or odd cycle transversal that is an independent set, then we let, respectively, ivc(G), ifvs(G) or ioct(G) denote the minimum size of such a set. We investigate for which graphs H the values of ivc(G), ifvs(G) and ioct(G) are bounded in terms of vc(G), fvs(G) and oct(G), respectively, when the graph G belongs to the class of H-free graphs. We find complete classifications for vertex cover and feedback vertex set and an almost complete classification for odd cycle transversal (subject to three non-equivalent open cases).

MFCS Conference 2017 Conference Paper

Clique-Width for Graph Classes Closed under Complementation

• Alexandre Blanché
• Konrad K. Dabrowski
• Matthew Johnson 0002
• Vadim V. Lozin
• Daniël Paulusma
• Viktor Zamaraev

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 into the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the |H|=1 case by classifying the boundedness of clique-width for every set H of self-complementary graphs. We then completely settle the |H|=2 case. In particular, we determine one new class of (H1, complement of H1)-free graphs of bounded clique-width (as a side effect, this leaves only six classes of (H1, H2)-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the |H|=2 case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for a set F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for ({H1, complement of H1} + F)-free graphs coincides with the one for the |H|=2 case if and only if F does not include the bull (the only non-empty self-complementary graphs on fewer than five vertices are P_1 and P_4, and P_4-free graphs have clique-width at most 2). Finally, we discuss the consequences of our results for COLOURING.

MFCS Conference 2017 Conference Paper

Recognizing Graphs Close to Bipartite Graphs

• Marthe Bonamy
• Konrad K. Dabrowski
• Carl Feghali
• Matthew Johnson 0002
• Daniël Paulusma

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-degenerate graphs. The problem is known to be polynomial-time solvable if k=0 (bipartite graphs) and NP-complete if k=1 (near-bipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomial-time solvability for graphs of diameter 2. We show that recognizing near-bipartite graphs of diameter 3 is NP-complete resolving their open problem. To answer another open problem, we consider graphs of maximum degree D on n vertices. We show how to find A and B in O(n) time for k=1 and D=3, and in O(n^2) time for k >= 2 and D >= 4. These results also provide an algorithmic version of a result of Catlin [JCTB, 1979] and enable us to complete the complexity classification of another problem: finding a path in the vertex colouring reconfiguration graph between two given k-colourings of a graph of bounded maximum degree.

TCS Journal 2014 Journal Article

Colouring of graphs with Ramsey-type forbidden subgraphs

• Konrad K. Dabrowski
• Petr A. Golovach
• Daniel Paulusma

A colouring of a graph G = ( V, E ) is a mapping c: V → { 1, 2, … } such that c ( u ) ≠ c ( v ) if u v ∈ 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 contains no induced subgraph isomorphic to any graph in some family H, then it is called H -free. The complexity of Colouring for H -free graphs with | H | = 1 has been completely classified. When | H | = 2, the classification is still wide open, although many partial results are known. We continue this line of research and forbid induced subgraphs { H 1, H 2 }, where we allow H 1 to have a single edge and H 2 to have a single non-edge. Instead of showing only polynomial-time solvability, we prove that Colouring on such graphs is fixed-parameter tractable when parameterized by | H 1 | + | H 2 |. As a by-product, we obtain the same result both for the problem of determining a maximum independent set and for the problem of determining a maximum clique.

TCS Journal 2013 Journal Article

New results on maximum induced matchings in bipartite graphs and beyond

• Konrad K. Dabrowski
• Marc Demange
• Vadim V. Lozin

The maximum induced matching problem is known to be APX-hard in the class of bipartite graphs. Moreover, the problem is also intractable in this class from a parameterized point of view, i. e. it is W[1]-hard. In this paper, we reveal several classes of bipartite (and more general) graphs for which the problem admits fixed-parameter tractable algorithms. We also study the computational complexity of the problem for regular bipartite graphs and prove that the problem remains APX-hard even under this restriction. On the other hand, we show that for hypercubes (a proper subclass of regular bipartite graphs) the problem admits a simple solution.