检索结果-内蒙古大学图书馆

FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds

Proceedings of the ACM on Management of Data 2025年第1期3卷 1-25页

作者： Aaron Huber Oliver Kennedy Atri Rudra Zhuoyue Zhao Su Feng Boris Glavic University at Buffalo Buffalo USA Nanjing Tech University Nanjing China University of Illinois Chicago Illinois USA

Probabilistic databases (PDBs) provide users with a principled way to query data that is incomplete or imprecise. In this work, we study computing expected multiplicities of query results over probabilistic databases under bag semantics which has PTIME data complexity. However, does this imply that bag probabilistic databases are practical? We strive to answer this question from both a theoretical as well as a systems perspective. We employ concepts from fine-grained complexity to demonstrate that exact bag probabilistic query processing is fundamentally less efficient than deterministic bag query evaluation, but that fast approximations are possible by sampling monomials from a circuit representation of a result tuple's lineage. A remaining issue, however, is that constructing such circuits, while in PTIME, can nonetheless have significant overhead. To avoid this cost, we utilize approximate query processing techniques to directly sample monomials without materializing lineage upfront. Our implementation in FastPDB provides accurate anytime approximation of probabilistic query answers and scales to datasets orders of magnitude larger than competing methods.

关键词： approximate query processing fine-grained complexity lineage polynomials parameterized complexity probabilistic data model

来源：评论

学校读者我要写书评

暂无评论

An O*(2.619^k) algorithm for 4-PATH VERTEX COVER

引用

DISCRETE APPLIED MATHEMATICS 2021年 291卷 1-14页

作者： Tsur, Dekel Ben Gurion Univ Negev Beer Sheva Israel

In the 4-PATH VERTEX COVER problem, the input is an undirected graph G and an integer k. The goal is to decide whether there is a set S of vertices of size at most k such that every path with 4 vertices in G contains at least one vertex of S. In this paper we give a parameterized algorithm for 4-PATH VERTEX COVER whose time complexity is 2.619(k). n(O)(1), where n denotes the number of vertices of the input graph. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity Iterative compression Branching rules

来源：评论

学校读者我要写书评

暂无评论

KERNELIZATION OF WHITNEY SWITCHES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第2期35卷 1298-1336页

作者： Fomin, Fedor, V Golovach, Petr A. Univ Bergen Dept Informat N-5020 Bergen Norway

A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs G and H are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if G can be transformed into H by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney's theorem: Given two 2-isomorphic graphs, can we transform one into another by applying at most k Whitney switches? This problem is already NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size O(k) and thus is fixed-parameter tractable when parameterized by k

关键词： Whitney switch 2-isomorphism parameterized complexity kernelization

来源：评论

学校读者我要写书评

暂无评论

Multistage graph problems on a global budget

引用

THEORETICAL COMPUTER SCIENCE 2021年 868卷 46-64页

作者： Heeger, Klaus Himmel, Anne-Sophie Kammer, Frank Niedermeier, Rolf Renken, Malte Sajenko, Andrej TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany Univ Appl Sci Mittelhessen THM Giessen Germany

Time-evolving or temporal graphs gain more and more popularity when exploring complex networks. In this context, the multistage view on computational problems is among the most natural frameworks. Roughly speaking, herein one studies the different (time) layers of a temporal graph (effectively meaning that the edge set may change over time, but the vertex set remains unchanged), and one searches for a solution of a given graph problem for each layer. The twist in the multistage setting is that the solutions found must not differ too much between subsequent layers. We relax on this already established notion by introducing a global instead of the local budget view studied so far. More specifically, we allow for few disruptive changes between subsequent layers but request that overall, that is, summing over all layers, the degree of change is moderate. Studying several classical graph problems (both NP-hard and polynomial-time solvable ones) from a parameterized complexity angle, we encounter both fixed-parameter tractability and parameterized hardness results. Surprisingly, we find that sometimes the global multistage versions of NP-hard problems such as VERTEX COVER turn out to be computationally more tractable than the ones of polynomial-time solvable problems such as MATCHING. In addition to time complexity, we also analyze the space efficiency of our algorithms. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Temporal graphs Time-varying graphs NP-hardness parameterized complexity Multivariate algorithmics Space complexity

来源：评论

学校读者我要写书评

暂无评论

FPT approximation and subexponential algorithms for covering few or many edges

引用

INFORMATION PROCESSING LETTERS 2024年 185卷

作者： Fomin, Fedor V. Golovach, Petr A. Inamdar, Tanmay Koana, Tomohiro Univ Bergen Dept Informat N-5004 Bergen Norway Indian Inst Technol Jodhpur 342030 India Tech Univ Berlin Algorithm & Computat Complex Berlin Germany

