4 Search Results for "Souza, Uéverton dos Santos"


Document
Reducing the Vertex Cover Number via Edge Contractions

Authors: Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, and Prafullkumar Tale

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
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. [MFCS 2020, 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) ⋅ 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: - 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) ⋅ n^o(k + d) for any function f. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative. - 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. - Contraction(vc) can be solved in time 2^O(d) ⋅ n^{k - d + O(1)}. This XP algorithm improves the one of Lima et al. [MFCS 2020], 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 hand, this shows that when k = d, the problem is FPT parameterized by d (or by k).

Cite as

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, Uéverton S. Souza, and Prafullkumar Tale. Reducing the Vertex Cover Number via Edge Contractions. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{lima_et_al:LIPIcs.MFCS.2022.69,
  author =	{Lima, Paloma T. and dos Santos, Vinicius F. and Sau, Ignasi and Souza, U\'{e}verton S. and Tale, Prafullkumar},
  title =	{{Reducing the Vertex Cover Number via Edge Contractions}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.69},
  URN =		{urn:nbn:de:0030-drops-168671},
  doi =		{10.4230/LIPIcs.MFCS.2022.69},
  annote =	{Keywords: Blocker problems, edge contraction, vertex cover, parameterized complexity}
}
Document
Reducing Graph Transversals via Edge Contractions

Authors: Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, and Uéverton S. Souza

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where π is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection ℋ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in ℋ, which in particular imply that Contraction(π) is co-NP-hard even for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.

Cite as

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau, and Uéverton S. Souza. Reducing Graph Transversals via Edge Contractions. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{lima_et_al:LIPIcs.MFCS.2020.64,
  author =	{Lima, Paloma T. and dos Santos, Vinicius F. and Sau, Ignasi and Souza, U\'{e}verton S.},
  title =	{{Reducing Graph Transversals via Edge Contractions}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{64:1--64:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.64},
  URN =		{urn:nbn:de:0030-drops-127346},
  doi =		{10.4230/LIPIcs.MFCS.2020.64},
  annote =	{Keywords: blocker problem, edge contraction, graph transversal, parameterized complexity, vertex cover, feedback vertex set, odd cycle transversal}
}
Document
Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs

Authors: Ignasi Sau and Uéverton dos Santos Souza

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S ⊆ V(G) such that G⧵ 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) ⋅ n^{𝒪(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^{𝒪(t^{h-2})} for every graph H on h ≥ 3 vertices, and that f_H(t) = 2^{𝒪(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₄}(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 ≤ 2 the problem can be solved in polynomial time; if h ≥ 3, f_H(t) = 2^{Θ(t)} if H is a clique, and f_H(t) = 2^{Θ(t^{h-2})} otherwise.

Cite as

Ignasi Sau and Uéverton dos Santos Souza. Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{sau_et_al:LIPIcs.MFCS.2020.82,
  author =	{Sau, Ignasi and Souza, U\'{e}verton dos Santos},
  title =	{{Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{82:1--82:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.82},
  URN =		{urn:nbn:de:0030-drops-127511},
  doi =		{10.4230/LIPIcs.MFCS.2020.82},
  annote =	{Keywords: parameterized complexity, induced subgraphs, treewidth, hitting subgraphs, dynamic programming, lower bound, Exponential Time Hypothesis}
}
Document
On the Parameterized Complexity of Grid Contraction

Authors: Saket Saurabh, Uéverton dos Santos Souza, and Prafullkumar Tale

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)


Abstract
For a family of graphs 𝒢, the 𝒢-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists F ⊆ E(G) of size at most k such that G/F belongs to 𝒢. Here, G/F is the graph obtained from G by contracting all the edges in F. In this article, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time c^k ⋅ |V(G)|^{{O}(1)}, for this problem. We complement this result by proving that unless ETH fails, there is no algorithm for Grid Contraction with running time c^{o(k)} ⋅ |V(G)|^{{O}(1)}. We also present a polynomial kernel for this problem.

Cite as

Saket Saurabh, Uéverton dos Santos Souza, and Prafullkumar Tale. On the Parameterized Complexity of Grid Contraction. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{saurabh_et_al:LIPIcs.SWAT.2020.34,
  author =	{Saurabh, Saket and Souza, U\'{e}verton dos Santos and Tale, Prafullkumar},
  title =	{{On the Parameterized Complexity of Grid Contraction}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.34},
  URN =		{urn:nbn:de:0030-drops-122810},
  doi =		{10.4230/LIPIcs.SWAT.2020.34},
  annote =	{Keywords: Grid Contraction, FPT, Kernelization, Lower Bound}
}
  • Refine by Author
  • 3 Sau, Ignasi
  • 2 Lima, Paloma T.
  • 2 Souza, Uéverton S.
  • 2 Souza, Uéverton dos Santos
  • 2 Tale, Prafullkumar
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 3 parameterized complexity
  • 2 edge contraction
  • 2 vertex cover
  • 1 Blocker problems
  • 1 Exponential Time Hypothesis
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 3 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail