Daniël Paulusma

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.

Classifying Subset Feedback Vertex Set for $H$ -Free Graphs

In the Feedback Vertex Set problem, we aim to find a small set $S$ of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires $S$ to intersect only those cycles that include a vertex of some specified set $T$ . We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex $u$ has weight $w(u)>0$ and we ask that $S$ has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for $H$ -free graphs, that is, graphs that do not contain a graph $H$ as an induced subgraph.

Feedback Vertex Set and Even Cycle Transversal for H-Free Graphs: Finding Large Block Graphs

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on $H$ -free graphs, that is, graphs that do not contain some fixed graph $H$ as an induced subgraph. In particular, we prove that for every $s\geq 1$ , both problems are polynomial-time solvable for $sP_3$ -free graphs and $(sP_1+P_5)$ -free graphs; here, the graph $sP_3$ denotes the disjoint union of $s$ paths on three vertices and the graph $sP_1+P_5$ denotes the disjoint union of $s$ isolated vertices and a path on five vertices. Our new results for Feedback Vertex Set extend all known polynomial-time results for Feedback Vertex Set on $H$ -free graphs, namely for $sP_2$ -free graphs [Chiarelli et al., TCS 2018], $(sP_1+P_3)$ -free graphs [Dabrowski et al., Algorithmica 2020] and $P_5$ -free graphs [Abrishami et al., SODA 2021]. Together, the new results also show that both problems exhibit the same behaviour on $H$ -free graphs (subject to some open cases). This is in part due to a new general algorithm we design for finding in a ( $sP_3)$ -free or $(sP_1+P_5)$ -free graph $G$ a largest induced subgraph whose blocks belong to some finite class ${\cal C}$ of graphs. We also compare our results with the state-of-the-art results for the Odd Cycle Transversal problem, which is known to behave differently on $H$ -free graphs.

Finding Matching Cuts in $H$ -Free Graphs

The NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to $H$ -free graphs, that is, graphs that do not contain some fixed graph $H$ as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on $H$ -free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant $r>0$ such that the first variant is NP-complete for $P_r$ -free graphs. This addresses a question of Bouquet and Picouleau (arXiv, 2020). For all three problems, we give state-of-the-art summaries of their computational complexity for $H$ -free graphs.

Induced Disjoint Paths and Connected Subgraphs for $H$ -Free Graphs

Paths $P_1,\ldots, P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices. The Induced Disjoint Paths problem is to decide if a graph $G$ with $k$ pairs of specified vertices $(s_i,t_i)$ contains $k$ mutually induced paths $P_i$ such that each $P_i$ starts from $s_i$ and ends at $t_i$ . This is a classical graph problem that is NP-complete even for $k=2$ . We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$ -Free Graphs

For a connected graph $G=(V,E)$ , a matching $M\subseteq E$ is a matching cut of $G$ if $G-M$ is disconnected. It is known that for an integer $d$ , the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most $d$ if $d\leq 2$ and NP-complete if $d\geq 3$ . We prove the same dichotomy for graphs of bounded radius. For a graph $H$ , a graph is $H$ -free if it does not contain $H$ as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for $P_6$ -free graphs, extending a recent result of Feghali for $P_5$ -free graphs. We then extend our result to hold even for $(sP_3+P_6)$ -free graphs for every $s\geq 0$ and initiate a complexity classification of Matching Cut for $H$ -free graphs.

Partitioning H-Free Graphs of Bounded Diameter

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of $H$ -free graphs, that is, graphs that do not contain some graph $H$ as an induced subgraph, have proven to be an ideal testbed for such a complexity study. However, if the forbidden graph $H$ contains a cycle or claw, then these problems often stay NP-complete. A recent complexity study on the $k$ -Colouring problem shows that we may still obtain tractable results if we also bound the diameter of the $H$ -free input graph. We continue this line of research by initiating a complexity study on the impact of bounding the diameter for a variety of classical vertex partitioning problems restricted to $H$ -free graphs. We prove that bounding the diameter does not help for Independent Set, but leads to new tractable cases for problems closely related to 3-Colouring. That is, we show that Near-Bipartiteness, Independent Feedback Vertex Set, Independent Odd Cycle Transversal, Acyclic 3-Colouring and Star 3-Colouring are all polynomial-time solvable for chair-free graphs of bounded diameter. To obtain these results we exploit a new structural property of 3-colourable chair-free graphs.

