Agrawal, Akanksha ;
Biswas, Arindam ;
Bonnet, Édouard ;
Brettell, Nick ;
Curticapean, Radu ;
Marx, Dániel ;
Miltzow, Tillmann ;
Raman, Venkatesh ;
Saurabh, Saket
Parameterized Streaming Algorithms for MinOnes dSAT
Abstract
In this work, we initiate the study of the MinOnes dSAT problem in the parameterized streaming model. An instance of the problem consists of a dCNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the readwrite memory available to the algorithm is O(f(k) log n) (f: N > N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k.
We design a (k + 1)pass parameterized streaming algorithm that solves MinOnes dSAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^kpass algorithm that uses space O(k log n). We also design a streaming kernelization for MinOnes 2SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses.
To complement these positive results, we show that any kpass algorithm for or MinOnes dSAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned.
In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1pass parameterized streaming algorithms for Vertex Cover (a restriction of MinOnes 2SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1pass streaming algorithm for MinOnes dSAT requires space Omega(n). This excludes the possibility of a 1pass parameterized streaming algorithm for the problem. Additionally, we show that any ppass algorithm for the problem requires space Omega(n/p).
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs:2019:11570,
author = {Akanksha Agrawal and Arindam Biswas and {\'E}douard Bonnet and Nick Brettell and Radu Curticapean and D{\'a}niel Marx and Tillmann Miltzow and Venkatesh Raman and Saket Saurabh},
title = {{Parameterized Streaming Algorithms for MinOnes dSAT}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {8:18:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771313},
ISSN = {18688969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11570},
URN = {urn:nbn:de:0030drops115708},
doi = {10.4230/LIPIcs.FSTTCS.2019.8},
annote = {Keywords: min, ones, sat, dsat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter}
}
04.12.2019
Keywords: 

min, ones, sat, dsat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter 
Seminar: 

39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Issue date: 

2019 
Date of publication: 

04.12.2019 