DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2020.9

New Algorithms for Mixed Dominating Set

Authors: Louis Dublois, Michael Lampis, and Vangelis Th. Paschos

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract

A mixed dominating set is a set of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for MDS, resolving some open questions. In particular, we settle the problem’s complexity parameterized by treewidth and pathwidth by giving an algorithm running in time O^*(5^{tw}) (improving the current best O^*(6^{tw})), and a lower bound showing that our algorithm cannot be improved under the SETH, even if parameterized by pathwidth (improving a lower bound of O^*((2-ε)^{pw})). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve the best known FPT algorithm for this problem, from O^*(4.172^k) to O^*(3.510^k), and the best known exact algorithm, from O^*(2ⁿ) and exponential space, to O^*(1.912ⁿ) and polynomial space.

Cite as

Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. New Algorithms for Mixed Dominating Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dublois_et_al:LIPIcs.IPEC.2020.9,
  author =	{Dublois, Louis and Lampis, Michael and Paschos, Vangelis Th.},
  title =	{{New Algorithms for Mixed Dominating Set}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.9},
  URN =		{urn:nbn:de:0030-drops-133127},
  doi =		{10.4230/LIPIcs.IPEC.2020.9},
  annote =	{Keywords: FPT Algorithms, Exact Algorithms, Mixed Domination}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2020.3

(In)approximability of Maximum Minimal FVS

Authors: Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract

We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: Maximum Minimal Vertex Cover, for which the best achievable approximation ratio is √n, and Upper Dominating Set, which does not admit any n^{1-ε} approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Max Min FVS with a ratio of O(n^{2/3}), as well as a matching hardness of approximation bound of n^{2/3-ε}, improving the previous known hardness of n^{1/2-ε}. Along the way, we also obtain an O(Δ)-approximation and show that this is asymptotically best possible, and we improve the bound for which the problem is NP-hard from Δ ≥ 9 to Δ ≥ 6. Having settled the problem’s approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r, produces an r-approximate solution in time n^O(n/r^{3/2}). This time-approximation trade-off is essentially tight: we show that under the ETH, for any ratio r and ε > 0, no algorithm can r-approximate this problem in time n^{O((n/r^{3/2})^{1-ε})}, hence we precisely characterize the approximability of the problem for the whole spectrum between polynomial and sub-exponential time, up to an arbitrarily small constant in the second exponent.

Cite as

Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos. (In)approximability of Maximum Minimal FVS. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dublois_et_al:LIPIcs.ISAAC.2020.3,
  author =	{Dublois, Louis and Hanaka, Tesshu and Khosravian Ghadikolaei, Mehdi and Lampis, Michael and Melissinos, Nikolaos},
  title =	{{(In)approximability of Maximum Minimal FVS}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.3},
  URN =		{urn:nbn:de:0030-drops-133477},
  doi =		{10.4230/LIPIcs.ISAAC.2020.3},
  annote =	{Keywords: Approximation Algorithms, ETH, Inapproximability}
}

Search Results

Documents authored by Dublois, Louis

New Algorithms for Mixed Dominating Set

Abstract

Cite as

(In)approximability of Maximum Minimal FVS

Abstract

Cite as

Thanks for your feedback!

Could not send message