Author name cluster

Daniël Paulusma

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

48 papers

2 author rows

TCS Journal 2025 Journal Article

Computing subset vertex covers in H-free graphs

Nick Brettell
Jelle J. Oostveen
Sukanya Pandey
Daniël Paulusma
Johannes Rauch
Erik Jan van Leeuwen

We consider a natural generalization of Vertex Cover: the Subset Vertex Cover problem, which is to decide for a graph G = ( V, E ), a subset T ⊆ V and integer k, if V has a subset S of size at most k, such that S contains at least one end-vertex of every edge incident to a vertex of T. A graph is H-free if it does not contain H as an induced subgraph. We solve two open problems from the literature by proving that Subset Vertex Cover is NP-complete on subcubic (claw, diamond)-free planar graphs and on 2-unipolar graphs, a subclass of 2 P 3 -free weakly chordal graphs. Our results show for the first time that Subset Vertex Cover is computationally harder than Vertex Cover (under P ≠ NP ). We also prove new polynomial time results, some of which follow from a reduction to Vertex Cover restricted to classes of probe graphs. We first give a dichotomy on graphs where G [ T ] is H-free. Namely, we show that Subset Vertex Cover is polynomial-time solvable on graphs G, for which G [ T ] is H-free, if H = s P 1 + t P 2 and NP-complete otherwise. Moreover, we prove that Subset Vertex Cover is polynomial-time solvable for ( s P 1 + P 2 + P 3 ) -free graphs and bounded mim-width graphs. By combining our new results with known results we obtain a partial complexity classification for Subset Vertex Cover on H-free graphs.

TCS Journal 2024 Journal Article

Classifying subset feedback vertex set for H-free graphs

Giacomo Paesani
Daniël Paulusma
Paweł Rzążewski

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.

AAMAS Conference 2024 Conference Paper

Computing Balanced Solutions for Large International Kidney Exchange Schemes when Cycle Length is Unbounded

Márton Benedek
Péter Biró
Gergely Csáji
Matthew Johnson
Daniël Paulusma
Xin Ye

In kidney exchange programmes (KEP) patients may swap their incompatible donors leading to cycles of kidney transplants. Countries try to merge their national patient-donor pools leading to international KEPs (IKEPs). Long-term stability of an IKEP can be achieved through a credit-based system. The goal is to find, in each round, an optimal solution that closely approximates this target allocation. We provide both theoretical and experimental results for the case where the cycle length is unbounded.

TCS Journal 2024 Journal Article

Dichotomies for Maximum Matching Cut: H-freeness, bounded diameter, bounded radius

Felicia Lucke
Daniël Paulusma
Bernard Ries

The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect) matching cut, i. e. , a (perfect) matching that is also an edge cut of G. Both Matching Cut and Perfect Matching Cut are known to be NP-complete. A perfect matching cut is also a matching cut with maximum number of edges. To increase our understanding of the relationship between the two problems, we perform a complexity study for the Maximum Matching Cut problem, which is to determine a largest matching cut in a graph. Our results yield full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and H-free graphs. A disconnected perfect matching of a graph G is a perfect matching that contains a matching cut of G. We also show how our new techniques can be used for finding a disconnected perfect matching with a largest matching cut for special graph classes. In this way we can prove that the decision problem Disconnected Perfect Matching is polynomial-time solvable for ( P 6 + s P 2 ) -free graphs for every s ≥ 0, extending a known result for P 5 -free graphs (Bouquet and Picouleau, 2020).

MFCS Conference 2023 Conference Paper

Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Matthew Johnson 0002
Barnaby Martin
Sukanya Pandey
Daniël Paulusma
Siani Smith
Erik Jan van Leeuwen

For any finite set ℋ = {H_1, …, H_p} of graphs, a graph is ℋ-subgraph-free if it does not contain any of H_1, …, H_p as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity can be classified on classes of ℋ-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.

MFCS Conference 2023 Conference Paper

Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius

