CS Paper Radar

The Complexity of Computing Class Probabilities in BID Probabilistic Databases

Sotiris Kanellopoulos, Ioannis Koutras, Aris Pagourtzis

cs.DS ·submitted 2026-09-18 02:42 UTC · v1
theory

Abstract

We study the problem of computing class probabilities in block-independent disjoint (BID) probabilistic databases. Given the probability with which each block in the database realizes each feasible tuple type, the goal is to compute the probability of a class of worlds specified by a given tuple multiplicity vector, thus grouping together worlds with the same bag (multiset) of realized tuple types. For this problem, we prove $\#\mathsf{P}$-hardness even for very restricted and structured inputs. On the other hand, we show that it admits an FPRAS, as well as $\mathsf{XP}$-time algorithms parameterized by the number of tuple types and the treewidth of an incidence graph modeling the connections between blocks and tuples. Finally, we show that augmenting the problem with certain compatibility constraints between block realizations renders it $\#\mathsf{XLP}$- and $\#\mathsf{XALP}$-hard parameterized by pathwidth and treewidth respectively, ruling out $\mathsf{FPT}$ algorithms under standard assumptions. We leave as an open question whether this also holds in the absence of compatibility constraints.

Closest papers

Nearest neighbours by meaning across the whole index.

Accumulating Pruning Constraints: New Exact Polynomial-Space Algorithms for Max 2-SAT

cs.DS cs.AI ·2026-10-29 ·Konstantin Kutzkov
code/data similarity 0.63
Abstract · Project folder with Lean verification: https://github.com/konstantinkutzkov/max-2-sat-arxiv

We present deterministic polynomial-space algorithms that solve Max 2-SAT on $n$ variables exactly in time $\Ostar(2^{(1-γ)n})$, for a fixed $γ>0$, on several classes of instances whose clause density may grow with $n$. Our main tool extends the classic DPLL branching algorithm. When the search gives a variable its less promising value, comparing the two values of the variable yields a pruning constraint that is satisfied by some optimal assignment. Accumulating these constraints along each branch prunes all but an exponentially small fraction of the assignments. The classes are formulas with many biased variables, semirandom 2-CNF formulas, and Max-Cut on regular expander graphs and on graphs generated by a stochastic block model. In a semirandom formula, the pairs of variables that may share a clause are arbitrary, and the clauses on these pairs are random. For semirandom formulas and block-model graphs, the algorithms are still exact on every input, and the time bound holds with high probability over the input. To our knowledge, these are the first polynomial-space algorithms with such a running time for nontrivial classes of dense Max 2-SAT instances. Beyond these classes, the pruning constraints can be added to any branching algorithm for Max 2-SAT, and we expect them to be of practical relevance for general formulas, in particular for sparse ones, where each constraint involves only a few variables.

0.31

Path Length Existence Problems in Bounded-Treewidth Probabilistic Graphs

cs.DB cs.CC ·2026-10-13 ·Antoine Amarilli, Mikaël Monet, Harshul Sagar
hot direction similarity 0.63
Abstract · 42 pages

