7 citations · 12 across the 14 of their papers we have counts for
14 papers
Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
Batya Kenig
Important separators reduce the search space in parameterized graph separation to a small family that can be enumerated efficiently. We extend this approach to cut-uncut problems,…
Connectivity-Preserving Minimum Separator in AT-free Graphs
Batya Kenig
Let and be disjoint, non-adjacent vertex-sets in an undirected, connected graph , whose vertices are associated with positive weights. We address the problem of identify…
Causal DAG Summarization (Full Version)
Anna Zeng, Michael Cafarella, Batya Kenig +3
Causal inference aids researchers in discovering cause-and-effect relationships, leading to scientific insights. Accurate causal estimation requires identifying confounding variabl…
Enumeration of Minimal Hitting Sets Parameterized by Treewidth
Batya Kenig, Dan Shlomo Mizrahi
Enumerating the minimal hitting sets of a hypergraph is a problem which arises in many data management applications that include constraint mining, discovering unique column combin…
Approximate Implication for Probabilistic Graphical Models
Batya Kenig
The graphical structure of Probabilistic Graphical Models (PGMs) represents the conditional independence (CI) relations that hold in the modeled distribution. Every separator in th…
Listing Small Minimal -separators in FPT-Delay
Batya Kenig
Let be an undirected graph, and distinguished vertices of . A minimal -separator is an inclusion-wise minimal vertex-set whose removal places and in disti…
Quantifying the Loss of Acyclic Join Dependencies
Batya Kenig, Nir Weinberger
Acyclic schemes posses known benefits for database design, speeding up queries, and reducing space requirements. An acyclic join dependency (AJD) is lossless with respect to a univ…
Enumerating Minimal Separators in Ranked Order
Batya Kenig
Let be an -vertex graph, and vertices of . We present an efficient algorithm which enumerates the set of minimal -separators of in ascending order of cardin…
Approximate Implication with d-Separation
Batya Kenig
The graphical structure of Probabilistic Graphical Models (PGMs) encodes the conditional independence (CI) relations that hold in the modeled distribution. Graph algorithms, such a…
A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries
Batya Kenig, Dan Suciu
We study the , defined as follows: given a database, and a set of deterministic tuples, count the number of subsets of the database that include…
Mining Approximate Acyclic Schemes from Relations
Batya Kenig, Pranay Mundra, Guna Prasad +2
Acyclic schemes have numerous applications in databases and in machine learning, such as improved design, more efficient storage, and increased performance for queries and machine…
Integrity Constraints Revisited: From Exact to Approximate Implication
Batya Kenig, Dan Suciu
Integrity constraints such as functional dependencies (FD) and multi-valued dependencies (MVD) are fundamental in database schema design. Likewise, probabilistic conditional indepe…
The Complexity of the Possible Winner Problem over Partitioned Preferences
Batya Kenig
The Possible-Winner problem asks, given an election where the voters' preferences over the set of candidates is partially specified, whether a distinguished candidate can become a…
Efficiently Enumerating Minimal Triangulations
Nofar Carmeli, Batya Kenig, Benny Kimelfeld +1
We present an algorithm that enumerates all the minimal triangulations of a graph in incremental polynomial time. Consequently, we get an algorithm for enumerating all the proper t…