Felicia Lucke
Daniël Paulusma
Bernard Ries

The (Perfect) Matching Cut problem is to decide if a graph G has a (perfect) matching cut, i. e. , a (perfect) matching that is also an edge cut of G. Both Matching Cut and Perfect Matching Cut are known to be NP-complete, leading to many complexity results for both problems on special graph classes. A perfect matching cut is also a matching cut with maximum number of edges. To increase our understanding of the relationship between the two problems, we introduce the Maximum Matching Cut problem. This problem is to determine a largest matching cut in a graph. We generalize and unify known polynomial-time algorithms for Matching Cut and Perfect Matching Cut restricted to graphs of diameter at most 2 and to (P₆+sP₂)-free graphs. We also show that the complexity of Maximum Matching Cut differs from the complexities of Matching Cut and Perfect Matching Cut by proving NP-hardness of Maximum Matching Cut for 2P₃-free quadrangulated graphs of diameter 3 and radius 2 and for subcubic line graphs of triangle-free graphs. In this way, we obtain full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and H-free graphs.

TCS Journal 2023 Journal Article

Few induced disjoint paths for H-free graphs

Barnaby Martin
Daniël Paulusma
Siani Smith
Erik Jan van Leeuwen

Paths P 1, …, 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. For a fixed integer k, the k -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. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer k, a classical result from the literature states that even 2-Induced Disjoint Paths is NP-complete. We prove new complexity results for k -Induced Disjoint Paths if the input is restricted to H-free graphs, that is, graphs without a fixed graph H as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where k is part of the input.

TCS Journal 2022 Journal Article

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter

Barnaby Martin
Daniël Paulusma
Siani Smith

For a fixed integer, the k -Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is known that for all k ≥ 3, the k -Colouring problem is NP-complete for H-free graphs if H contains an induced claw or cycle. The case where H contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

AAMAS Conference 2022 Conference Paper

Computing Balanced Solutions for Large International Kidney Exchange Schemes

Márton Benedek
Péter Biró
Walter Kern
Daniël Paulusma

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient-donor pools. We consider a recent credit system where in each round, countries are given an initial kidney transplant allocation which is adjusted by a credit function yielding a target allocation. The goal is to find a solution in the patient-donor compatibility graph that approaches the target allocation as closely as possible, to ensure long-term stability of the international pool. As solutions, we use maximum matchings that lexicographically minimize the country deviations from the target allocation. We first give a polynomial-time algorithm for computing such matchings. We then perform, for the first time, a computational study for a large number of countries. For the initial allocations we use, besides two easy-to-compute solution concepts, two classical concepts: the Shapley value and the nucleolus. These are hard to compute, but by using state-of-the-art software we show that they are now within reach for IKEPs of up to fifteen countries. Our experiments show that using lexicographically minimal maximum matchings instead of ones that only minimize the largest deviation from the target allocation (as previously done) may make an IKEP up to 52% more balanced.

TCS Journal 2022 Journal Article

Computing subset transversals in H-free graphs

Nick Brettell
Matthew Johnson
Giacomo Paesani
Daniël Paulusma

We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to H-free graphs, that is, to graphs that do not contain some fixed graph H as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on H-free graphs for every graph H except when H = s P 1 + P 4 for some s ≥ 1. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for ( s P 1 + P 4 ) -free graphs for every s ≥ 1.

TCS Journal 2022 Journal Article

Disjoint paths and connected subgraphs for H-free graphs

Walter Kern
Barnaby Martin
Daniël Paulusma
Siani Smith
Erik Jan van Leeuwen

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct vertex pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for H-free graphs. If k is fixed, we obtain the k -Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every k ≥ 1. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of k -Disjoint Connected Subgraphs for H-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for H-free graphs as for Disjoint Paths. Moreover, we give exact algorithms for Disjoint Paths and Disjoint Connected Subgraphs on graphs with n vertices and m edges that have running times of O ( 2 n n 2 k ) and O ( 3 n k m ), respectively.

