Source author record

Konrad K. Dabrowski

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

13works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Almost Consistent Systems of Linear Equations

Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains - a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers, and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests.

preprint2022arXiv

An Algorithmic Framework for Locally Constrained Homomorphisms

A homomorphism $f$ from a guest graph $G$ to a host graph $H$ is locally bijective, injective or surjective if for every $u\in V(G)$ , the restriction of $f$ to the neighbourhood of $u$ is bijective, injective or surjective, respectively. The corresponding decision problems, LBHOM, LIHOM and LSHOM, are well studied both on general graphs and on special graph classes. Apart from complexity results when the problems are parameterized by the treewidth and maximum degree of the guest graph, the three problems still lack a thorough study of their parameterized complexity. This paper fills this gap: we prove a number of new FPT, W[1]-hard and para-NP-complete results by considering a hierarchy of parameters of the guest graph $G$ . For our FPT results, we do this through the development of a new algorithmic framework that involves a general ILP model. To illustrate the applicability of the new framework, we also use it to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms.

preprint2016arXiv

Colouring Diamond-free Graphs

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 $(\mbox{diamond},H)$-free graphs. Our proof is based on combining known results together with proving that the clique-width is bounded for $(\mbox{diamond}, P_1+2P_2)$-free graphs. Our technique for handling this case is to reduce the graph under consideration to a $k$ -partite graph that has a very specific decomposition. As a by-product of this general technique we are also able to prove boundedness of clique-width for four other new classes of $(H_1,H_2)$ -free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of clique-width of $(H_1,H_2)$ -free graphs, and our five new classes of bounded clique-width reduce the number of open cases from 13 to 8.

preprint2016arXiv

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

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 many forbidden induced subgraphs. However, in the case of finitely many forbidden induced subgraphs the question remains open and we conjecture that in this case the answer is positive. The conjecture is known to hold for classes of graphs defined by a single forbidden induced subgraph $H$ , as such graphs are well-quasi-ordered and are of bounded clique-width if and only if $H$ is an induced subgraph of $P_4$ . For bigenic classes of graphs, i.e. ones defined by two forbidden induced subgraphs, there are several open cases in both classifications. In the present paper we obtain a number of new results on well-quasi-orderability of bigenic classes, each of which supports the conjecture.

preprint2015arXiv

Bounding Clique-Width via Perfect Graphs

Given two graphs $H_1$ and $H_2$ , a graph $G$ is $(H_1,H_2)$ -free if it contains no subgraph isomorphic to $H_1$ or $H_2$ . We continue a recent study into the clique-width of $(H_1,H_2)$ -free graphs and present three new classes of $(H_1,H_2)$ -free graphs of bounded clique-width and one of unbounded clique-width. The four new graph classes have in common that one of their two forbidden induced subgraphs is the diamond (the graph obtained from a clique on four vertices by deleting one edge). To prove boundedness of clique-width for the first three cases we develop a technique based on bounding clique covering number in combination with reduction to subclasses of perfect graphs. We extend our proof of unboundedness for the fourth case to show that Graph Isomorphism is Graph Isomorphism-complete on the same graph class. We also show the implications of our results for the computational complexity of the Colouring problem restricted to $(H_1,H_2)$ -free graphs.

preprint2015arXiv

Bounding the Clique-Width of $H$ -free Chordal Graphs

A graph is $H$ -free if it has no induced subgraph isomorphic to $H$ . Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le and Mosca erroneously claimed that the gem and the co-gem are the only two 1-vertex $P_4$ -extensions $H$ for which the class of $H$ -free chordal graphs has bounded clique-width. In fact we prove that bull-free chordal and co-chair-free chordal graphs have clique-width at most 3 and 4, respectively. In particular, we find four new classes of $H$ -free chordal graphs of bounded clique-width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs $H$ for which the class of $H$ -free chordal graphs has bounded clique-width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of $(2P_1+P_3,K_4)$ -free graphs has bounded clique-width via a reduction to $K_4$ -free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique-width of $H$ -free weakly chordal graphs.

