Outputs (22)

Modifying a Graph Using Vertex Elimination (2013)
Journal Article
Golovach, P., Heggernes, P., Hof, V. '. P., Manne, F., Paulusma, D., & Pilipczuk, M. (2015). Modifying a Graph Using Vertex Elimination. Algorithmica, 72(1), 99-125. https://doi.org/10.1007/s00453-013-9848-2

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the Elimination problem as follows: given two g... Read More about Modifying a Graph Using Vertex Elimination.

Characterizing graphs of small carving-width (2013)
Journal Article
Belmonte, R., Hof, V. '. P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13-14), 1888-1893. https://doi.org/10.1016/j.dam.2013.02.036

We characterize all graphs that have carving-width at most k for k=1,2,3. In particular, we show that a graph has carving-width at most 3 if and only if it has maximum degree at most 3 and treewidth at most 2. This enables us to identify the immersio... Read More about Characterizing graphs of small carving-width.

Detecting induced minors in AT-free graphs (2013)
Journal Article
Golovach, P., Kratsch, D., & Paulusma, D. (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science, 482, 20-32. https://doi.org/10.1016/j.tcs.2013.02.029

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 Induc... Read More about Detecting induced minors in AT-free graphs.

List Coloring in the Absence of a Linear Forest (2013)
Journal Article
Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2015). List Coloring in the Absence of a Linear Forest. Algorithmica, 71(1), 21-35. https://doi.org/10.1007/s00453-013-9777-0

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The Listk-Coloring problem requires in addition that every vertex u must receive a color from some giv... Read More about List Coloring in the Absence of a Linear Forest.

Increasing the minimum degree of a graph by contractions (2013)
Journal Article
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Increasing the minimum degree of a graph by contractions. Theoretical Computer Science, 481, 74-84. https://doi.org/10.1016/j.tcs.2013.02.030

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 whe... Read More about Increasing the minimum degree of a graph by contractions.

Satisfiability of acyclic and almost acyclic CNF formulas (2013)
Journal Article
Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85-99. https://doi.org/10.1016/j.tcs.2012.12.039

We show that the Satisfiability (SAT) problem for CNF formulas with ββ-acyclic hypergraphs can be solved in polynomial time by using a special type of Davis–Putnam resolution in which each resolvent is a subset of a parent clause. We extend this clas... Read More about Satisfiability of acyclic and almost acyclic CNF formulas.

Three complexity results on coloring Pk-free graphs (2013)
Journal Article
Broersma, H., Fomin, F., Golovach, P., & Paulusma, D. (2013). Three complexity results on coloring Pk-free graphs. European Journal of Combinatorics, 34(3), 609-619. https://doi.org/10.1016/j.ejc.2011.12.008

We prove three complexity results on vertex coloring problems restricted to PkPk-free graphs, i.e., graphs that do not contain a path on kk vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring r... Read More about Three complexity results on coloring Pk-free graphs.

Obtaining planarity by contracting few edges (2013)
Journal Article
Golovach, P., van 't Hof, P., & Paulusma, D. (2013). Obtaining planarity by contracting few edges. Theoretical Computer Science, 476, 38-46. https://doi.org/10.1016/j.tcs.2012.12.041

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

Choosability on H-free graphs (2013)
Journal Article
Golovach, P., Heggernes, P., van 't Hof, P., & Paulusma, D. (2013). Choosability on H-free graphs. Information Processing Letters, 113(4), 107-110. https://doi.org/10.1016/j.ipl.2012.12.003

A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the Choosability problem restricted to H-free graphs for every graph H that does not belong to {K1,3,P1+P2,P1+P3,P4}{K1,3,P1+P2,P1+P3,P4}. W... Read More about Choosability on H-free graphs.

Graph editing to a fixed target (2013)
Presentation / Conference Contribution
Golovach, P., Paulusma, D., & Stewart, I. A. (2013, December). Graph editing to a fixed target. Presented at International Workshop on Combinatorial Algorithms, Rouen, France

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex di... Read More about Graph editing to a fixed target.

Model counting for CNF formuals of bounded module treewidth (2013)
Presentation / Conference Contribution
Paulusma, D., Slivovksy, F., & Szeider, S. (2013, December). Model counting for CNF formuals of bounded module treewidth. Presented at 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Kiel, Christian-Albrechts-Universität zu Kiel, Germany