TCS Journal 2022 Journal Article

On the complexity of matching cut for graphs of bounded radius and H-free graphs

Felicia Lucke
Daniël Paulusma
Bernard Ries

For a connected graph G = ( V, E ), a matching M ⊆ 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 ≤ 2 and NP-complete if d ≥ 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 ( s P 3 + P 6 ) -free graphs for every s ≥ 0 and initiate a complexity classification of Matching Cut for H-free graphs.

TCS Journal 2022 Journal Article

Partitioning H-free graphs of bounded diameter

Christoph Brause
Petr Golovach
Barnaby Martin
Daniël Paulusma
Siani Smith

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 (MFCS 2019) 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.

MFCS Conference 2021 Conference Paper

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

Giacomo Paesani
Daniël Paulusma
Pawel Rzazewski

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 both problems are polynomial-time solvable for sP₃-free graphs for every integer s ≥ 1; here, the graph sP₃ denotes the disjoint union of s paths on three vertices. Our results show that both problems exhibit the same behaviour on H-free graphs (subject to some open cases). This is in part explained by a new general algorithm we design for finding in a graph G a largest induced subgraph whose blocks belong to some finite class 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.

TCS Journal 2021 Journal Article

Steiner trees for hereditary graph classes: A treewidth perspective

Hans L. Bodlaender
Nick Brettell
Matthew Johnson
Giacomo Paesani
Daniël Paulusma
Erik Jan van Leeuwen

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to ( H 1, H 2 ) -free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H-free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree (assuming P ≠ NP ). We also find that Edge Steiner Tree is polynomial-time solvable for ( H 1, H 2 ) -free graphs if and only if the treewidth of the class of ( H 1, H 2 ) -free graphs is bounded (subject to P ≠ NP ). To obtain the latter result, we determine all pairs ( H 1, H 2 ) for which the class of ( H 1, H 2 ) -free graphs has bounded treewidth.

MFCS Conference 2019 Conference Paper

Colouring H-Free Graphs of Bounded Diameter

Barnaby Martin
Daniël Paulusma
Siani Smith

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is known that Colouring is NP-complete for H-free graphs if H contains a cycle or claw, even for fixed k >= 3. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

TCS Journal 2018 Journal Article

Contraction and deletion blockers for perfect graphs and H-free graphs

Öznur Yaşar Diner
Daniël Paulusma
Christophe Picouleau
Bernard Ries

We study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter π of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number χ, clique number ω and independence number α, and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem for S = { ec } and S = { vd } and π ∈ { χ, ω, α } for a number of subclasses of perfect graphs. We use these results to determine the complexity of the problem for S = { ec } and S = { vd } and π ∈ { χ, ω, α } restricted to H-free graphs.

TCS Journal 2018 Journal Article

Minimum connected transversals in graphs: New hardness results and tractable cases using the price of connectivity

Nina Chiarelli
Tatiana R. Hartinger
Matthew Johnson
Martin Milanič
Daniël Paulusma

We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. Just like their original counterparts, these variants are NP-complete for general graphs. A graph G is H-free for some graph H if G contains no induced subgraph isomorphic to H. It is known that Connected Vertex Cover is NP-complete even for H-free graphs if H contains a claw or a cycle. We show that the two other connected variants also remain NP-complete if H contains a cycle or claw. In the remaining case H is a linear forest. We show that Connected Vertex Cover, Connected Feedback Vertex Set, and Connected Odd Cycle Transversal are polynomial-time solvable for s P 2 -free graphs for every constant s ≥ 1. For proving these results we use known results on the price of connectivity for vertex cover, feedback vertex set, and odd cycle transversal. This is the first application of the price of connectivity that results in polynomial-time algorithms.

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

TCS Journal 2017 Journal Article

A linear kernel for finding square roots of almost planar graphs