preprint2018arXiv

Simple Games versus Weighted Voting Games: Bounding the Critical Threshold Value

A simple game $(N,v)$ is given by a set $N$ of $n$ players and a partition of~ $2^N$ into a set~ $\mathcal{L}$ of losing coalitions~ $L$ with value $v(L)=0$ that is closed under taking subsets and a set $\mathcal{W}$ of winning coalitions $W$ with $v(W)=1$ . Simple games with $α= \min_{p\geq 0}\max_{W\in {\cal W}, L\in {\cal L}} \frac{p(L)}{p(W)}<1$ are exactly the weighted voting games. We show that $α\leq \frac{1}{4}n$ for every simple game $(N,v)$ , confirming the conjecture of Freixas and Kurz (IJGT, 2014). For complete simple games, Freixas and Kurz conjectured that $α=O(\sqrt{n})$ . We prove this conjecture up to a $\ln n$ factor. We also prove that for graphic simple games, that is, simple games in which every minimal winning coalition has size~2, computing $α$ is \NP-hard, but polynomial-time solvable if the underlying graph is bipartite. Moreover, we show that for every graphic simple game, deciding if $α<a$ is polynomial-time solvable for every fixed $a>0$ .

A Linear Kernel for Finding Square Roots of Almost Planar Graphs

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 from each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the "distance from triviality" framework. For an integer k, a planar+kv graph (or k-apex graph) is a graph that can be made planar by the removal of at most k vertices. We prove that a generalization of Square Root, in which some edges are prescribed to be either in or out of any solution, has a kernel of size O(k) for planar+kv graphs, when parameterized by k. Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem.

A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs

For a positive integer $k$ , a $k$ -colouring of a graph $G=(V,E)$ is a mapping $c: V\rightarrow\{1,2,...,k\}$ such that $c(u)\neq c(v)$ whenever $uv\in E$ . The Colouring problem is to decide, for a given $G$ and $k$ , whether a $k$ -colouring of $G$ exists. If $k$ is fixed (that is, it is not part of the input), we have the decision problem $k$ -Colouring instead. We survey known results on the computational complexity of Colouring and $k$ -Colouring for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial colouring, or where lists of permissible colours are given for each vertex.

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.

Squares of Low Maximum Degree

A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n^4)-time solvable for graphs of maximum degree at most 6.

The Stable Fixtures Problem with Payments

We generalize two well-known game-theoretic models by introducing multiple partners matching games, defined by a graph $G=(N,E)$ , with an integer vertex capacity function $b$ and an edge weighting $w$ . The set $N$ consists of a number of players that are to form a set $M\subseteq E$ of 2-player coalitions $ij$ with value $w(ij)$ , such that each player $i$ is in at most $b(i)$ coalitions. A payoff vector is a mapping $p: N \times N \rightarrow {\mathbb R}$ with $p(i,j)+p(j,i)=w(ij)$ if $ij\in M$ and $p(i,j)=p(j,i)=0$ if $ij\notin M$ . The pair $(M,p)$ is called a solution. A pair of players $i,j$ with $ij\in E\setminus M$ blocks a solution $(M,p)$ if $i,j$ can form, possibly only after withdrawing from one of their existing 2-player coalitions, a new 2-player coalition in which they are mutually better off. A solution is stable if it has no blocking pairs. We give a polynomial-time algorithm that either finds that a given multiple partners matching game has no stable solution, or obtains a stable solution for it. We characterize the set of stable solutions of a multiple partners matching game in two different ways and show how this leads to simple proofs for a number of known results of Sotomayor (1992,1999,2007) for multiple partners ssignment games and to generalizations of some of these results to multiple partners matching games. We also perform a study on the core of the corresponding cooperative game, where coalitions of any size may be formed. In particular we show that the standard relation between the existence of a stable solution and the non-emptiness of the core, which holds in the other models with payments, is no longer valid for our (most general) model. We also prove that the problem of deciding if an allocation belongs to the core jumps from being polynomial-time solvable for $b\leq 2$ to NP-complete for $b\equiv 3$ .

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.

