Source author record

Uéverton S. Souza

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

Research overview

5works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A note on independent sets in sparse-dense graphs

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 concerning independent sets in graphs having sparse-dense partitions is presented: if a $n$ -vertex graph $G$ admits a sparse-dense partition concerning classes $\mathcal S$ and $\mathcal D$ , where $\mathcal D$ is a subclass of the complement of $K_t$ -free graphs (for some ~ $t$ ), and graphs in $\mathcal S$ can be recognized in polynomial time, then: enumerate all maximal independent sets of $G$ (or find its maximum) can be performed in $n^{O(1)}$ time whenever it can be done in polynomial time for graphs in the class $\mathcal S$ . This result has the following interesting implications: A P versus NP-hard dichotomy for Max. Independent Set on graphs whose vertex set can be partitioned into $k$ independent sets and $\ell$ cliques, so-called $(k, \ell)$ -graphs. concerning the values of $k$ and $\ell$ of $(k, \ell)$ -graphs. A P-time algorithm that does not require $(1,\ell)$ -partitions for determining whether a $(1,\ell)$ -graph $G$ is well-covered. Well-covered graphs are graphs in which every maximal independent set has the same cardinality. The characterization of conflict graph classes for which the conflict version of a P-time graph problem is still in P assuming such classes. Conflict versions of graph problems ask for solutions avoiding pairs of conflicting elements (vertices or edges) described in conflict graphs.

preprint2022arXiv

Hitting forbidden induced subgraphs on bounded treewidth graphs

For a fixed graph $H$ , the $H$ -IS-Deletion problem asks, given a graph $G$ , for the minimum size of a set $S \subseteq V(G)$ such that $G\setminus S$ does not contain $H$ as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph $H$ , the smallest function $f_H(t)$ such that $H$ -IS-Deletion can be solved in time $f_H(t) \cdot n^{O(1)}$ assuming the Exponential Time Hypothesis (ETH), where $t$ and $n$ denote the treewidth and the number of vertices of the input graph, respectively. We show that $f_H(t) = 2^{O(t^{h-2})}$ for every graph $H$ on $h \geq 3$ vertices, and that $f_H(t) = 2^{O(t)}$ if $H$ is a clique or an independent set. We present a number of lower bounds by generalizing a reduction of Cygan et al. [MFCS 2014] for the subgraph version. In particular, we show that when $H$ deviates slightly from a clique, the function $f_H(t)$ suffers a sharp jump: if $H$ is obtained from a clique of size $h$ by removing one edge, then $f_H(t) = 2^{Θ(t^{h-2})}$ . We also show that $f_H(t) = 2^{Ω(t^{h})}$ when $H=K_{h,h}$ , and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function $f_{C_4}(t)$ for the subgraph version. Motivated by Cygan et al. [MFCS 2014], we also consider the colorful variant of the problem, where each vertex of $G$ is colored with some color from $V(H)$ and we require to hit only induced copies of $H$ with matching colors. In this case, we determine, under the ETH, the function $f_H(t)$ for every connected graph $H$ on $h$ vertices: if $h\leq 2$ the problem can be solved in polynomial time; if $h\geq 3$ , $f_H(t) = 2^{Θ(t)}$ if $H$ is a clique, and $f_H(t) = 2^{Θ(t^{h-2})}$ otherwise.

preprint2022arXiv

Recognizing well-dominated graphs is coNP-complete

A graph $G$ is well-covered if every minimal vertex cover of $G$ is minimum, and a graph $G$ is well-dominated if every minimal dominating set of $G$ is minimum. Studies on well-covered graphs were initiated in [Plummer, JCT 1970], and well-dominated graphs were first introduced in [Finbow, Hartnell and Nowakow, AC 1988]. Well-dominated graphs are well-covered, and both classes have been widely studied in the literature. The recognition of well-covered graphs was proved coNP-complete by [Chvátal and Slater, AODM 1993] and by [Sankaranarayana and Stewart, Networks 1992], but the complexity of recognizing well-dominated graphs has been left open since their introduction. We close this complexity gap by proving that recognizing well-dominated graphs is coNP-complete. This solves a well-known open question (c.f. [Levit and Tankus, DM 2017] and [Gözüpek, Hujdurovic and Milanič, DMTCS 2017]), which was first asked in [Caro, Sebő and Tarsi, JAlg 1996]. Surprisingly, our proof is quite simple, although it was a long-standing open problem. Finally, we show that recognizing well-totally-dominated graphs is coNP-complete, answering a question of [Bahad\ir, Ekim, and Gözüpek, AMC 2021].

preprint2022arXiv

Reducing the Vertex Cover Number via Edge Contractions

The CONTRACTION(vc) problem takes as input a graph $G$ on $n$ vertices and two integers $k$ and $d$ , and asks whether one can contract at most $k$ edges to reduce the size of a minimum vertex cover of $G$ by at least $d$ . Recently, Lima et al. [JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, CONTRACTION(vc) admits an XP algorithm running in time $f(d) \cdot n^{O(d)}$ . They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results: 1. CONTRACTION(vc) is W[1]-hard parameterized by $k + d$ . Moreover, unless the ETH fails, the problem does not admit an algorithm running in time $f(k + d) \cdot n^{o(k + d)}$ for any function $f$ . In particular, this answers the open question stated in Lima et al. [JCSS 2021] in the negative. 2. It is NP-hard to decide whether an instance $(G, k, d)$ of CONTRACTION(vc) is a yes-instance even when $k = d$ , hence enhancing our understanding of the classical complexity of the problem. 3. CONTRACTION(vc) can be solved in time $2^{O(d)} \cdot n^{k - d + O(1)}$ . This XP algorithm improves the one of Lima et al. [JCSS 2021], which uses Courcelle's theorem as a subroutine and hence, the $f(d)$ -factor in the running time is non-explicit and probably very large. On the other hard, it shows that when $k=d$ , the problem is FPT parameterized by $d$ (or by $k$ ).

preprint2020arXiv

Computing the Largest Bond and the Maximum Connected Cut of a Graph

The cut-set $\partial(S)$ of a graph $G=(V,E)$ is the set of edges that have one endpoint in $S\subset V$ and the other endpoint in $V\setminus S$ , and whenever $G[S]$ is connected, the cut $[S,V\setminus S]$ of $G$ is called a connected cut. A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$ , i.e., bonds are cut-sets that determine cuts $[S,V\setminus S]$ of $G$ such that $G[S]$ and $G[V\setminus S]$ are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP. Also, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard even for planar bipartite graphs, whereas \textsc{Maximum Cut} is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard on split graphs, and restricted to graphs of clique-width $w$ they can not be solved in time $f(w)\times n^{o(w)}$ unless the Exponential Time Hypothesis fails, but they can be solved in time $f(w)\times n^{O(w)}$ . Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Uéverton S. Souza

Research overview

Is this your work?

5 publications

A note on independent sets in sparse-dense graphs

Hitting forbidden induced subgraphs on bounded treewidth graphs

Recognizing well-dominated graphs is coNP-complete

Reducing the Vertex Cover Number via Edge Contractions

Computing the Largest Bond and the Maximum Connected Cut of a Graph

See the researcher in context

Building this map preview