Petr A. Golovach
Dieter Kratsch
Daniël Paulusma
Anthony Stewart

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 at 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 + k v 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 + k v 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.

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 2016 Journal Article

Induced disjoint paths in circular-arc graphs in linear time

Petr A. Golovach
Daniël Paulusma
Erik Jan van Leeuwen

The Induced Disjoint Paths problem is to test whether an graph G on n vertices 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 that solves Induced Disjoint Paths and finds the corresponding paths (if they exist) 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. In both cases, if a representation of the graph is given, then the algorithms run in O ( n + k ) time.

MFCS Conference 2016 Conference Paper

Using Contracted Solution Graphs for Solving Reconfiguration Problems

Paul S. Bonsma
Daniël Paulusma

We introduce a dynamic programming method for solving reconfiguration problems, based on contracted solution graphs, which are obtained from solution graphs by performing an appropriate series of edge contractions that decrease the graph size without losing any critical information needed to solve the reconfiguration problem under consideration. As an example, we consider a well-studied problem: given two k-colorings alpha and beta of a graph G, can alpha be modified into beta by recoloring one vertex of G at a time, while maintaining a k-coloring throughout? By applying our method in combination with a thorough exploitation of the graph structure we obtain a polynomial-time algorithm for (k-2)-connected chordal graphs.

TCS Journal 2015 Journal Article

Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Steven Chaplick
Jiří Fiala
Pim van 't Hof
Daniël Paulusma
Marek Tesař

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.

I&C Journal 2014 Journal Article

Closing complexity gaps for coloring problems on H-free graphs

Petr A. Golovach
Daniël Paulusma
Jian Song

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = ( V, E ) is a mapping c: V → { 1, 2, … } such that no two adjacent vertices have the same color, i. e. , c ( u ) ≠ c ( v ) if u v ∈ E; if | c ( V ) | ⩽ k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L ( u ). By imposing an upper bound ℓ on the size of each L ( u ) we obtain the ℓ -List Coloring problem. We first classify the Precoloring Extension problem and the ℓ -List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n-vertex graphs of minimum degree n − 2, i. e. , for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n − 2. Finally, for a fixed integer k > 0, the List k -Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L ( u ) that must be a subset of { 1, …, k }. We show that List 4-Coloring is NP-complete for P 6 -free graphs, where P 6 is the path on six vertices. This completes the classification of List k -Coloring for P 6 -free graphs.

TCS Journal 2014 Journal Article

Solutions for the stable roommates problem with payments

Péter Biró
Matthijs Bomhoff
Petr A. Golovach
Walter Kern
Daniël Paulusma

The stable roommates problem with payments has as input a graph G = ( V, E ) with an edge weighting w: E → R ≥ 0 and the problem is to find a stable solution. A solution is a matching M with a vector p ∈ R ≥ 0 V that satisfies p u + p v = w ( u v ) for all u v ∈ M and p u = 0 for all u unmatched in M. A solution is stable if it prevents blocking pairs, i. e. , pairs of adjacent vertices u and v with p u + p v < w ( u v ), or equivalently, if the total blocking value ∑ u v ∈ E max { 0, w ( u v ) − ( p u + p v ) } = 0. By pinpointing a relationship to the accessibility of the coalition structure core of matching games, we give a constructive proof for showing that every yes-instance of the stable roommates problem with payments allows a path of linear length that starts in an arbitrary unstable solution and that ends in a stable solution. This generalizes a result of Chen, Fujishige and Yang (2011) [4] for bipartite instances to general instances. We also show that the problems Blocking Pairs and Blocking Value, which are to find a solution with a minimum number of blocking pairs or a minimum total blocking value, respectively, are NP-hard. Finally, we prove that the variant of the first problem, in which the number of blocking pairs must be minimized with respect to some fixed matching, is NP-hard, whereas this variant of the second problem is polynomial-time solvable.

TCS Journal 2013 Journal Article

Detecting induced minors in AT-free graphs