preprint2015arXiv

Bounding the Clique-Width of $H$ -free Split Graphs

A 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 result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs $H$ for which the class of $H$ -free split graphs has bounded clique-width.

preprint2015arXiv

Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs

If a graph has no induced subgraph isomorphic to any graph in a finite family $\{H_1,\ldots,H_p\}$ , it is said to be $(H_1,\ldots,H_p)$ -free. The class of $H$ -free graphs has bounded clique-width if and only if $H$ is an induced subgraph of the 4-vertex path $P_4$ . We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs $H_1$ and $H_2$ . Prior to our study it was not known whether the number of open cases was finite. We provide a positive answer to this question. To reduce the number of open cases we determine new graph classes of bounded clique-width and new graph classes of unbounded clique-width. For obtaining the latter results we first present a new, generic construction for graph classes of unbounded clique-width. Our results settle the boundedness or unboundedness of the clique-width of the class of $(H_1,H_2)$ -free graphs (i) for all pairs $(H_1,H_2)$ , both of which are connected, except two non-equivalent cases, and (ii) for all pairs $(H_1,H_2)$ , at least one of which is not connected, except 11 non-equivalent cases. We also consider classes characterized by forbidding a finite family of graphs $\{H_1,\ldots,H_p\}$ as subgraphs, minors and topological minors, respectively, and completely determine which of these classes have bounded clique-width. Finally, we show algorithmic consequences of our results for the graph colour

preprint2015arXiv

Editing to a Planar Graph of Given Degrees

We consider the following graph modification problem. Let the input consist of a graph $G=(V,E)$ , a weight function $w\colon V\cup E\rightarrow \mathbb{N}$ , a cost function $c\colon V\cup E\rightarrow \mathbb{N}$ and a degree function $δ\colon V\rightarrow \mathbb{N}_0$ , together with three integers $k_v, k_e$ and $C$ . The question is whether we can delete a set of vertices of total weight at most $k_v$ and a set of edges of total weight at most $k_e$ so that the total cost of the deleted elements is at most $C$ and every non-deleted vertex $v$ has degree $δ(v)$ in the resulting graph $G'$ . We also consider the variant in which $G'$ must be connected. Both problems are known to be NP-complete and W[1]-hard when parameterized by $k_v+k_e$ . We prove that, when restricted to planar graphs, they stay NP-complete but have polynomial kernels when parameterized by $k_v+k_e$ .

preprint2014arXiv

Classifying the Clique-Width of $H$ -Free Bipartite Graphs

Let $G$ be a bipartite graph, and let $H$ be a bipartite graph with a fixed bipartition $(B_H,W_H)$ . We consider three different, natural ways of forbidding $H$ as an induced subgraph in $G$ . First, $G$ is $H$ -free if it does not contain $H$ as an induced subgraph. Second, $G$ is strongly $H$ -free if $G$ is $H$ -free or else has no bipartition $(B_G,W_G)$ with $B_H\subseteq B_G$ and $W_H\subseteq W_G$ . Third, $G$ is weakly $H$ -free if $G$ is $H$ -free or else has at least one bipartition $(B_G,W_G)$ with $B_H\not\subseteq B_G$ or $W_H\not\subseteq W_G$ . Lozin and Volz characterized all bipartite graphs $H$ for which the class of strongly $H$ -free bipartite graphs has bounded clique-width. We extend their result by giving complete classifications for the other two variants of $H$ -freeness.

preprint2014arXiv

Combinatorics and algorithms for augmenting graphs

The notion of augmenting graphs generalizes Berge's idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) problem. Recently, the augmenting graph approach has been successfully applied to solve MIS in various other special cases. However, our knowledge of augmenting graphs is still very limited, and we do not even know what the minimal infinite classes of augmenting graphs are. In the present paper, we find an answer to this question and apply it to extend the area of polynomial-time solvability of the maximum independent set problem.