The modular treewidth of a graph is its treewidth after the contraction of modules. Modular treewidth properly generalizes treewidth and is itself properly generalized by clique-width. We show that the number of satisfying assignments of a CNF formul... Read More about Model counting for CNF formuals of bounded module treewidth.

The price of connectivity for feedback vertex set (2013)
Presentation / Conference Contribution
Belmonte, R., Hof, V. '. P., Kaminski, M., & Paulusma, D. (2013, December). The price of connectivity for feedback vertex set. Presented at 7th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2013, Pisa, Italy

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. In general graphs, the ratio cfvs(G)/fvs(G) can be arbitrarily large. We study the interdependenc... Read More about The price of connectivity for feedback vertex set.

Sparse Square Roots (2013)
Presentation / Conference Contribution
Cochefert, M., Couturier, J.-F., Golovach, P. A., Kratsch, D., & Paulusma, D. (2013, December). Sparse Square Roots. Presented at 39th International Workshop, WG 2013, Lübeck, Germany

We show that it can be decided in polynomial time whether a graph of maximum degree 6 has a square root; if a square root exists, then our algorithm finds one with minimum number of edges. We also show that it is FPT to decide whether a connected n-v... Read More about Sparse Square Roots.

Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs (2013)
Presentation / Conference Contribution
Broersma, H. J., Fiala, J., Golovach, P. A., Kaiser, T., Paulusma, D., & Proskurowski, A. (2013, December). Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs. Presented at 39th International Workshop, WG 2013, 19-21 June 2013

We show that for all k ≤ − 1 an interval graph is − (k + 1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(n + m) time algorithm for computing the scattering number of an interval graph with n vertices and m e... Read More about Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs.

List Coloring in the Absence of Two Subgraphs (2013)
Presentation / Conference Contribution
Golovach, P. A., & Paulusma, D. (2013, December). List Coloring in the Absence of Two Subgraphs. Presented at 8th International Conference, CIAC 2013, Barcelona, Spain

list assignment of a graph G = (V;E) is a function L that assigns a list L(u) of so-called admissible colors to each u 2 V . The List Coloring problem is that of testing whether a given graph G = (V;E) has a coloring c that respects a given list assi... Read More about List Coloring in the Absence of Two Subgraphs.

Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs (2013)
Presentation / Conference Contribution
Johnson, M., Paulusma, D., & van Leeuwen, E. (2013, December). Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs. Presented at 24th International Symposium, ISAAC 2013, Hong Kong, China,

Social networks are often analyzed through a graph model of the network. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d-dimensional vector a v repr... Read More about Algorithms to Measure Diversity and Clustering in Social Networks through Dot Product Graphs.

Colouring of Graphs with Ramsey-Type Forbidden Subgraphs (2013)
Presentation / Conference Contribution
Dabrowski, K. K., Golovach, P. A., & Paulusma, D. (2013, December). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. Presented at 39th International Workshop, WG 2013, Lübeck, Germany

A colouring of a graph G = (V;E) is a mapping c : V ! f1; 2; : : :g such that c(u) 6= c(v) if uv 2 E; if jc(V )j k then c is a k-colouring. The Colouring problem is that of testing whether a given graph has a k-colouring for some given integer k. If... Read More about Colouring of Graphs with Ramsey-Type Forbidden Subgraphs.

Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints (2013)
Presentation / Conference Contribution
Belmonte, R., Golovach, P., Hof, V. '. P., & Paulusma, D. (2013, December). Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints. Presented at 8th International Symposium, IPEC 2013, Sophia Antipolis, France

Motivated by recent results of Mathieson and Szeider (J. Comput. Syst. Sci. 78(1): 179–191, 2012), we study two graph modification problems where the goal is to obtain a graph whose vertices satisfy certain degree constraints. The Regular Contraction... Read More about Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints.

Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree (2013)
Presentation / Conference Contribution
Chaplick, S., Fiala, J., Hof, V. '. P., Paulusma, D., & Tesar, M. (2013, December). Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree. Presented at Liverpool, UK, 19th International Symposium, FCT 2013

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... Read More about Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree.

Exact algorithms for finding longest cycles in claw-free graphs (2013)
Journal Article
Broersma, H., Fomin, F., Hof van 't, P., & Paulusma, D. (2013). Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica, 65(1), 129 -145. https://doi.org/10.1007/s00453-011-9576-4

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in O*(an)(n) time for some co... Read More about Exact algorithms for finding longest cycles in claw-free graphs.