Petr A. Golovach
Dieter Kratsch
Daniël Paulusma

The Induced Minor problem is that of testing whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. If only edge contractions are permitted, we obtain the Contractibility problem. We prove that Induced Minor is polynomial-time solvable when G is AT-free and H is fixed, i. e. , not part of the input. In addition, we show that Contractibility is polynomial-time solvable when G is AT-free and H is a fixed triangle-free graph. We complement these two results by proving that both problems are W[1]-hard on AT-free graphs when parameterized by | V H |.

TCS Journal 2013 Journal Article

Increasing the minimum degree of a graph by contractions

Petr A. Golovach
Marcin Kamiński
Daniël Paulusma
Dimitrios M. Thilikos

The Degree Contractibility problem is to test whether a given graph G can be modified to a graph of minimum degree at least d by using at most k contractions. We prove the following three results. First, Degree Contractibility is NP-complete even when d = 14. Second, it is fixed-parameter tractable when parameterized by k and d. Third, it is W [ 1 ] -hard when parameterized by k. We also study its variant where the input graph is weighted, i. e. , has some edge weighting and the contractions preserve these weights. The Weighted Degree Contractibility problem is to test if a weighted graph G can be contracted to a weighted graph of minimum weighted degree at least d by using at most k weighted contractions. We show that this problem is NP-complete and that it is fixed-parameter tractable when parameterized by k. In addition, we pinpoint a relationship with the problem of finding a minimal edge-cut of maximum size in a graph and study the parameterized complexity of this problem and its variants.

TCS Journal 2013 Journal Article

Obtaining planarity by contracting few edges

Petr A. Golovach
Pim van ’t Hof
Daniël Paulusma

The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k.

MFCS Conference 2012 Conference Paper

Coloring Graphs Characterized by a Forbidden Subgraph

Petr A. Golovach
Daniël Paulusma
Bernard Ries

Abstract The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k, such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an induced subgraph is known for each fixed graph H. A natural variant is to forbid a graph H only as a subgraph. We call such graphs strongly H -free and initiate a complexity classification of Coloring for strongly H -free graphs. We show that Coloring is NP -complete for strongly H -free graphs, even for k = 3, when H contains a cycle, has maximum degree at least five, or contains a connected component with two vertices of degree four. We also give three conditions on a forest H of maximum degree at most four and with at most one vertex of degree four in each of its connected components, such that Coloring is NP -complete for strongly H -free graphs even for k = 3. Finally, we classify the computational complexity of Coloring on strongly H -free graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when H is a forest that has at most seven vertices and maximum degree at most four.

TCS Journal 2012 Journal Article

Computing vertex-surjective homomorphisms to partially reflexive trees

Petr A. Golovach
Daniël Paulusma
Jian Song

A homomorphism from a graph G to a graph H is a vertex mapping f: V G → V H such that f ( u ) and f ( v ) form an edge in H whenever u and v form an edge in G. The H -Coloring problem is that of testing whether a graph G allows a homomorphism to a given graph H. A well-known result of Hell and Nešetřil determines the computational complexity of this problem for any fixed graph H. We study a natural variant of this problem, namely the Surjective H -Coloring problem, which is that of testing whether a graph G allows a homomorphism to a graph H that is (vertex-)surjective. We classify the computational complexity of this problem for when H is any fixed partially reflexive tree. Thus we identify the first class of target graphs H for which the computational complexity of Surjective H -Coloring can be determined. For the polynomial-time solvable cases we show a number of parameterized complexity results, including in particular ones on graph classes with (locally) bounded expansion.

TCS Journal 2012 Journal Article

Determining the chromatic number of triangle-free 2 P 3 -free graphs in polynomial time

Hajo Broersma
Petr A. Golovach
Daniël Paulusma
Jian Song

Let 2 P 3 denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H -free. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. Its computational complexity for triangle-free H -free graphs has been classified for every fixed graph H on at most 6 vertices except for the case H = 2 P 3. This remaining case is posed as an open problem by Dabrowski, Lozin, Raman and Ries. We solve their open problem by showing polynomial-time solvability.