preprint2014arXiv

Editing to Eulerian Graphs

We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let $ea$ , $ed$ and $vd$ denote the operations edge addition, edge deletion and vertex deletion respectively. For any $S\subseteq \{ea,ed,vd\}$ , we define Connected Degree Parity Editing $(S)$ (CDPE( $S$ )) to be the problem that takes as input a graph $G$ , an integer $k$ and a function $δ\colon V(G)\rightarrow\{0,1\}$ , and asks whether $G$ can be modified into a connected graph $H$ with $d_{H}(v)\equivδ(v)~(\bmod~2)$ for each $v\in V(H)$ , using at most $k$ operations from $S$ . We prove that 1. if $S=\{ea\}$ or $S=\{ea,ed\}$ , then CDPE( $S$ ) can be solved in polynomial time; 2. if $\{vd\} \subseteq S\subseteq \{ea,ed,vd\}$ , then CDPE( $S$ ) is NP-complete and W[1]-hard when parameterized by $k$ , even if $δ\equiv 0$ . Together with known results by Cai and Yang and by Cygan, Marx, Pilipczuk, Pilipczuk and Schlotter, our results completely classify the classical and parameterized complexity of the CDPE( $S$ ) problem for all $S\subseteq \{ea,ed,vd\}$ . We obtain the same classification for a natural variant of the CDPE( $S$ ) problem on directed graphs, where the target is a weakly connected digraph in which the difference between the in- and out-degree of every vertex equals a prescribed value. As an important implication of our results, we obtain polynomial-time algorithms for the Eulerian Editing problem and its directed variant.

preprint2013arXiv

Playing with parameters: structural parameterization in graphs

When considering a graph problem from a parameterized point of view, the parameter chosen is often the size of an optimal solution of this problem (the "standard" parameter). A natural subject for investigation is what happens when we parameterize such a problem by various other parameters, some of which may be the values of optimal solutions to different problems. Such research is known as parameterized ecology. In this paper, we investigate seven natural vertex problems, along with their respective parameters: the size of a maximum independent set, the size of a minimum vertex cover, the size of a maximum clique, the chromatic number, the size of a minimum dominating set, the size of a minimum independent dominating set and the size of a minimum feedback vertex set. We study the parameterized complexity of each of these problems with respect to the standard parameter of the others.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Konrad K. Dabrowski

Research overview

Is this your work?

13 publications

Almost Consistent Systems of Linear Equations

An Algorithmic Framework for Locally Constrained Homomorphisms

Colouring Diamond-free Graphs

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

Bounding Clique-Width via Perfect Graphs

Bounding the Clique-Width of $H$ -free Chordal Graphs

Bounding the Clique-Width of $H$ -free Split Graphs

Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs

Editing to a Planar Graph of Given Degrees

Classifying the Clique-Width of $H$ -Free Bipartite Graphs

Combinatorics and algorithms for augmenting graphs

Editing to Eulerian Graphs

Playing with parameters: structural parameterization in graphs

See the researcher in context

Building this map preview

Konrad K. Dabrowski

Research overview

Is this your work?

13 publications

Almost Consistent Systems of Linear Equations

An Algorithmic Framework for Locally Constrained Homomorphisms

Colouring Diamond-free Graphs

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

Bounding Clique-Width via Perfect Graphs

Bounding the Clique-Width of HHH-free Chordal Graphs

Bounding the Clique-Width of HHH-free Split Graphs

Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs

Editing to a Planar Graph of Given Degrees

Classifying the Clique-Width of HHH-Free Bipartite Graphs

Combinatorics and algorithms for augmenting graphs

Editing to Eulerian Graphs

Playing with parameters: structural parameterization in graphs

See the researcher in context

Building this map preview

Bounding the Clique-Width of $H$ -free Chordal Graphs

Bounding the Clique-Width of $H$ -free Split Graphs

Classifying the Clique-Width of $H$ -Free Bipartite Graphs