We consider the problem of computing the probability of existence of a source-to-target path or walk satisfying a given length constraint in an input probabilistic graph. The length constraints we consider can require the length to be at least $\ell$, at most $\ell$, or exactly $\ell$, for $\ell$ a target length given as input. The probabilistic graphs that we consider are directed graphs where each edge is annotated with an independent probability of existence. As this task is generally intractable (#P-hard), we aim for algorithms applying to input graphs that are assumed to be of bounded treewidth. We classify the complexity landscape of these problems: - We give an XP algorithm parameterised by treewidth to compute the probability that an input probabilistic graph contains a source-to-target path/walk of length $\geq \ell$, and do the same for a path/walk of length $\leq \ell$. - We show that the four problems mentioned in the last item are W[1]-hard parameterised by pathwidth (hence not FPT under the standard assumption that FPT$\neq$W[1]). This is in contrast to the case of non-probabilistic graphs, where the corresponding problems were known to be FPT parameterised by treewidth; and to the connectivity problem (and more generally MSO evaluation) on probabilistic graphs, where the same was known. - Surprisingly, we show that it is #P-hard to compute the probability that an input graph contains a source-to-target path/walk of length exactly $\ell$, even on graphs of pathwidth $2$. By contrast, all our problems are tractable on graphs of treewidth $1$. - Last, we investigate the complexity of our problems when the edges can carry weights. This causes all our problems to become #P-hard already on pathwidth-2 graphs, and causes specifically the ``exactly $\ell$'' walk problem to be #P-hard even on pathwidth-1 graphs.

0.32

Approximating Independent Sets Using Additive Combinatorics

cs.DS cs.CCmath.CO ·2026-10-18 ·Shachar Lovett
published similarity 0.61
Abstract

We give a deterministic quasi-polynomial time algorithm for approximating the largest independent set in a graph. We show that if an $N$-vertex graph contains an independent set of size $2^{-t} N$, then we can find an independent set of size $2^t$ in quasi-polynomial time, for all $t$ up to a constant factor of $(\log N)^{1/3}$. This gives an approximation factor of $N / \exp((\log N)^{1/3})$, which has the same shape as known hardness results for quasi-polynomial time algorithms, up to a different exponent of the logarithm. The algorithm builds on a structural principle: a graph containing a large independent set must also contain a large sparse structured set, and such a set can be found efficiently. A greedy algorithm then extracts an independent set from it. Our proof draws on tools in additive combinatorics, in particular spreadness and sifting, to obtain the combinatorial structural results. We then convert these to efficient algorithms using pseudo-marginals obtained by semidefinite programming.

0.60

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth

cs.DS cs.CC ·2026-11-12 ·Jakob Greilhuber, Dániel Marx, George Osipov, Marta Piecyk, Paweł Rzążewski +1 more
similarity 0.58
Abstract · The abstract has been truncated for arXiv

We consider valued constraint satisfaction problems (VCSPs) with a fixed finite domain $D$ and a fixed finite constraint language $Γ$, in the setting where $Γ$ contains all crisp unary constraints (called hard lists) and the remaining cost functions are finite-valued. We call such a language a finite-valued hard-list language. Let $c_Γ$ be the size of the largest set $S\subseteq D$ such that $Γ$ can express (using the usual VCSP closure operations) a binary disequality function on elements of $S$. Our main result tightly connects the complexity of the problem parameterized by treewidth to this value $c_Γ$. (1) The problem can be solved in time $(c_Γ)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ when given an instance $I$ with a tree decomposition $\mathcal{T}$ of width $\mathsf{tw}$ of the primal graph of $I$. (2) If $c_Γ\geq 2$, there is no such algorithm solving the problem in time $(c_Γ- \varepsilon)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ for any $\varepsilon > 0$, unless the Primal Treewidth SETH (and hence CNF-SETH) fails. In particular, this gives a far-reaching generalization of a similar result of Esmer et al. [ESA 2024] on the optimization version of list homomorphism for graphs.

0.23

Fortune's Bounty: Taming Complexity by Trimming Trees --- A Hands-On Problem-Solving Experience in Advanced Complexity Suitable for Introductory Students

cs.CC cs.CY ·2026-08-13 ·Kimberly Fluet, Lane A. Hemaspaandra, Christopher M. Homan
theory similarity 0.58
Abstract · 22 pages; 1 figure

This article provides an assignment designed to let undergraduate students who have completed an undergraduate CS1/CS2 sequence try to themselves, in groups, prove Fortune's Theorem. (Fortune's Theorem states that if the complement of the Boolean satisfiability problem polynomial-time reduces to a sparse set, then the Boolean satisfiability problem is polynomial-time computable. The assignment does not assume that students have previously seen the Boolean satisfiability problem, polynomial-time reductions, or sparse sets. Rather, it teaches those within the assignment. Note: Reworded into the technical vocabulary of complexity theory, Fortune's Theorem states that no sparse set is coNP-hard unless P=NP. Fortune's Theorem was a major advance in the understanding of the relationship between hardness and density.) We provide both the assignment handout (as the main body of this report plus Appendix A) and a solution to the assignment (as Appendix B, which would of course not be made available to the students until after they had handed in the assignment). The assignment handout, though the instructor can change this, is framed as having the students starting the assignment in teams in class for a whole class session, and then finishing it in those same teams as a take-home assignment, and handing it in before the next class session. We have found that student groups often succeed, partially or completely, in this challenge. This can mean a lot to the students: they see that they were able to make an advance that, when it was first obtained, appeared in what was arguably at the time the top journal venue for complexity theory research. This can give them confidence that they have substantial problem-solving skills (which basically means research skills) when they truly apply themselves to a given challenge.