TCS Journal 2012 Journal Article

Induced packing of odd cycles in planar graphs

Petr A. Golovach
Marcin Kamiński
Daniël Paulusma
Dimitrios M. Thilikos

An induced packing of odd cycles in a graph is a packing such that there is no edge in the graph between any two odd cycles in the packing. We prove that an induced packing of k odd cycles in an n -vertex graph can be found (if it exists) in time 2 O ( k 3 / 2 ) ⋅ n 2 + ϵ (for any constant ϵ > 0 ) when the input graph is planar. We also show that deciding if a graph has an induced packing of two odd induced cycles is NP-complete.

MFCS Conference 2012 Conference Paper

Obtaining Planarity by Contracting Few Edges

Petr A. Golovach
Pim van 't Hof
Daniël Paulusma

Abstract The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP -complete. We show that it is fixed-parameter tractable when parameterized by k.

TCS Journal 2012 Journal Article

Updating the complexity status of coloring graphs without a fixed induced linear forest

Hajo Broersma
Petr A. Golovach
Daniël Paulusma
Jian Song

A graph is H -free if it does not contain an induced subgraph isomorphic to the graph H. The graph P k denotes a path on k vertices. The ℓ -Coloring problem is the problem to decide whether a graph can be colored with at most ℓ colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for P 8 -free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for P 9 -free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for P 8 -free graphs. Additionally, we prove that the precoloring extension version of 4 -Coloring is NP-complete for P 7 -free graphs, but that the precoloring extension version of 3 -Coloring can be solved in polynomial time for ( P 2 + P 4 ) -free graphs, a subclass of P 7 -free graphs. Here P 2 + P 4 denotes the disjoint union of a P 2 and a P 4. We denote the disjoint union of s copies of a P 3 by s P 3 and involve Ramsey numbers to prove that the precoloring extension version of 3 -Coloring can be solved in polynomial time for s P 3 -free graphs for any fixed s. Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for H -free graphs when H is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.

MFCS Conference 2011 Conference Paper

Contracting a Chordal Graph to a Split Graph or a Tree

Petr A. Golovach
Marcin Kaminski 0001
Daniël Paulusma

Abstract The problems Contractibility and Induced Minor are to test whether a graph G contains a graph H as a contraction or as an induced minor, respectively. We show that these two problems can be solved in \(|V_G|^{f(|V_H|)}\) time if G is a chordal input graph and H is a split graph or a tree. In contrast, we show that containment relations extending Subgraph Isomorphism can be solved in linear time if G is a chordal input graph and H is an arbitrary graph not part of the input.

TCS Journal 2011 Journal Article

On partitioning a graph into two connected subgraphs

Daniël Paulusma
Johan M.M. van Rooij

Suppose a graph G is given with two vertex-disjoint sets of vertices Z 1 and Z 2. Can we partition the remaining vertices of G such that we obtain two connected vertex-disjoint subgraphs of G that contain Z 1 and Z 2, respectively? This problem is known as the 2-Disjoint Connected Subgraphs problem. It is already NP-complete for the class of n -vertex graphs G = ( V, E ) in which Z 1 and Z 2 each contain a connected set that dominates all vertices in V ∖ ( Z 1 ∪ Z 2 ). We present an O ∗ ( 1. 205 1 n ) time algorithm that solves it for this graph class. As a consequence, we can also solve this problem in O ∗ ( 1. 205 1 n ) time for the classes of n -vertex P 6 -free graphs and split graphs. This is an improvement upon a recent O ∗ ( 1. 579 0 n ) time algorithm for these two classes. Our approach translates the problem to a generalized version of hypergraph 2-coloring and combines inclusion/exclusion with measure and conquer.

TCS Journal 2011 Journal Article

Parameterizing cut sets in a graph by the number of their components

