DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2023.27

Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions

Authors: Bart M. P. Jansen and Bart van der Steenhoven

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract

A kernelization for a parameterized decision problem 𝒬 is a polynomial-time preprocessing algorithm that reduces any parameterized instance (x,k) into an instance (x',k') whose size is bounded by a function of k alone and which has the same yes/no answer for 𝒬. Such preprocessing algorithms cannot exist in the context of counting problems, when the answer to be preserved is the number of solutions, since this number can be arbitrarily large compared to k. However, we show that for counting minimum feedback vertex sets of size at most k, and for counting minimum dominating sets of size at most k in a planar graph, there is a polynomial-time algorithm that either outputs the answer or reduces to an instance (G',k') of size polynomial in k with the same number of minimum solutions. This shows that a meaningful theory of kernelization for counting problems is possible and opens the door for future developments. Our algorithms exploit that if the number of solutions exceeds 2^{poly(k)}, the size of the input is exponential in terms of k so that the running time of a parameterized counting algorithm can be bounded by poly(n). Otherwise, we can use gadgets that slightly increase k to represent choices among 2^{𝒪(k)} options by only poly(k) vertices.

Cite as

Bart M. P. Jansen and Bart van der Steenhoven. Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2023.27,
  author =	{Jansen, Bart M. P. and van der Steenhoven, Bart},
  title =	{{Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.27},
  URN =		{urn:nbn:de:0030-drops-194466},
  doi =		{10.4230/LIPIcs.IPEC.2023.27},
  annote =	{Keywords: kernelization, counting problems, feedback vertex set, dominating set, protrusion decomposition}
}

Search Results

Documents authored by van der Steenhoven, Bart

Kernelization for Counting Problems on Graphs: Preserving the Number of Minimum Solutions

Abstract

Cite as

Thanks for your feedback!

Could not send message