A Reconfigurations Analogue of Brooks' Theorem and its Consequences

Let $G$ be a simple undirected graph on $n$ vertices with maximum degree~ $Δ$ . Brooks' Theorem states that $G$ has a $Δ$ -colouring unless~ $G$ is a complete graph, or a cycle with an odd number of vertices. To recolour $G$ is to obtain a new proper colouring by changing the colour of one vertex. We show an analogue of Brooks' Theorem by proving that from any $k$ -colouring, $k>Δ$ , a $Δ$ -colouring of $G$ can be obtained by a sequence of $O(n^2)$ recolourings using only the original $k$ colours unless $G$ is a complete graph or a cycle with an odd number of vertices, or $k=Δ+1$ , $G$ is $Δ$ -regular and, for each vertex $v$ in $G$ , no two neighbours of $v$ are coloured alike. We use this result to study the reconfiguration graph $R_k(G)$ of the $k$ -colourings of $G$ . The vertex set of $R_k(G)$ is the set of all possible $k$ -colourings of $G$ and two colourings are adjacent if they differ on exactly one vertex. We prove that for $Δ\geq 3$ , $R_{Δ+1}(G)$ consists of isolated vertices and at most one further component which has diameter $O(n^2)$ . This result enables us to complete both a structural classification and an algorithmic classification for reconfigurations of colourings of graphs of bounded maximum degree.

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.

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.

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.

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

The Price of Connectivity for Feedback Vertex Set

Let fvs $(G)$ and cfvs(G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph $G$ , respectively. The price of connectivity for feedback vertex set (poc-fvs) for a class of graphs ${\cal G}$ is defined as the maximum ratio $\mbox{cfvs}(G)/\mbox{fvs}(G)$ over all connected graphs $G\in {\cal G}$ . We study the poc-fvs for graph classes defined by a finite family ${\cal H}$ of forbidden induced subgraphs. We characterize exactly those finite families ${\cal H}$ for which the poc-fvs for ${\cal H}$ -free graphs is upper bounded by a constant. Additionally, for the case where $|{\cal H}|=1$ , we determine exactly those graphs $H$ for which there exists a constant $c_H$ such that $\mbox{cfvs}(G)\leq \mbox{fvs}(G) + c_H$ for every connected $H$ -free graph $G$ , as well as exactly those graphs $H$ for which we can take $c_H=0$ .

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.

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.

Finding Shortest Paths between Graph Colourings

The $k$ -colouring reconfiguration problem asks whether, for a given graph $G$ , two proper $k$ -colourings $α$ and $β$ of $G$ , and a positive integer $\ell$ , there exists a sequence of at most $\ell+1$ proper $k$ -colourings of $G$ which starts with $α$ and ends with $β$ and where successive colourings in the sequence differ on exactly one vertex of $G$ . We give a complete picture of the parameterized complexity of the $k$ -colouring reconfiguration problem for each fixed $k$ when parameterized by $\ell$ . First we show that the $k$ -colouring reconfiguration problem is polynomial-time solvable for $k=3$ , settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all $k \geq 4$ , we show that the $k$ -colouring reconfiguration problem, when parameterized by $\ell$ , is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.

Induced Disjoint Paths in Circular-Arc Graphs in Linear Time

The Induced Disjoint Paths problem is to test whether a graph G with k distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i connects s_i and t_i for i=1,...,k, and P_i and P_j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1<=i < j<=k. We present a linear-time algorithm for Induced Disjoint Paths on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs (s_i,t_i) are not necessarily distinct.

Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph G allows a homomorphism to a given graph H that is locally bijective, surjective, or injective, respectively, are NP-complete, even when G has pathwidth at most 5, 4, or 2, respectively, or when both G and H have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if G has bounded treewidth and in addition G or H has bounded maximum degree.