Takehiro Ito
Marcin Kamiński
Daniël Paulusma
Dimitrios M. Thilikos

For a connected graph G = ( V, E ), a subset U ⊆ V is a disconnected cut if U disconnects G and the subgraph G [ U ] induced by U is disconnected as well. A cut U is a k -cut if G [ U ] contains exactly k ( ≥ 1 ) components. More specifically, a k -cut U is a ( k, ℓ ) -cut if V ∖ U induces a subgraph with exactly ℓ ( ≥ 2 ) components. The Disconnected Cut problem is to test whether a graph has a disconnected cut and is known to be NP-complete. The problems k -Cut and ( k, ℓ ) -Cut are to test whether a graph has a k -cut or ( k, ℓ ) -cut, respectively. By pinpointing a close relationship to graph contractibility problems we show that ( k, ℓ ) -Cut is in P for k = 1 and any fixed constant ℓ ≥ 2, while it is NP-complete for any fixed pair k, ℓ ≥ 2. We then prove that k -Cut is in P for k = 1 and NP-complete for any fixed k ≥ 2. On the other hand, for every fixed integer g ≥ 0, we present an FPT algorithm that solves ( k, ℓ ) -Cut on graphs of Euler genus at most g when parameterized by k + ℓ. By modifying this algorithm we can also show that k -Cut is in FPT for this graph class when parameterized by k. Finally, we show that Disconnected Cut is solvable in polynomial time for minor-closed classes of graphs excluding some apex graph.

SAT Conference 2011 Conference Paper

Satisfiability of Acyclic and almost Acyclic CNF Formulas (II)

Sebastian Ordyniak
Daniël Paulusma
Stefan Szeider

Abstract In the first part of this work (FSTTCS’10) we have shown that the satisfiability of CNF formulas with β -acyclic hypergraphs can be decided in polynomial time. In this paper we continue and extend this work. The decision algorithm for β -acyclic formulas is based on a special type of Davis-Putnam resolution where each resolvent is a subset of a parent clause. We generalize the class of β -acyclic formulas to more general CNF formulas for which this type of Davis-Putnam resolution still applies. We then compare the class of β -acyclic formulas and this superclass with a number of known polynomial formula classes.

TCS Journal 2010 Journal Article

Computing role assignments of chordal graphs

Pim van ’t Hof
Daniël Paulusma
Johan M.M. van Rooij

In social network theory, a simple graph G is called k -role assignable if there is a surjective mapping that assigns a number from { 1, …, k }, called a role, to each vertex of G such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the k -Role Assignment problem. This problem is known to be NP-complete for any fixed k ≥ 2. In this paper, we classify the computational complexity of the k -Role Assignment problem for the class of chordal graphs. We show that for this class the problem can be solved in linear time for k = 2, but remains NP-complete for any k ≥ 3. This generalizes earlier results by Sheng and answers her open problem.

TCS Journal 2009 Journal Article

Covering graphs with few complete bipartite subgraphs

Herbert Fleischner
Egbert Mujuni
Daniël Paulusma
Stefan Szeider

We consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the biclique partition problem is defined similarly with the additional condition that the bicliques are required to be mutually edge-disjoint. The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most k bicliques, the biclique vertex-partition problem is defined similarly with the additional condition that the bicliques are required to be mutually vertex-disjoint. All these four problems are known to be NP-complete even if the given graph is bipartite. In this paper, we investigate them in the framework of parameterized complexity: do the problems become easier if k is assumed to be small? We show that, considering k as the parameter, the first two problems are fixed-parameter tractable, while the latter two problems are not fixed-parameter tractable unless P = NP.

TCS Journal 2009 Journal Article

Partitioning graphs into connected parts

Pim van ’t Hof
Daniël Paulusma
Gerhard J. Woeginger

