research
∙
07/05/2023
Exact and Parameterized Algorithms for the Independent Cutset Problem
The Independent Cutset problem asks whether there is a set of vertices i...
share
research
∙
10/13/2022
Computing the Best Case Energy Complexity of Satisfying Assignments in Monotone Circuits
Measures of circuit complexity are usually analyzed to ensure the comput...
research
∙
10/13/2022
Perfect matching cuts partitioning a graph into complementary subgraphs
In Partition Into Complementary Subgraphs (Comp-Sub) we are given a grap...
research
∙
10/13/2022
On the Minimum Cycle Cover problem on graphs with bounded co-degeneracy
In 2021, Duarte, Oliveira, and Souza [MFCS 2021] showed some problems th...
research
∙
09/13/2022
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P_4
An oriented graph is a digraph that does not contain a directed cycle of...
research
∙
08/18/2022
Recognizing well-dominated graphs is coNP-complete
A graph G is well-covered if every minimal vertex cover of G is minimum,...
research
∙
08/08/2022
A note on independent sets in sparse-dense graphs
Sparse-dense partitions was introduced by Feder, Hell, Klein, and Motwan...
research
∙
07/15/2022
A tight quasi-polynomial bound for Global Label Min-Cut
We study a generalization of the classic Global Min-Cut problem, called ...
research
∙
05/02/2022
Taming graphs with no large creatures and skinny ladders
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: i...
research
∙
02/07/2022
Reducing the Vertex Cover Number via Edge Contractions
The CONTRACTION(vc) problem takes as input a graph G on n vertices and t...
research
∙
07/09/2020
Computing the Largest Bond and the Maximum Connected Cut of a Graph
The cut-set ∂(S) of a graph G=(V,E) is the set of edges that have one en...
research
∙
05/04/2020
Reducing graph transversals via edge contractions
For a graph parameter π, the Contraction(π) problem consists in, given a...
research
∙
04/17/2020
Hitting forbidden induced subgraphs on bounded treewidth graphs
For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, fo...
research
∙
04/12/2020
Linear-time Algorithms for Eliminating Claws in Graphs
Since many NP-complete graph problems have been shown polynomial-time so...
research
∙
10/04/2019
Width Parameterizations for Knot-free Vertex Deletion on Digraphs
A knot in a directed graph G is a strongly connected subgraph Q of G wit...
research
∙
10/02/2019
Computing the largest bond of a graph
A bond of a graph G is an inclusion-wise minimal disconnecting set of G,...
research
∙
06/26/2019
The Complexity of Helly-B_1 EPG Graph Recognition
Golumbic, Lipshteyn and Stern defined in 2009 the class of EPG graphs, a...
research
∙
10/18/2018
FPT algorithms to recognize well covered graphs
Given a graph G, let vc(G) and vc^+(G) be the sizes of a minimum and a m...
research
∙
05/02/2018
Maximum cuts in edge-colored graphs
The input of the Maximum Colored Cut problem consists of a graph G=(V,E)...
research
∙
10/21/2017