We study the alpha-Fixed Cardinality Graph Partitioning (alpha-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph G, two numbers k,p and 0 <= alpha <= 1, the question is whether there is a set S subset of V of size k with a specified coverage function cov(alpha)(S) at least p (or at most p for the minimization version). The coverage function cov(alpha)(center dot) counts edges with exactly one endpoint in S with weight alpha and edges with both endpoints in S with weight 1-alpha. alpha-FCGP generalizes a number of fundamental graph problems such as Densest k-Subgraph, Max k-Vertex Cover, and Max (k, n-k)-CUT. A natural question in the study of alpha-FCGP is whether the algorithmic results known for its special cases, like Max k-VERTEX COVER, could be extended to more general settings. One of the simple but powerful methods for obtaining parameterized approximation [Manurangsi, SOSA 2019] and subexponential algorithms [Fomin et al. IPL 2011] for Max k-Vertex Cover is based on the greedy vertex degree orderings. The main insight of our work is that the idea of greedy vertex degree ordering could be used to design fixed-parameter approximation schemes (FPT-AS) for alpha>0 and subexponential-time algorithms for the problem on apex-minor free graphs for maximization with alpha > 1/3 and minimization with alpha < 1/3.(4)

关键词： parameterized complexity Approximation algorithms Partial vertex cover

来源：评论

学校读者我要写书评

暂无评论

Constrained hitting set problem with intervals: Hardness, FPT and approximation algorithms

引用

THEORETICAL COMPUTER SCIENCE 2024年 990卷

作者： Acharyya, Ankush Keikha, Vahideh Majumdar, Diptapriyo Pandit, Supantha Natl Inst Technol Dept Comp Sci & Engn Durgapur India Czech Acad Sci Inst Comp Sci Prague Czech Republic Indraprastha Inst Informat Technol Delhi New Delhi India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India

We study a constrained version of the GEOMETRIC HITTING SET problem where we are given a set of points, partitioned into pairwise disjoint subsets, and a set of intervals. The objective is to hit all the intervals with a minimum number of points such that if we select a point from a subset, we must select all the points from that subset. We consider two special cases of the problem where each subset can have at most 2 and 3 points. If each subset contains at most 2 points and the intervals are disjoint, we show that the problem admits a polynomial -time algorithm. On the contrary, if each subset contains at most t points, where t >= 2, and the intervals are overlapping, we show that the problem becomes NP -Hard. Further, when each subset contains at most t points where t >= 3, and the intervals are disjoint, we prove that the problem is NP -Hard, and we provide two constant factor approximation algorithms for this problem. We also study the problem from the parameterized complexity perspective. If the intervals are disjoint, then we prove that the problem is in FPT when parameterized by the size of the solution. We also complement this result by giving a lower bound in the size of the kernel for disjoint intervals, and we also provide a polynomial kernel when the size of all subsets is bounded by a constant.

关键词： Computational complexity Approximation algorithms parameterized complexity Kernelization Set cover conjecture

来源：评论

学校读者我要写书评

暂无评论

Computational complexity of normalizing constants for the product of determinantal point processes

引用

THEORETICAL COMPUTER SCIENCE 2024年 997卷

作者： Matsuoka, Tatsuya Ohsaka, Naoto NEC Corp Ltd Minato City Japan CyberAgent Inc Shibuya Japan

We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant, which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: Computing S.. det(....,..).. exactly for every (fixed) positive even integer.. is UP- hard and Mod3P-hard, which gives a negative answer to an open question posed by Kulesza and Taskar [51]. S.. det(....,..) det(....,..) det(....,..) is NP- hard to approximate within a factor of 2.(|.|1-..) or 2. (..1/..) for any.. > 0, where |.| is the input size and.. is the order of the input matrix. This result is stronger than the #P-hardness for the case of two matrices derived by Gillenwater [36]. There exists a...(..)...(1)- time algorithm for computing S.. det(....,..) det(....,..), where.. is the maximum rank of.. and.. or the treewidth of the graph formed by nonzero entries of.. and... Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixedparameter tractable algorithms given a matrix.. of treewidth..: We can compute a 2.. 2..-1 -approximation to S.. det(....,..).. for any fractional number.. > 1 in...(....)...(1) time. We can find a 2v.. -approximation to unconstrained maximum a posteriori inference in...(..v..)...(1) time.

关键词： Determinantal point process Partition function Hardness of approximation Fixed-parameter tractability parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Grouped domination parameterized by vertex cover, twin cover, and beyond

引用

THEORETICAL COMPUTER SCIENCE 2024年 996卷

作者： Hanaka, Tesshu Ono, Hirotaka Otachi, Yota Uda, Saeki Kyushu Univ Fukuoka Japan Nagoya Univ Nagoya Japan

A dominating set S of graph G is called an r-grouped dominating set if S can be partitioned into S-1,S-2, . . . ,S-K such that the size of each unit S is r and the subgraph of G induced by S is connected. The concept of r-grouped dominating sets generalizes several well-studied variants of dominating sets with requirements for connected component sizes, such as the ordinary dominating sets (r = 1), paired dominating sets (r = 2), and connected dominating sets (r is arbitrary and k = 1). In this paper, we investigate the computational complexity of r-Grouped Dominating Set, which is the problem of deciding whether a given graph has an r-grouped dominating set with at most k units. For general r, r-Grouped Dominating Set is hard to solve in various senses because the hardness of the connected dominating set is inherited. We thus focus on the case in which r is a constant or a parameter, but we see that r-Grouped Dominating Set for every fixed r > 0 is still hard to solve. From the observations about the hardness, we consider the parameterized complexity concerning well-studied graph structural parameters. We first see that r-Grouped Dominating Set is fixed-parameter tractable for r and treewidth, which is derived from the fact that the condition of r-grouped domination for a constant r can be represented as monadic second-order logic (MSO2). This fixed-parameter tractability is good news, but the running time is not practical. We then design an O*(min{(2(r+1)),(2)(2)})-time algorithm for general r >= 2, where tau is the twin cover number, which is a parameter between vertex cover number and clique-width. For paired dominating set and trio dominating set, i.e., r is an element of {2,3}, we can speed up the algorithm, whose running time becomes O*((r+1)). We further argue the relationship between FPT results and graph parameters, which draws the parameterized complexity landscape of r-Grouped Dominating Set.

关键词： Dominating set Paired dominating set parameterized complexity Graph structural parameters

来源：评论

学校读者我要写书评

暂无评论

Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts 1

引用

48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Brand, Cornelius Ceylan, Esra Robert, Ganian B. Hatschka, Christian Korchemna, Viktoriia TU Wien Algorithms & Complex Grp Vienna Austria

ISBN: (数字)9783031159145

ISBN: (纸本)9783031159145;9783031159138

Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for N P-hard graph problems. For problems that are W[1]-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of treewidth that is based on edge cuts instead of vertex separators. While tree-cut width has been coined as such an analogue of treewidth for edge cuts, its algorithmic applications have often led to disappointing results: out of twelve problems where one would hope for fixed-parameter tractability parameterized by an edge-cut based analogue to treewidth, eight were shown to be W[1]-hard parameterized by tree-cut width. As our main contribution, we develop an edge-cut based analogue to treewidth called edge-cut width. Edge-cut width is, intuitively, based on measuring the density of cycles passing through a spanning tree of the graph. Its benefits include not only a comparatively simple definition, but mainly that it has interesting algorithmic properties: it can be computed by a fixed-parameter algorithm, and it yields fixed-parameter algorithms for all the aforementioned problems where tree-cut width failed to do so.

关键词： tree-cut width parameterized complexity graph parameters

来源：评论

学校读者我要写书评

暂无评论

An Algorithmic Framework for Locally Constrained Homomorphisms 1

引用

48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Bulteau, Laurent Konrad, K. Dabrowski B. Kohler, Noleen Ordyniak, Sebastian Paulusma, Daniel Univ Gustave Eiffel CNRS LIGM Champs Sur Marne France Newcastle Univ Sch Comp Newcastle Upon Tyne England PSL Univ Univ Paris Dauphine CNRS LAMSADE Paris France Univ Leeds Sch Comp Leeds England Univ Durham Dept Comp Sci Durham England

ISBN: (数字)9783031159145

ISBN: (纸本)9783031159145;9783031159138

A homomorphism phi from a guest graph G to a host graph H is locally bijective, injective or surjective if for every u is an element of V(G), the restriction of phi to the neighbourhood of u is bijective, injective or surjective, respectively. The corresponding decision problems, LBHOM, LIHOM and LSHOM, are well studied both on general graphs and on special graph classes. We prove a number of new FPI, W[1]-hard and para-NP-complete results by considering a hierarchy of parameters of the guest graph G. For our FPI results, we do this through the development of a new algorithmic framework that involves a general ILP model. To illustrate the applicability of the new framework, we also use it to prove FPI results for the ROLE ASSIGNMENT problem, which originates from social network theory and is closely related to locally surjective homomorphisms.

关键词： (locally constrained) graph homomorphism parameterized complexity fracture number

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：