The 2-Disjoint Connected Subgraphs problem asks if a given graph has two vertex-disjoint connected subgraphs containing prespecified sets of vertices. We show that this problem is NP-complete even if one of the sets has cardinality 2. The Longest Path Contractibility problem asks for the largest integer ℓ for which an input graph can be contracted to the path P ℓ on ℓ vertices. We show that the computational complexity of the Longest Path Contractibility problem restricted to P ℓ -free graphs jumps from being polynomially solvable to being NP-hard at ℓ = 6, while this jump occurs at ℓ = 5 for the 2-Disjoint Connected Subgraphs problem. We also present an exact algorithm that solves the 2-Disjoint Connected Subgraphs problem faster than O ∗ ( 2 n ) for any n -vertex P ℓ -free graph. For ℓ = 6, its running time is O ∗ ( 1. 579 0 n ). We modify this algorithm to solve the Longest Path Contractibility problem for P 6 -free graphs in O ∗ ( 1. 579 0 n ) time.

TCS Journal 2009 Journal Article

Upper bounds and algorithms for parallel knock-out numbers

Hajo Broersma
Matthew Johnson
Daniël Paulusma

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph G, the minimum number of required rounds is O ( n ); in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is O ( α ), where α is the independence number of G. This upper bound is tight. We also show that for reducible K 1, p -free graphs at most p − 1 rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.

MFCS Conference 2008 Conference Paper

Computing Sharp 2-Factors in Claw-Free Graphs

Hajo Broersma
Daniël Paulusma

Abstract In a recently submitted paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we extend these results by presenting a polynomial algorithm that constructs a 2-factor of a claw-free graph with minimum degree at least four whose number of components meets this bound. As a byproduct we show that the problem of obtaining a minimum 2-factor (if it exists) is polynomially solvable for a subclass of claw-free graphs. As another byproduct we give a short constructive proof for a result of Ryjáček, Saito & Schelp.

TCS Journal 2008 Journal Article

The computational complexity of the parallel knock-out problem

Hajo Broersma
Matthew Johnson
Daniël Paulusma
Iain A. Stewart

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for a given bipartite graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers k ≥ 2, the problem of whether a given bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) k rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time. We also show that r -regular graphs with r ≥ 1, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.

TCS Journal 2005 Journal Article

A complete complexity classification of the role assignment problem

Jiří Fiala
Daniël Paulusma

In social network theory a society is often represented by a simple graph G, where vertices stand for individuals and edges represent relationships between those individuals. The description of the social network is tried to be simplified by assigning roles to the individuals, such that the neighborhood relation is preserved. Formally, for a fixed graph R we ask for a vertex mapping r: V G → V R, such that r ( N G ( u ) ) = N R ( r ( u ) ) for all u ∈ V G. If such a mapping exists the graph G is called R-role assignable and the corresponding decision problem is called the R-role assignment problem. Kristiansen and Telle conjectured that the R-role assignment problem is an NP -complete problem for any simple connected graph R on at least three vertices. In this paper we prove their conjecture. In addition, we determine the computational complexity of the role assignment problem for nonsimple and disconnected role graphs, as these are considered in social network theory as well.

MFCS Conference 2005 Conference Paper

Matrix and Graph Orders Derived from Locally Constrained Graph Homomorphisms

Jirí Fiala 0001
Daniël Paulusma
Jan Arne Telle

Abstract We consider three types of locally constrained graph homomorphisms: bijective, injective and surjective. We show that the three orders imposed on graphs by existence of these three types of homomorphisms are partial orders. We extend the well-known connection between degree refinement matrices of graphs and locally bijective graph homomorphisms to locally injective and locally surjective homomorphisms by showing that the orders imposed on degree refinement matrices by our locally constrained graph homomorphisms are also partial orders. We provide several equivalent characterizations of degree (refinement) matrices, e. g. in terms of the dimension of the cycle space of a graph related to the matrix. As a consequence we can efficiently check whether a given matrix M is a degree matrix of some graph and also compute the size of a smallest graph for which it is a degree matrix in polynomial time.