Almost optimal query algorithm for hitting set using a subset query
Almost optimal query algorithm for hitting set using a subset query
复制标题
DOI：
10.1016/j.jcss.2023.02.002
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Arijit Bishnu;Arijit Ghosh;Sudeshna Kolay;Gopinath Mishra;Saket Saurabh
中科院分区：
文献类型：
--
作者：
Arijit Bishnu;Arijit Ghosh;Sudeshna Kolay;Gopinath Mishra;Saket Saurabh
在本文中，我们专注于击中集，在组合优化的基本问题，通过透镜的次线性时间算法。在给定通过查询模型中的子集查询预言机访问超图的条件下，给出了具有几乎紧参数化查询复杂度的击中集的次线性时间算法。在参数化查询复杂度中，我们根据参数k（命中集的大小）估计对oracle的查询次数。本文中使用的子集查询预言机称为广义d-部独立集查询预言机（GPIS），它是由Bishnu等人提出的。（ISAAC'18）。GPIS是由Beame等人提出的二分独立集查询oracle（BIS）的超图的推广。(ITCS'18和TALG'20）用于估计图中的边的数目。自从引入GPIS查询Oracle以来，Dell等人已经独立地使用它来估计超边的数量。(SODA'20和SICOMP'22）和Bhattacharya et al.（STACS'22），并估计在一个图形中的三角形的数量由Bhattacharya等人。（ISAAC'19和TOCS'21）。形式上，GPIS定义如下：对于d-一致超图H，GPIS oracle将H中顶点的d个两两不相交的非空子集A1，.，Ad作为输入，并回答H中是否存在与每个集合Ai相交的超边，其中i∈{1，2，.，d}。当d= 2时，GPIS oracle只不过是BIS oracle。我们表明，d-击中集，击中集的d-一致超图的问题，可以解决使用O d（k d log n）GPIS查询。此外，我们还证明了d-Hitting-Set的决策版本d-Decision-Hitting-Set可以用O <$d（min <${kdlogn，k2 d2}）GPIS查询求解.我们用一个几乎匹配的参数化下界来补充这些参数化上界，该下界指出任何求解d-决策命中集的算法都需要Ω（（k+ d d））GPIS查询。
In this paper, we focus on Hitting-Set, a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity, we estimate the number of queries to the oracle based on the parameter k, the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d-partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al.(ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al.(ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al.(SODA'20 and SICOMP'22) and Bhattacharya et al.(STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al.(ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1,…, A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i, where i∈{1, 2,…, d}. For d= 2, the GPIS oracle is nothing but BIS oracle. We show that d-Hitting-Set, the hitting set problem for d-uniform hypergraphs, can be solved using O˜ d (k d log n) GPIS queries. Additionally, we also showed that d-Decision-Hitting-Set, the decision version of d-Hitting-Set can be solved with O˜ d (min{k d log n, k 2 d 2}) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d-Decision-Hitting-Set requires Ω ((k+ d d)) GPIS queries.