0.10

The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness

cs.GT cs.CC ·2026-11-12 ·Ethan Dickey, Athina Terzoglou
theory similarity 0.58
Abstract · 51 pages, 11 figures

The tournament equilibrium set (TEQ), proposed by Schwartz in 1990, is a classical voting rule based on pairwise majority comparisons. Its definition is recursive: an alternative is judged by the alternatives that beat it, called its dominators, and by which of those dominators TEQ itself selects. Deciding whether a given alternative belongs to TEQ was known to be NP-hard and to lie in PSPACE. We close this gap by proving that the problem is PSPACE-complete. To our knowledge, this is the first PSPACE-completeness result for membership in a tournament solution. The hardness persists even when every nonempty subtournament has a unique minimal retentive set, the property conjectured by Schwartz to hold for all tournaments. Moreover, every such subtournament in our hard instances contains an alternative with at most three dominators. We prove that a single alternative with at most four dominators suffices both to guarantee uniqueness and to find a TEQ winner in $O(N^2)$ time. Thus, on our hard instances, finding one winner is efficient even though recognizing a specified winner is PSPACE-complete. We also study how the complexity changes with the dominator bound. If every nonempty subtournament has an alternative with at most one dominator, the entire TEQ can be computed in quadratic time; allowing two dominators makes membership NP-hard. Under the same condition with four dominators, all $t$ winners can be computed in $O(2^t N^2)$ time, where $N$ is the number of alternatives.

0.24

SPARQLcirc: Probabilistic Query Evaluation with Provenance Circuits

cs.DB cs.AI ·2026-10-29 ·Jingcheng Wu, Ratan Bahadur Thapa, Daniel Hernández, Steffen Staab
similarity 0.58
Abstract · 23 pages, 17 figures, 3 tables. Extended version with full proofs and additional experiments

Probabilistic query evaluation (PQE) computes the probability of every answer of a query over a tuple-independent probabilistic knowledge graph. We study exact PQE for SPARQL over graphs accessed through SPARQL 1.1 endpoints. Shared triples among the derivations of an answer make exact PQE #P-hard in general. Knowledge compilation of the Boolean provenance of every answer yields exact probabilities, and the provenance formulas of different answers can share subformulas. We propose SPARQLcirc, which rewrites a SPARQL query into CONSTRUCT queries that name every gate by its content, so that the results of independent queries form one Boolean provenance circuit for all answers. The rewriting covers joins, unions, projection, filters, OPTIONAL, difference, and transitive closures. SPARQLcirc compiles the circuit and computes the exact probability of every answer by weighted model counting. For the evaluation, we draw random probabilities for the triples of WatDiv and gMark and the statements of Wikidata and evaluate the CONSTRUCT queries on GraphDB, Fuseki, and Oxigraph. The ratio of the end-to-end time of PQE with SPARQLcirc to that of PQE by compiling the provenance expressions of the SPARQL provenance rewriting NPCS decreases with the number of derivations.

0.29

Subexponential-Time Exact-One Hitting Set

cs.DS ·2026-10-31 ·Shiteng Chen, Tao Jiang, Yijie Zhu
theory similarity 0.58
Abstract · 33 pages, full version including proofs and appendices

Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.

0.27