Enumeration of Minimal Hitting Sets Parameterized by Treewidth
Abstract
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 combinations, and enumerating database repairs. Previously, Eiter et al. [22] showed that the minimal hitting sets of an -vertex hypergraph, with treewidth , can be enumerated with delay (ignoring polynomial factors), with space requirements that scale with the output size. We improve this to fixed-parameter-linear delay, following an FPT preprocessing phase. The memory consumption of our algorithm is exponential with respect to the treewidth of the hypergraph.
Keywords and phrases:
Enumeration, Hitting setsCopyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Mathematics of computing EnumerationFunding:
This work was supported by the US-Israel Binational Science Foundation (NSF-BSF) Grant No. 2020751.Editors:
Sudeepa Roy and Ahmet KaraSeries and Publisher:

1 Introduction
A hypergraph is a finite collection of sets called hyperedges over a finite set of nodes. A transversal (or hitting set) of is a set that has a non-empty intersection with every hyperedge of . A transversal is minimal if no proper subset of is a transversal of . The problem of enumerating the set of minimal transversals of a hypergraph (called Trans-Enum for short) is a fundamental combinatorial problem with a wide range of applications in Boolean algebra [23], computational biology [57], drug-discovery [56], and many more (see surveys [21, 29, 20]).
The role of Trans-Enum in data management applications can be traced back to the 1987 paper by Mannila and Räihä [50]. This stems from the fact that finding minimal or maximal solutions (with respect to some property) is an essential task in many data management applications. In many cases, such tasks are easily translated, or even equivalent, to Trans-Enum. These include, for example, the discovery of inclusion-wise minimal Unique Column Combinations (UCCs), which are natural candidates for primary keys [8, 9], and play an important role in data profiling and query optimization (see surveys by Papenbrock, Naumann, and coauthors [1], [45]). Eiter and Gottlob have proved that UCC discovery and Trans-Enum are, in fact, equivalent [20]. Other data profiling tasks that can be reduced to trans-enum include discovering maximal frequent itemsets [33], functional dependencies [50, 59, 46], and multi-valued dependencies [40, 41]. Another data-management task that directly translates to Trans-Enum is that of enumerating database repairs, which are maximal sets of tuples that exclude some combinations of tuples based on logical patterns (e.g., functional dependencies, denial constraints etc.) [12, 7, 42, 48]. The forbidden combinations of tuples are represented as the hyperedges in a conflict hypergraph [11, 12], and the problem of enumerating the repairs is reduced to that of enumerating the minimal transversals of the conflict hypergraph [48].
An edge cover of a hypergraph is a subset of hyperedges such that every vertex is included in at least one hyperedge in . An edge cover is minimal if no proper subset of is an edge cover. Minimal edge covers are used to generate covers of query results, which are succinct, lossless representations of query results [35]. Our results for trans-enum carry over to the problem of enumerating minimal edge-covers (cover-enum).
A hypergraph can have exponentially many minimal hitting sets, ruling out any polynomial-time algorithm. Hence, the yardstick used to measure the efficiency of an algorithm for Trans-Enum is the delay between the output of successive solutions. An enumeration algorithm runs in polynomial delay if the delay is polynomial in the size of the input. Weaker notions are incremental polynomial delay if the delay between the th and the st solutions is bounded by a polynomial of the size of the input plus , and polynomial total time if the total computation time is polynomial in the sizes of both the input and output. While there exists a quasi-polynomial total time algorithm [27], whether Trans-Enum has a polynomial total time algorithm is a major open question [23]. In the absence of a tractable algorithm for general inputs, previous work has focused on special classes of hypergraphs. In particular, Trans-Enum admits a polynomial total time algorithm when restricted to acyclic hypergraphs, and hypergraphs with bounded hyperedge size [10].
In this paper, we consider the trans-enum problem parameterized by the treewidth of the input hypergraph. The treewidth of a graph is an important graph complexity measure that occurs as a parameter in many Fixed Parameter Tractable (FPT) algorithms [26]. An FPT algorithm for a parameterized problem solves the problem in time , where is the size of the input, is a computable function that depends only on the parameter , and is a fixed constant. The treewidth of a hypergraph is defined to be the treewidth of its associated node-hyperedge incidence graph [22] (formal definitions in Section 2). Our main result is that for a hypergraph , with vertices, hyperedges, and treewidth , we can enumerate the minimal hitting sets of with fixed-parameter-linear-delay , following an FPT preprocessing-phase that takes time , where . The memory requirement of our algorithm is in .
Previously, Eiter et al. [22] showed that the minimal transversals of an -vertex hypergraph with treewidth can be enumerated with delay , where is the size of the hypergraph (formal definition in Section 2), and its treewidth. When parameterized by the treewidth of the input hypergraph, our result provides a significant improvement: the minimal transversals can be enumerated in fixed-parameter-linear delay , following an FPT preprocessing phase. Ours also improves on the memory consumption which, for the algorithm of Eiter et al. [22], scales with the output size, while ours is polynomial for bounded-treewidth hypergraphs.
Overview of approach, and new techniques
We build on the well known relationship between the problem of enumerating minimal hypergraph transversals (trans-enum) and enumerating minimal dominating sets in graphs. A subset of vertices is a dominating set of a graph if every vertex in has a neighbor in . A dominating set is minimal if no proper subset of is a dominating set of . We denote by Dom-Enum the problem of enumerating the minimal dominating sets of . There is a tight connection between Dom-Enum and trans-enum; Kanté et al. [34] showed that Dom-Enum can be solved in polynomial-total-time if and only if trans-enum can as well. Building on this result, we show in Section 3 that trans-enum over a hypergraph with treewidth can be reduced to Dom-Enum over a graph with treewidth . Therefore, we focus on an algorithm for enumerating minimal dominating sets, where the delay is parameterized by the treewidth. In that vein, we mention the recent work by Rote [54], that presented an algorithm for enumerating the minimal dominating sets of trees.
The enumeration algorithm has two phases: preprocessing and enumeration. In the preprocessing phase, we construct a data structure that allows us to efficiently determine whether graph has a minimal dominating set meeting specified constraints. During enumeration, the algorithm queries this structure repeatedly, backtracking on a negative answer. This method of enumeration is known as Backtrack Search [52]. Our algorithm leverages the treewidth parameter in two ways: constructing the data structure in fixed-parameter-tractable time and space dependent on , and querying it such that each query answers in time . Overall, for an -vertex graph, this yields a delay of .
Central to our approach is a novel data structure based on the disjoint branch tree decomposition. Graphs with such a tree decomposition were first characterized by Gavril, and are called rooted directed path graphs [30]. The class of hypergraphs that have a disjoint branch tree decomposition strictly include the class of -acyclic hypergraphs, and are strictly included in the class of -acyclic hypergraphs [19]. Hypergraphs that have a disjoint-branch tree decomposition have proved beneficial for both schema design in relational databases [24, 19], and query processing in probabilistic databases [6, 37, 36, 38]. To our knowledge, ours is the first to make use of this structure for enumeration. Dynamic programming over tree decompositions breaks down complex problems into smaller subproblems associated with the nodes (or bags) of the tree decomposition. These subproblems are solved independently and combined in a bottom-up manner according to the tree structure. The challenge lies in merging solutions of multiple subtrees at each node, which can be complex and computationally intensive. Disjoint-branch tree decompositions simplify this by ensuring each node’s children have disjoint vertex sets, easing the enforcement of specific constraints placed on the vertices. This is especially important in the case of Dom-Enum where the constraints imposed on the vertices have the form of “vertex has at least two neighbors in the solution set”. Intuitively, it is easier and more efficient to ensure such constraints hold when the structure partitions ’s neighbors into disjoint sets. For the detailed application of this property for Dom-Enum see Section 5.2 and Example 5.2.
Our enumeration algorithm does not assume that the (incidence graph) of the input hypergraph has a disjoint branch tree decomposition [19]. Therefore, as part of the preprocessing phase, we construct a disjoint branch tree decomposition directly from the tree decomposition of the input graph. This new structure contains “vertices” that are not in the original input graph, and whose sole purpose is to facilitate the enumeration. In Section 5.2 we show that given a tree decomposition (that is not disjoint-branch) whose width is , we can construct the required disjoint-branch data-structure in time , with the guarantee that the width of the resulting structure is, effectively, at most . The main results of this paper are the following.
Theorem 1.
Let be an -vertex graph whose treewidth is . Following a preprocessing phase that takes time , the minimal dominating sets of can be enumerated with delay and total space .
The translation from the Trans-Enum (cover-enum) problem in the hypergraph to the Dom-Enum problem in the bipartite incidence-graph of (see Section 3) imposes certain restrictions on the set of vertices that can belong to the solution set (i.e., the minimal transversal or edge-cover). As a corollary of Theorem 1, we show the following (in Section 5.3).
Corollary 2.
Let be a hypergraph with vertices, hyperedges, and treewidth . Following a preprocessing phase that takes time , the minimal transversals (edge-covers) of can be enumerated with delay and total space .
Relation to the meta-theorem of Courcelle [13].
The seminal meta-theorem by Courcelle [13, 3] states that every decision and optimization graph problem definable in Monadic Second Order Logic (MSO) is FPT (and even linear in the input size) when parameterized by the treewidth of the input structure. MSO is the extension of First Order logic that allows quantification (i.e., ) over sets. Bagan [4], Courcelle [14], and Amarilli et al. [2] extended this result to enumeration problems, and showed that the delay between successive solutions to problems defined in MSO logic is fixed-parameter linear, when parameterized by the treewidth of the input structure.
Courcelle-based algorithms for model-checking, counting, and enumerating the assignments satisfying an MSO formula have the following form. Given a TD of a graph , it is first converted to a labeled binary tree over a fixed alphabet that depends on the width of the TD. The binary tree has the property that if and only if , where is derived from (e.g., by the algorithm in [25]). Next, is converted to a finite, deterministic tree automaton (FTA) using standard techniques [55, 17]. The generated FTA accepts the binary tree if and only if . Since simulating the deterministic FTA on takes linear time, this proves that Courcelle-based algorithms run in time , where , is the width of the TD , and is the length of .
The main problem with Courcelle-based algorithms is that the function is an iterated exponential of height . The problem stems from the fact that every quantifier alternation in the MSO formula (i.e., and ) induces a power-set construction during the generation of the FTA. Therefore, an MSO formula with quantifier alternations, will result in a deterministic FTA whose size is a -times iterated exponential. Various lower-bound results have shown that this blowup is unavoidable [53] even for model-checking over trees. According to Gottlob, Pichler and Wei [31], the problem is even more severe on bounded treewidth structures because the original (possibly simple) MSO-formula is first transformed into an equivalent MSO-formula over trees, which is more complex than the original formula , and in general will have additional quantifier alternations.
MSO-logic is highly expressive, and can express complex graph properties. The condition that is a minimal dominating set in an undirected graph can be specified using MSO logic. You can see the exact formulation (based on Proposition 4) in the full version [39]. The MSO formula for a minimal dominating set has two quantifier alternations. By the previous, the size of an FTA representing this formula will be at least doubly exponential. Previous analysis and experiments that attempted to craft the FTA directly (i.e., without going through the generic MSO-to-FTA conversion) have shown that this blowup materializes even for very simple MSO formulas [47, 44, 31, 58]. Moreover, Frick and Grohe [28] prove that no general algorithm can perform better than the FTA-based approach.
Despite evidence pointing to the contrary, it may be the case that with some considerable effort our algorithm can be formulated using an FTA with comparable runtime guarantees. The only instance we are aware of where a generic approach achieves running times comparable to those of a specialized algorithm is the algorithm of Gottlob, Pichler, and Wei [32] that translates an MSO formula to a monadic Datalog program (not an FTA). However, there too, the monadic Datalog programs were crafted manually, and used to directly encode the dynamic programming over the TD [32, 47].
Because of these limitations, practical algorithms over bounded-treewidth structures often avoid the MSO-to-FTA conversion and directly encode dynamic programming strategies on the tree decomposition [31, 49]. These specialized algorithms are not only more efficient, but are also transparent, allowing for exact runtime analysis, and enable proving optimality guarantees by optimizing the dependence on treewidth [49, 5, 18]. See the full version of this paper for more details [39].
Organization.
Following preliminaries in Section 2, we show in Section 3 how trans-enum and cover-enum over a hypergraph with treewidth can be reduced to dom-enum over a graph with treewidth . In Section 4 we present an overview of the algorithm. In Section 5, we describe the FPT preprocessing-phase, and in Section 6 prove correctness, and establish the FPL-delay guarantee of the enumeration algorithm. We conclude in Section 7. Due to space constraints, we defer some of the technical details and proofs to the full version of this paper [39], which also contains a discussion of lower bounds, and other related work.
2 Preliminaries and Notation
Let be an undirected graph with vertices and edges , where , and . We assume that does not have self-loops. Let . We let denote the neighborhood of , dropping the subscript when it is clear from the context. We denote by the subgraph of induced by a subset of vertices . Formally, , and .
Let , and let be a finite set of labels. We denote by an assignment of labels to the vertices . For example, let , , and be an assignment where . If , we denote by the assignment that results from by extending it with the assignment of the label to vertex . That is, for every , and . Finally, for , we denote by the assignment where for all .
Definition 3.
A subset of vertices is a dominating set of if every vertex has a neighbor in . A dominating set is minimal if is no longer a dominating set for every . We denote by the minimal dominating sets of .
A hypergraph is a pair , where , called the vertices of , is a finite set and are called the hyperedges of . The dual of a hypergraph , denoted , is the hypergraph with vertices , and hyperedges , where .
Definition 4 ([22](Incidence Graph)).
The incidence graph of a hypergraph , denoted , is the undirected, bipartite graph with vertex set and edge set .
Observe that a hypergraph and its dual have the same incidence graph. The size of a hypergraph , denoted , is . A transversal of a hypergraph is a subset that intersects every hyperedge . That is, for every . It is a minimal transversal if it does not contain any transversal as a proper subset. It is well known that a transversal is minimal if and only if for every , there exists a hyperedge , such that [51]. An edge cover of a hypergraph is a subset such that . It is a minimal edge cover if it does not contain any edge cover as a proper subset. The following shows that trans-enum and cover-enum are equivalent.
Proposition 5.
A subset is a minimal edge cover of if and only if the set is a minimal transversal of .
Definition 6 (Tree Decomposition (TD)).
A Tree Decomposition (TD) of a graph is a pair where is an undirected tree with nodes , edges , and is a function that maps each to a set of vertices , called a bag, such that:
-
1.
.
-
2.
For every there is a node such that .
-
3.
For every the set is connected in ; this is called the running intersection property.
The width of is the size of the largest bag minus one (i.e., ). The tree-width of , denoted , is the minimal width of a TD for .
There is more than one way to define the treewidth of a hypergraph [22]. In this work, the treewidth of a hypergraph is defined to be the treewidth of its incidence graph [22].
Let be a TD of a graph . Root the tree at node by directing the edges from to the leaves. We say that such a TD is rooted; in notation . For a node , we denote by its parent in (where if is the root node), by the subtree of rooted at node , by , and by the graph induced by (i.e., ). By this definition, . We will use “vertices” to refer to the vertices of the graph , and “nodes” to refer to the vertices of the TD.
Definition 7 (Disjoint-Branch TD (DBTD) [19, 30]).
A rooted TD is disjoint branch if, for every , with children , it holds that for all . A TD is disjoint branch if it has a node such that is disjoint branch.
First characterized by Gavril [30], graphs that have a disjoint branch TD are called rooted directed path graphs. In [15], disjoint branch TDs are called special tree decompositions. For the purpose of enumeration, our algorithm constructs a disjoint-branch TD whose width is at most twice the treewidth of the input graph . It is common practice to formulate dynamic programming algorithms over TDs that are nice [43].
Definition 8 (Nice Tree Decomposition [43, 16]).
A nice TD is a rooted TD with root node , in which each node is one of the following types:
-
Leaf node: a leaf of where .
-
Introduce node: has one child node where , and .
-
Forget node: has one child node where , and .
-
Join node: has two child nodes , where .
3 From Trans-Enum to Dom-Enum
In this section, we show how the trans-enum problem over a hypergraph with treewidth is translated to the dom-enum problem over a graph with treewidth . Due to the equivalence between trans-enum and cover-enum (Proposition 2), the translation also carries over to the cover-enum problem. We associate with the hypergraph a tripartite graph that is obtained from the incidence graph (Definition 2) by adding a new vertex that is made adjacent to all vertices in . Formally, the nodes of are defined where , and . Note that for every vertex in , it holds that , , and , for every . The construction of takes time , and is clearly polynomial.
Theorem 9.
A set is a minimal transversal of if and only if is a minimal dominating set of .
If is a minimal transversal of , then it is the unique minimal transversal of . Consequently, is the unique minimal dominating set of that is contained in . Hence, the problem of enumerating the minimal transversals of is reduced to that of enumerating the minimal dominating sets of that exclude the vertex-set , and include the vertex . Symmetrically, the problem of enumerating the minimal edge covers of is reduced to enumerating the minimal dominating sets of the tripartite graph that results from by adding a new vertex as a neighbor to all vertices , and enumerating the minimal dominating sets of that exclude the vertex-set , and include the vertex . In Section 5.3, we show how these restrictions are encoded.
Suppose that is a hypergraph with treewidth . That is, the treewidth of the incidence graph [22]. Next, we show that the treewidth of and is at most . This claim is directly implied by the following lemma.
Lemma 10.
Let be a tree-decomposition for the graph , and let . Let be the graph that results from by adding a vertex as a neighbor to all vertices . That is, and . If the width of is , then has a tree-decomposition whose width is .
The reduction from Trans-Enum to Dom-Enum of Kanté et al. [34] does not preserve the bounded-treewidth property, and generates a graph whose treewidth is , regardless of the treewidth of the hypergraph . Our reduction guarantees that the increase to the treewidth is at most one. That is, in our reduction (and ), hence preserving the bounded treewidth property.
4 Overview of Algorithm
In this section, we provide a high-level view of the algorithm for enumerating the minimal dominating sets of a graph , which applies the following simple characterization.
Proposition 11.
A dominating set is minimal if and only if for every , one of the following holds: (i) , or (ii) there exists a vertex , such that .
Definition 12 ([51](Private Neighbor)).
Let . A vertex is a private neighbor of if there exists a vertex such that . In this case we say that is ’s private neighbor. By private neighbors of we refer to the vertices in that are private neighbors of .
Another way to state Proposition 4 is to say that is a minimal dominating set if and only if is dominating, and for every that does not have a private neighbor, it holds that . In other words, if , then every vertex either has a private neighbor where , or . Therefore, the minimal dominating set partitions the vertices into four categories (or labels):
-
1.
Vertices in that have a private neighbor in are labeled .
-
2.
Vertices that have no private neighbor in , (), are labeled .
-
3.
Vertices that are private neighbors of , (), are labeled .
-
4.
All that are not private neighbors of , (), are labeled .
It is easy to see that distinct minimal dominating sets induce distinct labelings to the vertices of . Therefore, we view as assigning labels to vertices according to their category.
Example 13.
Consider the graph in Figure 3(a), and the minimal dominating set . Vertices , and have exactly one neighbor in , and hence are assigned the label ; since , then is assigned the label . The private neighbors of are , and the private neighbors of are . Therefore, vertices and are assigned label . Finally, is assigned label because it has no private neighbors (i.e., ), and .
Next, we refine our labeling as follows. Let , where the indices represent a complete ordering of (in Section 4.1 we discuss this ordering and its properties). We let denote the first vertices in the ordering.
Definition 14 (Labels Induced by minimal dominating set).
Let be a minimal dominating set. We define the labels induced by on as follows.
-
1.
Vertices in that have a private neighbor in . Vertex is labeled if and only if , has a private neighbor in , and no private neighbors in ; it is labeled if and only if , and it has a private neighbor in .
-
2.
A vertex is labeled if and only if has no private neighbors in , and .
-
3.
Vertices that are private neighbors of , and hence . Vertex is labeled if and only if has a single neighbor in . Otherwise, has a single neighbor in , and is labeled .
-
4.
Vertices where . Let . Then has at least neighbors in , and is labeled .
Overall, we have eight labels that we partition to three groups: , , and . We let .
Definition 15 (Minimal Dominating set consistent with assignment; extendable assignment).
Let denote a labeling to . A minimal dominating set is consistent with if, for every , the label that induces on is (Definition 4). We say that the labeling is extendable if there exists a minimal dominating set that is consistent with .
Example 16.
Consider the path . The labeling is extendable because the minimal dominating set is consistent with ; vertex , does not have any private neighbors in (because has two neighbors in ), and . On the other hand, the assignment is not extendable because the only minimal dominating set that contains , and excludes , must contain , thus violating the constraint that have no dominating neighbors among , or a single neighbor in the minimal dominating set (item (3) of Definition 4). Also, is not extendable for the same reason; must contain a private neighbor, which can only be . If is not part of the solution, then must be included in it. But then, is no longer a private neighbor because both its neighbors (i.e., and ) are dominating, thus violating the constraint .
We denote by the empty assignment, which is vacuously extendable. For every , we denote by the set of extendable assignments . Formally:
(1) |
Let be an assignment. For brevity, we denote by , and the vertices in that are assigned a label in and , respectively. Formally, , , and .
Lemma 17.
The following holds: .
Proof.
By bidirectional inclusion. Let be an extendable labeling. Then there exists a that is consistent with . By Definition 4 (items (1) and (2)), this means that . If , then by the consistency of , it holds that . Therefore, , and thus . Hence, .
Now, let . We build the labeling as follows. For every , such that we assign the label . For every , such that we assign the label . Since is dominating, then the the remaining (unlabeled) vertices must belong to . We assign the label to every that has a private neighbor in (i.e., has a neighbor assigned ). By Proposition 4, the remaining vertices in do not have any neighbors in , and hence are assigned . By construction, is consistent with , and hence . Also by construction, . Therefore, . According to Lemma 4, we describe an algorithm for enumerating the set . We fix a complete order over . In the preprocessing phase, the algorithm constructs a data structure that receives as input a labeling , and in time returns if and only if is extendable. Here, are the first vertices of .
The outline of the enumeration algorithm is presented in Figure 1 (ignore the algorithm in Figure 2 for now). It is initially called with the empty labeling , which is vacuously extendable, and the first vertex in the order . If , then the set is printed in line 2. The algorithm then iterates over all eight labels in , and for each label attempts to increment the extendable labeling , to one or more labelings , where . Assigning label to triggers an update to the labels of ’s neighbors in (i.e., ). The details of this update are specified in the procedure IncrementLabeling described in Section 4.2. The enumeration algorithm then utilizes the data structure , built in the preprocessing phase. In line 6, the algorithm queries the data structure , whether the resulting labeling is extendable. If and only if this is the case, does the algorithm recurs with the pair in line 7. Since the algorithm is initially called with the empty labeling, which is extendable, it follows that it only receives as input pairs where is extendable. From this observation, we prove the following in the full version of this paper [39].
Theorem 18.
For all , EnumDS is called with the pair if and only if is extendable.
A corollary of Theorem 18 is that EnumDS is called with the pair if and only if . From Lemma 4, we get that EnumDS prints if and only if .
Proposition 19.
Let be a complete order over such that the following holds for every :
-
1.
IncrementLabeling runs in time for every pair where , and returns a constant number of labelings .
-
2.
IsExtendable runs in time .
Then the delay between the output of consecutive items in algorithm EnumDS is .
In the following, we describe an order , and a data structure that meet the conditions of Proposition 4. We also show how can be built in time .
4.1 Ordering Vertices for Enumeration
Let be a TD rooted at node . Define to be a depth first order of . For every , is a node , with closer to the root . Define to map every to the earliest bag in the order , such that . By the running intersection property of TDs, the mapping is well defined; every vertex is assigned a single node in . Let be a complete order of that is consistent with , such that if then . There can be many such complete orders consistent with , and we choose one arbitrarily. With some abuse of notation, we denote by both the identifier of the node in the TD, and the bag . The enumeration algorithm EnumDS in Figure 1 follows the order .
Example 20.
Lemma 4.1 establishes an important property of the order , that is crucial for obtaining a delay of , where is the width of the TD. Proof is deferred to [39].
Lemma 21.
Let be the th vertex in . Then .
4.2 The IncrementLabeling Procedure
Let be an assignment to the first vertices of according to the complete order over defined in Section 4.1. Recall that , , and are the vertices in that are assigned a label in , , and by , respectively. Likewise, for every , we denote by the vertices in that are assigned label in (e.g., and are the vertices in assigned labels and respectively in ). The following proposition follows almost immediately from Definition 4, and the definition of an extendable assignment (Definition 4).
Proposition 22.
Let be an extendable assignment. For every it holds:
-
1.
If , then for every .
-
2.
If where , then , and .
-
3.
If , then , and .
-
4.
If , then , , and .
-
5.
If where , then ; and if , then .
IncrementLabeling receives as input a labeling , which we assume to be extendable (see EnumDS in Figure 1), and a label . It generates at most two new assignments , where (1) for all , and (2) For all it holds that if and only if where , and (3) . The procedure updates the labels of vertices based on the value , so that the conditions of Proposition 4.2 are maintained in . If the conditions of Proposition 4.2 cannot be maintained following the assignment of label to , then IncrementLabeling returns an empty set, indicating that cannot be incremented with the assignment while maintaining its extendability.
The pseudocode of IncrementLabeling is deferred to the full version of this paper [39]. In what follows, we illustrate with an example. If , and where , then ’s label is updated to (item (5) of Proposition 4.2). If , and , then ’s label is updated to (item (2) of Proposition 4.2). On the other hand, if , then by item (2) of Proposition 4.2, it means that . Therefore, if , then , thus violating item (2) of Proposition 4.2 with respect to . In this case, the procedure will return an empty set, indicating that cannot be augmented with , while maintaining the conditions of Proposition 4.2, which are required for the labeling to be extendable (Definition 4).
Lemma 23.
Procedure IncrementLabeling receives as input an extendable assignment to the first vertices of according to the complete order , and a value . There exist at most two extendable assignments where (1) for all , and (2) For all it holds that if and only if where , and (3) , that will be returned by IncrementLabeling. If no such extendable assignment exists, the procedure will return the empty set.
Lemma 24.
The runtime of procedure IncrementLabeling with input where for all is .
The proofs of Lemmas 4.2 and 4.2 are deferred to the full version of this paper [39]. Proposition 4 defines two conditions sufficient for obtaining FPL-delay of . In Section 4.1 we introduced the ordering , which guarantees that the runtime of IncrementLabeling is in (Lemma 4.2), thus meeting the first condition of Proposition 4. We now proceed to the second.
5 Preprocessing for Enumeration
The data structure generated in the preprocessing-phase is a nice disjoint-branch tree-decomposition.
Definition 25 (Nice Disjoint-Branch Tree Decomposition (Nice DBTD)).
A nice DBTD is a rooted TD with root node , in which each node is one of the following types:
-
Leaf node: a leaf of where .
-
Introduce node: has one child node where , and .
-
Forget node: has one child node where , and .
-
Disjoint Join node: has two child nodes , where and .
Figure 3(b) presents an example of a nice DBTD. The nodes of the generated nice DBTD are associated with factor tables (described in Section 5.1). Every tuple in the factor table associated with node is an assignment to the vertices of , where is the set of labels described in Section 4 (see Definition 4).
Since the input graph is given with a nice TD that is not necessarily disjoint-branch, we describe, in Section 5.2, how to transform its nice TD into one that is nice and disjoint-branch (Definition 5). This involves adding additional “vertices” to the bags of the tree, which are not vertices in the original graph. Essentially, some vertices in the graph will be represented by two or more “vertices” in the generated nice DBTD. The introduction of these new vertices is done in a way that maintains the consistency with respect to the vertex-assignments in the original (nice) TD. Importantly, our algorithm does not require the graph to be a rooted-directed-path graph [19, 30], and does not change it. The transformation from a nice TD to a nice DBTD comes at the cost of at most doubling the width of the nice TD. The necessity of this step, the details of the transformation, its correctness, and runtime analysis are presented in Section 5.2; some of the technical details are deferred to the full version of this paper [39]. After the transformation from a nice TD to a nice DBTD, the preprocessing phase proceeds by dynamic programming over the generated nice DBTD.
For the sake of completeness, we show in the full version of this paper [39] how to transform a DBTD (Definition 2) to a nice DBTD in polynomial time, while preserving its width. While the nice DBTD structure is new, transforming a DBTD to a nice DBTD is similar to transforming a TD to a nice TD (Chapter 13 in [43]).
In Section 5.4, we describe how to represent the factor tables of Section 5.1 as tries. This allows us to test whether an assignment is extendable in time , and allows us to obtain fixed-parameter-linear delay of (see Proposition 4).
5.1 Factors in the TD
Let be a TD of , and . Recall that is the graph induced by . We define a labeling of the bag to be an assignment . There are possible labelings of . In Section 4, we defined what it means for a minimal dominating set to be consistent with a labeling. Next, we define what it means for a set of vertices to be consistent with an assignment .
Definition 26.
Let , and . A subset is consistent with if the following holds for every :
-
1.
if and only if .
-
2.
If where , then , and (i.e., has neighbors in ).
-
3.
If where , then has at least neighbors in . That is, .
-
4.
If , then has a neighbor , such that . In addition, none of ’s neighbors in are assigned label .
-
5.
If , then for every , it holds that .
-
6.
If , then every neighbor of in is assigned a label in .
In addition, for every one of the following holds:
-
1.
and (i.e., is dominated by ).
-
2.
, and has a private neighbor in . That is, there exists a such that .
-
3.
, does not have a private neighbor in , and .
We denote by a mapping that assigns every labeling a Boolean indicating whether there exists a subset that is consistent with according to Definition 5.1. That is, if and only if there exists a set that is consistent with according to Definition 5.1. The factors of the TD are the mappings .
Example 27.
Consider node marked (with a double circle) in Figure 3(b), and an assignment . Note that . According to Definition 5.1, every consistent subset can induce only one of to the vertex . Equivalently, for any where , it holds that .
Consider the labeling where . If , then by Definition 5.1 and the fact that , in any that is consistent with , it must hold that . But then, , violating the constraint that . Hence, no such consistent set exists, and . If , , and , then by Definition 5.1 and the fact that , in any that is consistent with , it must hold that . Since , then cannot be consistent with the assignment . Therefore, .
Now, consider the assignment where , and . In this case because the set is consistent with according to Definition 5.1. Indeed, , hence is consistent with label on vertices and as required. Since , then is consistent with . We now consider vertices . Observe that , and thus is dominated by . Also, has a private neighbor in . Indeed, . Figure 3(c) presents other assignments to the vertices of where , along with the appropriate consistent subsets of vertices (i.e., according to Definition 5.1).
5.2 From Nice to Disjoint-Nice TD
In this section, we show how the encoding of an instance of the Dom-Enum problem in a nice TD , of width , can be represented using a nice disjoint branch TD , whose width is at most , and how this representation is built in time . We start with an example that provides some intuition regarding the requirement for a nice DBTD.
Example 28.
Let be a regular (i.e., not disjoint) join node in a nice TD , with children and (Definition 2). Hence, . For simplicity, suppose that . Consider the assignment , where . By definition, a subset that is consistent with (Definition 5.1) is such that . This means that includes exactly one neighbor of in (and no neighbors of from ), or vice versa. Therefore, to infer whether there exists a subset that is consistent with the assignment (i.e., ), we need to assign distinct labels to in the two sub-trees and , corresponding to the induced subgraphs and respectively. Specifically, we need to assign and , or and . The transformation of Lemma 5.2 represents as two distinct vertices in and respectively, while preserving the integrity of the assignment; that is, .
The details of the algorithm that generates a nice DBTD from a nice TD , proof of correctness and runtime analysis are deferred to the full version of this paper [39]. Here, we provide some intuition. The algorithm transforms every join node with children and to a disjoint join node (see Definition 5). To that end, the algorithm adds a new node to , such that , where and are variables used to represent the neighbors of in and respectively. Every occurrence of in is replaced with , and every occurrence of in is replaced with . To maintain the niceness of the resulting TD, the algorithm adds additional nodes (of type forget and introduce, see details and illustration in [39]). Since and essentially represent vertex in and respectively, then certain constraints are placed on the assignments associated with node . For example, if and only if for and . Another such constraint, for example, is that if and only if , , and . The complete list of constraints are specified in [39]. We refer to this set of constraints as local constraints. Observe that local constraints can be verified in time .
Let , and let be the set of local constraints on that can be verified in time . We say that an assignment is consistent with if . For a node , and local constraints , we let . For a given set of local constraints , and letting , the effective width of is defined:
(2) |
Observe that in any dynamic programming algorithm over a TD, the runtime and memory consumption of the algorithm depends exponentially on the effective width of the TD.
Lemma 29.
If a graph has a nice TD of width , then there is an algorithm that in time constructs a nice disjoint-branch TD with the following properties:
-
1.
, where for every node , there is a bijection between and .
-
2.
For every node , and every , it holds that if and only if , where and are the corresponding labeling and factor of node in .
-
3.
The effective width of is at most .
Conditions (1) and (2) of Lemma 5.2 guarantee that for every node , and , a subset is consistent with (in ) according to Definition 5.1, if and only if is consistent with (in ) according to Definition 5.1 (following the appropriate name-change to the vertices). This guarantees that, following the preprocessing phase, the generated TD can be used for enumerating the minimal dominating sets of . The proof of Lemma 5.2 and the pseudocode detailing the construction of a nice disjoint branch TD is deferred to the full version of this paper [39].
In [39], we present the algorithm that receives as input a nice DBTD and a set of local constraints , which computes the factor tables for every labeling , and every node , by dynamic programming. The factor tables account for the local constraints. That is, if then . We define , where is the set of labels that may be assigned to .
Lemma 30.
Let be a nice DBTD whose width is , and let be a set of local constraints. There is an algorithm that in time computes the factors of such that for every , and every labeling , it holds that if and only if , and there exists a subset that is consistent with according to Definition 5.1.
5.3 Factor Sizes and Runtime for trans-enum (proof of Corollary 1)
Recall that for every , we denote by the domain of . That is, is the set of labels that may be assigned to in any labeling where and . In Lemma 5.2, we establish that the dynamic programming over the nice DBTD takes time where is the width of the DBTD, and . In Section 5.2, we show that if , then has an embedding to a disjoint-branch TD whose effective width is at most . This allows us to prove Theorem 1. Next, we show that for trans-enum, every vertex can be assigned only one of labels (i.e., as opposed to labels), leading to better runtimes of the preprocessing phase, thus proving Corollary 1.
In Section 3, we reduced trans-enum on hypergraph to dom-enum over the tripartite graph , where . By Theorem 9, we are interested in minimal dominating sets , where , and . In particular, where . Therefore, vertices in can only be assigned labels in . If , then by construction . Consequently, vertices can have at most one neighbor in the minimal dominating set; namely the vertex . Therefore, vertices in can only be assigned labels in . Finally, the only dominating set of that excludes and , is . Since we are interested only in minimal transversals that are strictly included in , then must be dominating, and can only be assigned labels in . So, we get that vertices in can only be assigned labels from , vertices in can only be assigned labels in , and the vertex can only be assigned labels in . Since , and , every vertex of can be assigned one of at most labels. Therefore, for trans-enum the runtime of the preprocessing phase is in . This proves Corollary 1.
5.4 Compact Representation with Tries
A trie is a tree-based data structure used for efficient retrieval of strings. It organizes the strings by storing characters as tree-nodes, with common prefixes shared among multiple strings. Each node represents a character, and its outgoing edges possible next characters. The root node represents an empty string, and leaf nodes represent complete strings.
In Lemma 5.2 we establish the correctness and runtime guarantees of the algorithm that receives as input a nice DBTD , and a set of local constraints , which computes the factor tables where . We represent as a trie where every root-to-leaf path in represents an assignment , or a word in , such that . Let where the indices represent a complete order over . We view every assignment as a string: over the alphabet . In our construction, every string in the trie has precisely characters from , where the first character represents the assignment to , the second character the assignment to , etc. The advantage of this representation is that given an assignment , we can check if in time by traversing the trie from root to leaf to check whether the string appears in the trie . In the tabular representation, this requires traversing all assignments in the table, which, in the worst case, takes time . The order used to generate the tries is derived from the complete order defined in Section 4.1. See Figure 3(c) for an illustration.
6 Correctness and Analysis of The Enumeration Algorithm
We prove correctness of algorithm EnumDS presented in Section 4, and show that its delay is where and . By Proposition 4, this requires showing that both IncrementLabeling and IsExtendable are correct and run in time . The former is established in Lemmas 4.2 and 4.2. We present the IsExtendable procedure (Figure 2), prove its correctness, and show that it runs in time . The input to IsExtendable is the pair where is the nice DBJT (Definition 5) that is the output of the preprocessing phase described in Section 5, and is an assignment which meets the conditions of Proposition 4.2. In Lemmas 5.2 and 5.2 we established that has the property that every node is associated with a factor where if and only if there exists a subset that is consistent with the assignment according to Definition 5.1. In Section 5.4, we showed how to check whether in time .
Theorem 31.
IsExtendable returns true iff is extendable, and runs in time .
7 Conclusion
We present an efficient algorithm for enumerating minimal hitting sets parameterized by the treewidth of the hypergraph. We introduced the nice disjoint-branch TD suited for this task and potentially useful for other problems involving the enumeration of minimal or maximal solutions with respect to some property, common in data management. As future work, we intend to publish an implementation of our algorithm and empirically evaluate it on datasets for data-profiling problems [1, 45]. We also plan to investigate ranked enumeration of minimal hitting sets parameterized by treewidth.
References
- [1] Ziawasch Abedjan, Lukasz Golab, Felix Naumann, and Thorsten Papenbrock. Data Profiling. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2018. doi:10.2200/S00878ED1V01Y201810DTM052.
- [2] Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. A circuit-based approach to efficient enumeration. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 111:1–111:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.ICALP.2017.111.
- [3] Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12(2):308–340, 1991. doi:10.1016/0196-6774(91)90006-K.
- [4] Guillaume Bagan. MSO queries on tree decomposable structures are computable with linear delay. In Zoltán Ésik, editor, Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, volume 4207 of Lecture Notes in Computer Science, pages 167–181. Springer, 2006. doi:10.1007/11874683_11.
- [5] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 951–970. SIAM, 2020. doi:10.1137/1.9781611975994.57.
- [6] Paul Beame, Guy Van den Broeck, Eric Gribkoff, and Dan Suciu. Symmetric weighted first-order model counting. In Tova Milo and Diego Calvanese, editors, Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 313–328. ACM, 2015. doi:10.1145/2745754.2745760.
- [7] Leopoldo E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. doi:10.2200/S00379ED1V01Y201108DTM020.
- [8] Johann Birnick, Thomas Bläsius, Tobias Friedrich, Felix Naumann, Thorsten Papenbrock, and Martin Schirneck. Hitting set enumeration with partial information for unique column combination discovery. Proc. VLDB Endow., 13(11):2270–2283, 2020. URL: http://www.vldb.org/pvldb/vol13/p2270-birnick.pdf.
- [9] Thomas Bläsius, Tobias Friedrich, Julius Lischeid, Kitty Meeks, and Martin Schirneck. Efficiently enumerating hitting sets of hypergraphs arising in data profiling. J. Comput. Syst. Sci., 124:192–213, 2022. doi:10.1016/j.jcss.2021.10.002.
- [10] Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan. An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Process. Lett., 10(4):253–266, 2000. doi:10.1142/S0129626400000251.
- [11] Jan Chomicki and Jerzy Marcinkowski. Minimal-change integrity maintenance using tuple deletions. Inf. Comput., 197(1-2):90–121, 2005. doi:10.1016/j.ic.2004.04.007.
- [12] Jan Chomicki, Jerzy Marcinkowski, and Slawomir Staworko. Computing consistent query answers using conflict hypergraphs. In David A. Grossman, Luis Gravano, ChengXiang Zhai, Otthein Herzog, and David A. Evans, editors, Proceedings of the 2004 ACM CIKM International Conference on Information and Knowledge Management, Washington, DC, USA, November 8-13, 2004, pages 417–426. ACM, 2004. doi:10.1145/1031171.1031254.
- [13] Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pages 193–242. Elsevier and MIT Press, 1990. doi:10.1016/b978-0-444-88074-1.50010-x.
- [14] Bruno Courcelle. Linear delay enumeration and monadic second-order logic. Discret. Appl. Math., 157(12):2675–2700, 2009. doi:10.1016/j.dam.2008.08.021.
- [15] Bruno Courcelle. On the model-checking of monadic second-order formulas with edge set quantifications. Discret. Appl. Math., 160(6):866–887, 2012. doi:10.1016/J.DAM.2010.12.017.
- [16] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition, 2015.
- [17] John Doner. Tree acceptors and some of their applications. J. Comput. Syst. Sci., 4(5):406–451, 1970. doi:10.1016/S0022-0000(70)80041-1.
- [18] Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. Upper dominating set: Tight algorithms for pathwidth and sub-exponential approximation. Theor. Comput. Sci., 923:271–291, 2022. doi:10.1016/J.TCS.2022.05.013.
- [19] David Duris. Some characterizations of and -acyclicity of hypergraphs. Inf. Process. Lett., 112(16):617–620, 2012. doi:10.1016/j.ipl.2012.05.005.
- [20] Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput., 24(6):1278–1304, 1995. doi:10.1137/S0097539793250299.
- [21] Thomas Eiter and Georg Gottlob. Hypergraph transversal computation and related problems in logic and AI. In Sergio Flesca, Sergio Greco, Nicola Leone, and Giovambattista Ianni, editors, Logics in Artificial Intelligence, European Conference, JELIA 2002, Cosenza, Italy, September, 23-26, Proceedings, volume 2424 of Lecture Notes in Computer Science, pages 549–564. Springer, 2002. doi:10.1007/3-540-45757-7_53.
- [22] Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput., 32(2):514–537, 2003. doi:10.1137/S009753970240639X.
- [23] Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. Computational aspects of monotone dualization: A brief survey. Discret. Appl. Math., 156(11):2035–2049, 2008. doi:10.1016/j.dam.2007.04.017.
- [24] Ronald Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM, 30(3):514–550, 1983. doi:10.1145/2402.322390.
- [25] Jörg Flum, Markus Frick, and Martin Grohe. Query evaluation via tree-decompositions. J. ACM, 49(6):716–752, 2002. doi:10.1145/602220.602222.
- [26] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. doi:10.1007/3-540-29953-X.
- [27] Michael L. Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms, 21(3):618–628, 1996. doi:10.1006/jagm.1996.0062.
- [28] Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Annals of Pure and Applied Logic, 130(1):3–31, 2004. Papers presented at the 2002 IEEE Symposium on Logic in Computer Science (LICS). doi:10.1016/j.apal.2004.01.007.
- [29] Andrew Gainer-Dewar and Paola Vera-Licona. The minimal hitting set generation problem: Algorithms and computation. SIAM J. Discret. Math., 31(1):63–100, 2017. doi:10.1137/15M1055024.
- [30] Fanica Gavril. A recognition algorithm for the intersection graphs of directed paths in directed trees. Discret. Math., 13(3):237–249, 1975. doi:10.1016/0012-365X(75)90021-7.
- [31] Georg Gottlob, Reinhard Pichler, and Fang Wei. Bounded treewidth as a key to tractability of knowledge representation and reasoning. Artif. Intell., 174(1):105–132, 2010. doi:10.1016/J.ARTINT.2009.10.003.
- [32] Georg Gottlob, Reinhard Pichler, and Fang Wei. Monadic datalog over finite structures of bounded treewidth. ACM Trans. Comput. Log., 12(1):3:1–3:48, 2010. doi:10.1145/1838552.1838555.
- [33] Dimitrios Gunopulos, Roni Khardon, Heikki Mannila, Sanjeev Saluja, Hannu Toivonen, and Ram Sewak Sharm. Discovering all most specific sentences. ACM Trans. Database Syst., 28(2):140–174, 2003. doi:10.1145/777943.777945.
- [34] Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. On the enumeration of minimal dominating sets and related notions. SIAM J. Discret. Math., 28(4):1916–1929, 2014. doi:10.1137/120862612.
- [35] Ahmet Kara and Dan Olteanu. Covers of query results. In Benny Kimelfeld and Yael Amsterdamer, editors, 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, volume 98 of LIPIcs, pages 16:1–16:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPICS.ICDT.2018.16.
- [36] Batya Kenig and Avigdor Gal. On the impact of junction-tree topology on weighted model counting. In Christoph Beierle and Alex Dekhtyar, editors, Scalable Uncertainty Management - 9th International Conference, SUM 2015, Québec City, QC, Canada, September 16-18, 2015. Proceedings, volume 9310 of Lecture Notes in Computer Science, pages 83–98. Springer, 2015. doi:10.1007/978-3-319-23540-0_6.
- [37] Batya Kenig, Avigdor Gal, and Ofer Strichman. A new class of lineage expressions over probabilistic databases computable in p-time. In Weiru Liu, V. S. Subrahmanian, and Jef Wijsen, editors, Scalable Uncertainty Management - 7th International Conference, SUM 2013, Washington, DC, USA, September 16-18, 2013. Proceedings, volume 8078 of Lecture Notes in Computer Science, pages 219–232. Springer, 2013. doi:10.1007/978-3-642-40381-1_17.
- [38] Batya Kenig, Benny Kimelfeld, Haoyue Ping, and Julia Stoyanovich. Querying probabilistic preferences in databases. In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 21–36. ACM, 2017. doi:10.1145/3034786.3056111.
- [39] Batya Kenig and Dan Shlomo Mizrahi. Enumeration of minimal hitting sets parameterized by treewidth. CoRR, abs/2408.15776, 2024. doi:10.48550/arXiv.2408.15776.
- [40] Batya Kenig, Pranay Mundra, Guna Prasaad, Babak Salimi, and Dan Suciu. Mining approximate acyclic schemes from relations. In David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo, editors, Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pages 297–312. ACM, 2020. doi:10.1145/3318464.3380573.
- [41] Batya Kenig and Nir Weinberger. Quantifying the loss of acyclic join dependencies. In Floris Geerts, Hung Q. Ngo, and Stavros Sintos, editors, Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023, Seattle, WA, USA, June 18-23, 2023, pages 329–338. ACM, 2023. doi:10.1145/3584372.3588658.
- [42] Benny Kimelfeld, Ester Livshits, and Liat Peterfreund. Counting and enumerating preferred database repairs. Theor. Comput. Sci., 837:115–157, 2020. doi:10.1016/j.tcs.2020.05.016.
- [43] Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. doi:10.1007/BFb0045375.
- [44] Joachim Kneis and Alexander Langer. A practical approach to courcelle’s theorem. In Milan Ceska, Zdenek Kotásek, Mojmír Kretínský, Ludek Matyska, and Tomás Vojnar, editors, Proceedings of the International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2008, Znojmo, Czech Republic, November 14-16, 2008, volume 251 of Electronic Notes in Theoretical Computer Science, pages 65–81. Elsevier, 2008. doi:10.1016/J.ENTCS.2009.08.028.
- [45] Jan Kossmann, Thorsten Papenbrock, and Felix Naumann. Data dependencies for query optimization: a survey. VLDB J., 31(1):1–22, 2022. doi:10.1007/S00778-021-00676-3.
- [46] Sebastian Kruse and Felix Naumann. Efficient discovery of approximate dependencies. Proc. VLDB Endow., 11(7):759–772, 2018. doi:10.14778/3192965.3192968.
- [47] Alexander Langer, Felix Reidl, Peter Rossmanith, and Somnath Sikdar. Practical algorithms for MSO model-checking on tree-decomposable graphs. Comput. Sci. Rev., 13-14:39–74, 2014. doi:10.1016/j.cosrev.2014.08.001.
- [48] Ester Livshits, Alireza Heidari, Ihab F. Ilyas, and Benny Kimelfeld. Approximate denial constraints. Proc. VLDB Endow., 13(10):1682–1695, 2020. doi:10.14778/3401960.3401966.
- [49] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM J. Comput., 47(3):675–702, 2018. doi:10.1137/16M1104834.
- [50] Heikki Mannila and Kari-Jouko Räihä. Dependency inference. In Peter M. Stocker, William Kent, and Peter Hammersley, editors, VLDB’87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England, pages 155–158. Morgan Kaufmann, 1987. URL: http://www.vldb.org/conf/1987/P155.PDF.
- [51] Keisuke Murakami and Takeaki Uno. Efficient algorithms for dualizing large-scale hypergraphs. Discret. Appl. Math., 170:83–94, 2014. doi:10.1016/J.DAM.2014.01.012.
- [52] Ronald C. Read and Robert E. Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5(3):237–252, 1975. doi:10.1002/net.1975.5.3.237.
- [53] Klaus Reinhardt. The complexity of translating logic to finite automata. In Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors, Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 of Lecture Notes in Computer Science, pages 231–238. Springer, 2001. doi:10.1007/3-540-36387-4_13.
- [54] Günter Rote. Minimal dominating sets in a tree: Counting, enumeration, and extremal results. CoRR, abs/1903.04517, 2019. arXiv:1903.04517.
- [55] James W. Thatcher and Jesse B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Syst. Theory, 2(1):57–81, 1968. doi:10.1007/BF01691346.
- [56] Alexei Vazquez. Optimal drug combinations and minimal hitting sets. BMC Syst. Biol., 3:81, 2009. doi:10.1186/1752-0509-3-81.
- [57] Paola Vera-Licona, Eric Bonnet, Emmanuel Barillot, and Andrei Zinovyev. OCSANA: optimal combinations of interventions from network analysis. Bioinformatics, 29(12):1571–1573, April 2013. _eprint: https://academic.oup.com/bioinformatics/article-pdf/29/12/1571/48886062/bioinformatics_29_12_1571.pdf. doi:10.1093/bioinformatics/btt195.
- [58] M. Weyer. Modifizierte parametrische komplexitätstheorie. PhD Thesis, Universität Freiburg, 2008.
- [59] R. Xiao, Y. Yuan, Z. Tan, S. Ma, and W. Wang. Dynamic functional dependency discovery with dynamic hitting set enumeration. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 286–298, Los Alamitos, CA, USA, May 2022. IEEE Computer Society. doi:10.1109/ICDE53745.2022.00026.