4 citations · 12 across the 12 of their papers we have counts for
12 papers · 1 filter
A tight quasi-polynomial bound for Global Label Min-Cut
Lars Jaffke, Paloma T. Lima, Tomáš Masařík +2
We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (o…
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
Meike Hatzel, Lars Jaffke, Paloma T. Lima +4
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph , pairs of ve…
Reducing the Vertex Cover Number via Edge Contractions
Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +2
The CONTRACTION(vc) problem takes as input a graph on vertices and two integers and , and asks whether one can contract at most edges to reduce the size of a min…
Graph Square Roots of Small Distance from Degree One Graphs
Petr A. Golovach, Paloma T. Lima, Charis Papadopoulos
Given a graph class , the task of the -Square Root problem is to decide, whether an input graph has a square root from . We are inter…
Structural Parameterizations of Clique Coloring
Lars Jaffke, Paloma T. Lima, Geevarghese Philip
A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the C…
Reducing graph transversals via edge contractions
Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +1
For a graph invariant , the Contraction() problem consists in, given a graph and two positive integers , deciding whether one can contract at most edges of t…
b-Coloring Parameterized by Clique-Width
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph clas…
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
Lars Jaffke, Paloma T. Lima
A -coloring of a graph is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b…
Classifying k-Edge Colouring for H-free Graphs
Esther Galby, Paloma T. Lima, Daniel Paulusma +1
A graph is -free if it does not contain an induced subgraph isomorphic to . For every integer and every graph , we determine the computational complexity of -Edge C…
Parameterized Aspects of Strong Subgraph Closure
Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis +2
Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized…
Finding Connected Secluded Subgraphs
Petr A. Golovach, Pinar Heggernes, Paloma Lima +1
Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough…
Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
Petr A. Golovach, Pinar Heggernes, Dieter Kratsch +2
Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem i…