DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2021.42

Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances

Authors: Gabriel L. Duarte, Mateus de Oliveira Oliveira, and Uéverton S. Souza

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies bounded clique-width, but not vice versa. Problems like Longest Cycle, Longest Path, MaxCut, Edge Dominating Set, and Graph Coloring are fixed-parameter tractable when parameterized by the treewidth, but they cannot be solved in FPT time when parameterized by the clique-width unless FPT = W[1], as shown by Fomin, Golovach, Lokshtanov, and Saurabh [SIAM J. Comput. 2010, SIAM J. Comput. 2014]. For a given problem that is fixed-parameter tractable when parameterized by treewidth, but intractable when parameterized by clique-width, there may exist infinite families of instances of bounded clique-width and unbounded treewidth where the problem can be solved efficiently. In this work, we initiate a systematic study of the parameters co-treewidth (the treewidth of the complement of the input graph) and co-degeneracy (the degeneracy of the complement of the input graph). We show that Longest Cycle, Longest Path, and Edge Dominating Set are FPT when parameterized by co-degeneracy. On the other hand, Graph Coloring is para-NP-complete when parameterized by co-degeneracy but FPT when parameterized by the co-treewidth. Concerning MaxCut, we give an FPT algorithm parameterized by co-treewidth, while we leave open the complexity of the problem parameterized by co-degeneracy. Additionally, we show that Precoloring Extension is fixed-parameter tractable when parameterized by co-treewidth, while this problem is known to be W[1]-hard when parameterized by treewidth. These results give evidence that co-treewidth is a useful width parameter for handling dense instances of problems for which an FPT algorithm for clique-width is unlikely to exist. Finally, we develop an algorithmic framework for co-degeneracy based on the notion of Bondy-Chvátal closure.

Cite as

Gabriel L. Duarte, Mateus de Oliveira Oliveira, and Uéverton S. Souza. Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{duarte_et_al:LIPIcs.MFCS.2021.42,
  author =	{Duarte, Gabriel L. and de Oliveira Oliveira, Mateus and Souza, U\'{e}verton S.},
  title =	{{Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.42},
  URN =		{urn:nbn:de:0030-drops-144828},
  doi =		{10.4230/LIPIcs.MFCS.2021.42},
  annote =	{Keywords: FPT, treewidth, degeneracy, complement graph, Bondy-Chv\'{a}tal closure}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2019.12

Computing the Largest Bond of a Graph

Authors: Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, and Uéverton S. Souza

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract

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\S] of G such that G[S] and G[V\S] are both connected. Given s,t in V(G), an st-bond of G is a bond whose removal disconnects s and t. Contrasting with the large number of studies related to maximum cuts, there are 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 largest st-bond of a graph. Although cuts and bonds are similar, we remark that computing the largest bond of a graph tends to be harder than computing its maximum cut. We show that Largest Bond remains NP-hard even for planar bipartite graphs, and it does not admit a constant-factor approximation algorithm, unless P = NP. We also show that Largest Bond and Largest st-Bond on graphs of clique-width w cannot be solved in time f(w) x n^{o(w)} unless the Exponential Time Hypothesis fails, but they can be solved in time f(w) x n^{O(w)}. In addition, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, but they do not admit polynomial kernels unless NP subseteq coNP/poly.

Cite as

Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, and Uéverton S. Souza. Computing the Largest Bond of a Graph. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{duarte_et_al:LIPIcs.IPEC.2019.12,
  author =	{Duarte, Gabriel L. and Lokshtanov, Daniel and Pedrosa, Lehilton L. C. and Schouery, Rafael C. S. and Souza, U\'{e}verton S.},
  title =	{{Computing the Largest Bond of a Graph}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.12},
  URN =		{urn:nbn:de:0030-drops-114732},
  doi =		{10.4230/LIPIcs.IPEC.2019.12},
  annote =	{Keywords: bond, cut, maximum cut, connected cut, FPT, treewidth, clique-width}
}

Search Results

Documents authored by Duarte, Gabriel L.

Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances

Abstract

Cite as

Computing the Largest Bond of a Graph

Abstract

Cite as

Thanks for your feedback!

Could not send message