4 citations · 6 across the 10 of their papers we have counts for
17 papers
Sparse vertex cutsets and the maximum degree
Stéphane Bessy, Johannes Rauch, Dieter Rautenbach +1
We show that every graph of maximum degree and sufficiently large order has a vertex cutset of order at most that induces a subgraph of maximum degree at mos…
Computing the Best Case Energy Complexity of Satisfying Assignments in Monotone Circuits
Janio Carlos Nascimento Silva, Uéverton S. Souza
Measures of circuit complexity are usually analyzed to ensure the computation of Boolean functions with economy and efficiency. One of these measures is energy complexity, which is…
Perfect matching cuts partitioning a graph into complementary subgraphs
Diane Castonguay, Erika M. M. Coelho, Hebert Coelho +2
In Partition Into Complementary Subgraphs (Comp-Sub) we are given a graph , and an edge set property , and asked whether can be decomposed into two graphs, and…
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of
Linda Cook, Tomáš Masařík, Marcin Pilipczuk +2
An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph is -free if does not contain as an induced sub(di)graph. The…
A note on independent sets in sparse-dense graphs
Uéverton S. Souza
Sparse-dense partitions was introduced by Feder, Hell, Klein, and Motwani [STOC 1999, SIDMA 2003] as a tool to solve partitioning problems. In this paper, the following result conc…
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…
Taming graphs with no large creatures and skinny ladders
Jakub Gajarský, Lars Jaffke, Paloma T. Lima +4
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class there exists a constant such that no member of $\mathcal{G}…
On the Parameterized Complexity Of Grid Contraction
Saket Saurabh, Uéverton dos Santos Souza, Prafullkumar Tale
For a family of graphs , the -\textsc{Contraction} problem takes as an input a graph and an integer , and the goal is to decide if there exists $F…
Computing the Largest Bond and the Maximum Connected Cut of a Graph
Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka +6
The cut-set of a graph is the set of edges that have one endpoint in and the other endpoint in , and whenever is connected…
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…
Width Parameterizations for Knot-free Vertex Deletion on Digraphs
Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro +2
A knot in a directed graph is a strongly connected subgraph of with at least two vertices, such that no vertex in is an in-neighbor of a vertex in $V(G)\setminus…
Computing the largest bond of a graph
Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa +2
A bond of a graph is an inclusion-wise minimal disconnecting set of , i.e., bonds are cut-sets that determine cuts of such that and $G[V\setmin…
Maximum cuts in edge-colored graphs
Luerbio Faria, Sulamita Klein, Ignasi Sau +2
The input of the Maximum Colored Cut problem consists of a graph with an edge-coloring and a positive integer , and the question is wheth…
On the Computational Complexity of the Bipartizing Matching Problem
Carlos V. G. C. Lima, Dieter Rautenbach, Uéverton S. Souza +1
We study the problem of determining whether a given graph~ admits a matching~ whose removal destroys all odd cycles of~ (or equivalently whether~ is bipartite).…
Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
Fábio Protti, Uéverton S. Souza
A graph is {\em matching-decyclable} if it has a matching such that is acyclic. Deciding whether is matching-decyclable is an NP-complete problem even if is 2…
A general framework for path convexities
João Vinicius C. Thompson, Loana T. Nogueira, Fábio Protti +3
In this work we deal with the so-called path convexities, defined over special collections of paths. For example, the collection of the shortest paths in a graph is associated with…
Graphs in which some and every maximum matching is uniquely restricted
Lucia Draque Penso, Dieter Rautenbach, Ueverton dos Santos Souza
A matching in a graph is uniquely restricted if there is no matching in that is distinct from but covers the same vertices as . Solving a problem posed by G…