首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Dynamic Kernels for Hitting Sets and Set Packing
  • 本地全文:下载
  • 作者:Max Bannach ; Zacharias Heinrich ; Rüdiger Reischuk
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-25
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Computing kernels for the hitting set problem (the problem of finding a size- k set that intersects each hyperedge of a hypergraph) is a well-studied computational problem. For hypergraphs with m hyperedges, each of size at most~ d , the best algorithms can compute kernels of size O ( k d ) in time O ( 2 d m ) . In this paper we generalize the task to the dynamic setting where hyperedges may be continuously added and deleted and we always have to keep track of a hitting set kernel (including moments when no size- k hitting set exists). We present a deterministic solution, based on a novel data structure, that needs worst-case time O ( 3 d ) for updating the kernel upon hyperedge inserts and time~ O ( 5 d ) for updates upon deletions -- thus nearly matching the time O ( 2 d ) needed by the best static algorithm per hyperedge. As a novel technical feature, our approach does not use the standard replace-sunflowers-by-their-cores methodology, but introduces a generalized concept that is actually easier to compute and that allows us to achieve a kernel size of d i =0 k i rather than the typical size d ! k d resulting from the Sunflower Lemma. We also show that our approach extends to the dual problem of finding packings in hypergraphs (the problem of finding k pairwise disjoint hyperedges), albeit with a slightly larger kernel size of d i =0 d i ( k − 1 ) i .

  • 关键词:dynamic data structures ; dynamic graph algorithms ; FPT algorithms ; Hitting Set ; hypergraph ; kernelization ; Matching Problem ; set packing ; Vertex Cover
国家哲学社会科学文献中心版权所有