Enumeration of Minimal Hitting Sets Parameterized by Treewidth

Kenig, Batya; Mizrahi, Dan Shlomo

doi:10.4230/LIPIcs.ICDT.2025.8

Enumeration of Minimal Hitting Sets Parameterized by Treewidth

Batya Kenig

Technion, Israel Institute of Technology, Haifa, Israel Dan Shlomo Mizrahi Technion, Israel Institute of Technology, Haifa, Israel

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 $n$ -vertex hypergraph, with treewidth $w$ , can be enumerated with delay $O^{*}(n^{w})$ (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 sets

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Enumeration

Related Version:

Full Version: https://doi.org/10.48550/arXiv.2408.15776 [39]

Funding:

This work was supported by the US-Israel Binational Science Foundation (NSF-BSF) Grant No. 2020751.

DOI:

10.4230/LIPIcs.ICDT.2025.8

Event:

28th International Conference on Database Theory (ICDT 2025)

Editors:

Sudeepa Roy and Ahmet Kara

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

A hypergraph $\mathcal{H}$ is a finite collection $\mathcal{E}(\mathcal{H})$ of sets called hyperedges over a finite set $\texttt{V}(\mathcal{H})$ of nodes. A transversal (or hitting set) of $\mathcal{H}$ is a set ${\mathcal{S}}\subseteq\texttt{V}(\mathcal{H})$ that has a non-empty intersection with every hyperedge of $\mathcal{H}$ . A transversal ${\mathcal{S}}$ is minimal if no proper subset of ${\mathcal{S}}$ is a transversal of $\mathcal{H}$ . 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 $\mathcal{H}$ is a subset of hyperedges $\mathcal{D}\subseteq\mathcal{E}(\mathcal{H})$ such that every vertex $v\in\texttt{V}(\mathcal{H})$ is included in at least one hyperedge in $\mathcal{D}$ . An edge cover $\mathcal{D}$ is minimal if no proper subset of $\mathcal{D}$ 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 $i$ th and the $(i{+}1)$ st solutions is bounded by a polynomial of the size of the input plus $i$ , 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 $O(f(k)n^{c})$ , where $n$ is the size of the input, $f(k)$ is a computable function that depends only on the parameter $k$ , and $c$ 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 $\mathcal{H}$ , with $n$ vertices, $m$ hyperedges, and treewidth $w$ , we can enumerate the minimal hitting sets of $\mathcal{H}$ with fixed-parameter-linear-delay $O((n+m)w)$ , following an FPT preprocessing-phase that takes time $O((n{+}m)k5^{k})$ , where $w\leq k\leq 2w$ . The memory requirement of our algorithm is in $O((n{+}m)5^{k})$ .

Previously, Eiter et al. [22] showed that the minimal transversals of an $n$ -vertex hypergraph $\mathcal{H}$ with treewidth $w$ can be enumerated with delay $O(||\mathcal{H}||n^{w+1})$ , where $||\mathcal{H}||$ is the size of the hypergraph (formal definition in Section 2), and $w$ 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 $O(||\mathcal{H}||\cdot w)$ , 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 $S\subseteq\texttt{V}(G)$ is a dominating set of a graph $G$ if every vertex in $\texttt{V}(G){\setminus}S$ has a neighbor in $S$ . A dominating set is minimal if no proper subset of $S$ is a dominating set of $G$ . We denote by Dom-Enum the problem of enumerating the minimal dominating sets of $G$ . 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 $w$ can be reduced to Dom-Enum over a graph with treewidth $w^{\prime}\in\mathord{\{w,w+1\}}$ . 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 $G$ has a minimal dominating set $S$ 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 $w$ in two ways: constructing the data structure in fixed-parameter-tractable time and space dependent on $w$ , and querying it such that each query answers in time $O(w)$ . Overall, for an $n$ -vertex graph, this yields a delay of $O(nw)$ .

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 $\gamma$ -acyclic hypergraphs, and are strictly included in the class of $\beta$ -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 $v$ 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 $v$ ’s neighbors into disjoint sets. For the detailed application of this property for Dom-Enum see Section 5.2 and Example 28.

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 $w$ , we can construct the required disjoint-branch data-structure in time $O(nw^{2})$ , with the guarantee that the width of the resulting structure is, effectively, at most $2w$ . The main results of this paper are the following.

Theorem 1.

Let $G$ be an $n$ -vertex graph whose treewidth is $w$ . Following a preprocessing phase that takes time $O(nw8^{2w})$ , the minimal dominating sets of $G$ can be enumerated with delay $O(nw)$ and total space $O(n8^{2w})$ .

The translation from the Trans-Enum (cover-enum) problem in the hypergraph $\mathcal{H}$ to the Dom-Enum problem in the bipartite incidence-graph of $\mathcal{H}$ (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 $\mathcal{H}$ be a hypergraph with $n$ vertices, $m$ hyperedges, and treewidth $w$ . Following a preprocessing phase that takes time $O((m+n)w5^{2w})$ , the minimal transversals (edge-covers) of $\mathcal{H}$ can be enumerated with delay $O((m+n)w)$ and total space $O((m+n)5^{2w})$ .

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., $\forall,\exists$ ) 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 $\varphi$ have the following form. Given a TD $({\mathcal{T}},\chi)$ of a graph $G$ , it is first converted to a labeled binary tree $T^{\prime}$ over a fixed alphabet that depends on the width of the TD. The binary tree $T^{\prime}$ has the property that $G\models\varphi$ if and only if $T^{\prime}\models\varphi^{\prime}$ , where $\varphi^{\prime}$ is derived from $\varphi$ (e.g., by the algorithm in [25]). Next, $\varphi^{\prime}$ is converted to a finite, deterministic tree automaton (FTA) using standard techniques [55, 17]. The generated FTA accepts the binary tree $T^{\prime}$ if and only if $T^{\prime}\models\varphi^{\prime}$ . Since simulating the deterministic FTA on $T^{\prime}$ takes linear time, this proves that Courcelle-based algorithms run in time $O(n\cdot f(||\varphi||,w))$ , where $n=|\texttt{V}(G)|$ , $w$ is the width of the TD $({\mathcal{T}},\chi)$ , and $||\varphi||$ is the length of $\varphi$ .

The main problem with Courcelle-based algorithms is that the function $f(||\varphi||,w)$ is an iterated exponential of height $O(||\varphi||)$ . The problem stems from the fact that every quantifier alternation in the MSO formula (i.e., $\exists\forall$ and $\forall\exists$ ) induces a power-set construction during the generation of the FTA. Therefore, an MSO formula with $k$ quantifier alternations, will result in a deterministic FTA whose size is a $k$ -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 $\varphi$ is first transformed into an equivalent MSO-formula $\varphi^{\prime}$ over trees, which is more complex than the original formula $\varphi$ , and in general will have additional quantifier alternations.

MSO-logic is highly expressive, and can express complex graph properties. The condition that $X\subseteq\texttt{V}(G)$ is a minimal dominating set in an undirected graph $G$ can be specified using MSO logic. You can see the exact formulation (based on Proposition 11) 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 $w$ can be reduced to dom-enum over a graph with treewidth $w^{\prime}\leq w+1$ . 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 $G$ be an undirected graph with vertices $\texttt{V}(G)$ and edges $\texttt{E}(G)$ , where $n=|\texttt{V}(G)|$ , and $m=|\texttt{E}(G)|$ . We assume that $G$ does not have self-loops. Let $v\in\texttt{V}(G)$ . We let $N_{G}(v)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mathord{\{u% \in\texttt{V}(G)\mathrel{\mathop{\ordinarycolon}}(u,v)\in\texttt{E}(G)\}}$ denote the neighborhood of $v$ , dropping the subscript $G$ when it is clear from the context. We denote by $G[T]$ the subgraph of $G$ induced by a subset of vertices $T\subseteq\texttt{V}(G)$ . Formally, $\texttt{V}(G[T])=T$ , and $\texttt{E}(G[T])=\{(u,v)\in\texttt{E}(G)\mathrel{\mathop{\ordinarycolon}}$ $\mathord{\{u,v\}}\subseteq T\}$ .

Let $U\subseteq\texttt{V}(G)$ , and let $F$ be a finite set of labels. We denote by $\varphi\mathrel{\mathop{\ordinarycolon}}U\rightarrow F$ an assignment of labels to the vertices $U$ . For example, let $U=\mathord{\{v_{1},v_{2}\}}$ , $F=\mathord{\{\alpha,\beta\}}$ , and $\varphi$ be an assignment where $\varphi(v_{1})=\alpha,\varphi(v_{2})=\alpha$ . If $t\in\texttt{V}(G){\setminus}U$ , we denote by $\varphi^{\prime}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}(% \varphi,t\leftarrow\beta)$ the assignment that results from $\varphi$ by extending it with the assignment of the label $\beta$ to vertex $t$ . That is, $\varphi^{\prime}(v)=\varphi(v)$ for every $v\in U$ , and $\varphi^{\prime}(t)=\beta$ . Finally, for $U^{\prime}\subseteq U$ , we denote by $\varphi[U^{\prime}]\mathrel{\mathop{\ordinarycolon}}U^{\prime}\rightarrow F$ the assignment where $\varphi[U^{\prime}](w)=\varphi(w)$ for all $w\in U^{\prime}$ .

Definition 3.

A subset of vertices $D\subseteq\texttt{V}(G)$ is a dominating set of $G$ if every vertex $v\in\texttt{V}(G){\setminus}D$ has a neighbor in $D$ . A dominating set $D$ is minimal if $D^{\prime}$ is no longer a dominating set for every $D^{\prime}\subset D$ . We denote by ${\mathcal{S}}(G)$ the minimal dominating sets of $G$ .

A hypergraph $\mathcal{H}$ is a pair $(\texttt{V}(\mathcal{H}),\mathcal{E}(\mathcal{H}))$ , where $\texttt{V}(\mathcal{H})$ , called the vertices of $\mathcal{H}$ , is a finite set and $\mathcal{E}(\mathcal{H})\subseteq 2^{\texttt{V}(\mathcal{H})}{\setminus}% \mathord{\{\emptyset\}}$ are called the hyperedges of $\mathcal{H}$ . The dual of a hypergraph $\mathcal{H}$ , denoted $\mathcal{H}^{d}$ , is the hypergraph with vertices $\texttt{V}(\mathcal{H}^{d})\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}% }{{=}}}\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(% \mathcal{H})\}}$ , and hyperedges $\mathcal{E}(\mathcal{H}^{d})\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}% }}{{=}}}\mathord{\{f_{v}\mathrel{\mathop{\ordinarycolon}}v\in\texttt{V}(% \mathcal{H})\}}$ , where $f_{v}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mathord{\{y_{e% }\in\texttt{V}(\mathcal{H}^{d})\mathrel{\mathop{\ordinarycolon}}v\in e\}}$ .

Definition 4 ([22](Incidence Graph)).

The incidence graph of a hypergraph $\mathcal{H}$ , denoted $I(\mathcal{H})$ , is the undirected, bipartite graph with vertex set $\texttt{V}(I(\mathcal{H}))\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}% {{=}}}\texttt{V}(\mathcal{H})\cup\mathord{\{y_{e}\mathrel{\mathop{% \ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ and edge set $\texttt{E}(I(\mathcal{H}))\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}% {{=}}}\mathord{\{(x,y_{e})\mathrel{\mathop{\ordinarycolon}}x\in\texttt{V}(% \mathcal{H}),e\in\mathcal{E}(\mathcal{H}),\text{ and }x\in e\}}$ .

Observe that a hypergraph $\mathcal{H}$ and its dual $\mathcal{H}^{d}$ have the same incidence graph. The size of a hypergraph $\mathcal{H}$ , denoted $||\mathcal{H}||$ , is $|\texttt{V}(\mathcal{H})|+\sum_{e\in\mathcal{E}(\mathcal{H})}|e|$ . A transversal of a hypergraph $\mathcal{H}$ is a subset $\mathcal{M}\subseteq\texttt{V}(\mathcal{H})$ that intersects every hyperedge $e\in\mathcal{E}(\mathcal{H})$ . That is, $\mathcal{M}\cap e\neq\emptyset$ for every $e\in\mathcal{E}(\mathcal{H})$ . It is a minimal transversal if it does not contain any transversal as a proper subset. It is well known that a transversal $\mathcal{M}\subseteq\texttt{V}(\mathcal{H})$ is minimal if and only if for every $u\in\mathcal{M}$ , there exists a hyperedge $e_{u}\in\mathcal{E}(\mathcal{H})$ , such that $e_{u}\cap\mathcal{M}=\mathord{\{u\}}$ [51]. An edge cover of a hypergraph $\mathcal{H}$ is a subset $\mathcal{D}\subseteq\mathcal{E}(\mathcal{H})$ such that $\bigcup_{e\in\mathcal{D}}e=\texttt{V}(\mathcal{H})$ . 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 $\mathcal{D}\subseteq\mathcal{E}(\mathcal{H})$ is a minimal edge cover of $\mathcal{H}$ if and only if the set $\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{D}\}}$ is a minimal transversal of $\mathcal{H}^{d}$ .

Definition 6 (Tree Decomposition (TD)).

A Tree Decomposition (TD) of a graph $G$ is a pair $\left({\mathcal{T}},\chi\right)$ where ${\mathcal{T}}$ is an undirected tree with nodes $\texttt{V}({\mathcal{T}})$ , edges $\texttt{E}({\mathcal{T}})$ , and $\chi$ is a function that maps each $u\in\texttt{V}({\mathcal{T}})$ to a set of vertices $\chi(u)\subseteq\texttt{V}(G)$ , called a bag, such that:

1.

$\bigcup_{u\in\texttt{V}({\mathcal{T}})}\chi(u)=\texttt{V}(G)$ .
2.

For every $(s,t){\in}\texttt{E}(G)$ there is a node $u{\in}\texttt{V}({\mathcal{T}})$ such that $\mathord{\{s,t\}}{\subseteq}\chi(u)$ .
3.

For every $v\in\texttt{V}(G)$ the set $\{{u\in\texttt{V}({\mathcal{T}})}\mid{v\in\chi(u)}\}$ is connected in ${\mathcal{T}}$ ; this is called the running intersection property.

The width of $\left({\mathcal{T}},\chi\right)$ is the size of the largest bag minus one (i.e., $\max\mathord{\{|\chi(u)|\mathrel{\mathop{\ordinarycolon}}u\in\texttt{V}({% \mathcal{T}})\}}-1$ ). The tree-width of $G$ , denoted ${\tt\mathrm{tw}}(G)$ , is the minimal width of a TD for $G$ .

There is more than one way to define the treewidth of a hypergraph [22]. In this work, the treewidth of a hypergraph $\mathcal{H}$ is defined to be the treewidth of its incidence graph $I(\mathcal{H})$ [22].

Let $\left({\mathcal{T}},\chi\right)$ be a TD of a graph $G$ . Root the tree at node $r\in\texttt{V}({\mathcal{T}})$ by directing the edges $\texttt{E}({\mathcal{T}})$ from $r$ to the leaves. We say that such a TD is rooted; in notation $({\mathcal{T}}_{r},\chi)$ . For a node $u\in\texttt{V}({\mathcal{T}}_{r})$ , we denote by $\texttt{pa}(u)$ its parent in ${\mathcal{T}}_{r}$ (where $\texttt{pa}(u)\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}% \texttt{nil}$ if $u$ is the root node), by ${\mathcal{T}}_{u}$ the subtree of ${\mathcal{T}}_{r}$ rooted at node $u$ , by $V_{u}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\bigcup_{t\in% \texttt{V}({\mathcal{T}}_{u})}\chi(t)$ , and by $G_{u}$ the graph induced by $V_{u}$ (i.e., $G_{u}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}G[V_{u}]$ ). By this definition, $G_{r}=G$ . We will use “vertices” to refer to the vertices of the graph $G$ , and “nodes” to refer to the vertices of the TD.

Definition 7 (Disjoint-Branch TD (DBTD) [19, 30]).

A rooted TD $({\mathcal{T}}_{r},\chi)$ is disjoint branch if, for every $u\in\texttt{V}({\mathcal{T}}_{r})$ , with children $u_{1},\dots,u_{k}$ , it holds that $\chi(u_{i})\cap\chi(u_{j})=\emptyset$ for all $i\neq j$ . A TD $({\mathcal{T}},\chi)$ is disjoint branch if it has a node $r\in\texttt{V}(T)$ such that $({\mathcal{T}}_{r},\chi)$ 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 $G$ . 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 $({\mathcal{T}},\chi)$ with root node $r$ , in which each node $u\in\texttt{V}({\mathcal{T}})$ is one of the following types:

$\blacksquare$

Leaf node: a leaf of ${\mathcal{T}}$ where $\chi(u)=\emptyset$ .
$\blacksquare$

Introduce node: has one child node $u^{\prime}$ where $\chi(u)=\chi(u^{\prime})\cup\mathord{\{v\}}$ , and $v\notin\chi(u^{\prime})$ .
$\blacksquare$

Forget node: has one child node $u^{\prime}$ where $\chi(u)=\chi(u^{\prime})\setminus\mathord{\{v\}}$ , and $v\in\chi(u^{\prime})$ .
$\blacksquare$

Join node: has two child nodes $u_{1}$ , $u_{2}$ where $\chi(u)=\chi(u_{1})=\chi(u_{2})$ .

Given a TD (Definition 6) of a graph $G$ of width $w$ , one can in time $O(w^{2}\cdot|\texttt{V}(G)|)$ compute a nice tree decomposition of $G$ of width $w$ that has at most $O(w|\texttt{V}(G)|)$ nodes [16].

3 From Trans-Enum to Dom-Enum

In this section, we show how the trans-enum problem over a hypergraph $\mathcal{H}$ with treewidth $w$ is translated to the dom-enum problem over a graph $G$ with treewidth $w^{\prime}\leq w+1$ . Due to the equivalence between trans-enum and cover-enum (Proposition 5), the translation also carries over to the cover-enum problem. We associate with the hypergraph $\mathcal{H}$ a tripartite graph $B(\mathcal{H})$ that is obtained from the incidence graph $I(\mathcal{H})$ (Definition 4) by adding a new vertex that is made adjacent to all vertices in $\texttt{V}(\mathcal{H})$ . Formally, the nodes of $B(\mathcal{H})$ are defined $\texttt{V}(B(\mathcal{H}))\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}% {{=}}}\texttt{V}(I(\mathcal{H}))\cup\mathord{\{v\}}$ where $v\notin\texttt{V}(I(\mathcal{H}))$ , and $\texttt{E}(B(\mathcal{H}))\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}% {{=}}}\texttt{E}(I(\mathcal{H}))\cup\mathord{\{(u,v)\mathrel{\mathop{% \ordinarycolon}}u\in\texttt{V}(\mathcal{H})\}}$ . Note that for every vertex in $\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ , it holds that $N_{B(\mathcal{H})}(y_{e})=e$ , $N_{B(\mathcal{H})}(v)=\texttt{V}(\mathcal{H})$ , and $v\notin N_{B(\mathcal{H})}(y_{e})$ , for every $e\in\mathcal{E}(\mathcal{H})$ . The construction of $B(\mathcal{H})$ takes time $O(||\mathcal{H}||)$ , and is clearly polynomial.

Theorem 9.

A set $\mathcal{M}{\subset}\texttt{V}(\mathcal{H})$ is a minimal transversal of $\mathcal{H}$ if and only if $\mathcal{M}{\cup}\mathord{\{v\}}$ is a minimal dominating set of $B(\mathcal{H})$ .

If $\mathcal{M}=\texttt{V}(\mathcal{H})$ is a minimal transversal of $\mathcal{H}$ , then it is the unique minimal transversal of $\mathcal{H}$ . Consequently, $\texttt{V}(\mathcal{H})$ is the unique minimal dominating set of $B(\mathcal{H})$ that is contained in $\texttt{V}(\mathcal{H})\cup\mathord{\{v\}}$ . Hence, the problem of enumerating the minimal transversals of $\mathcal{H}$ is reduced to that of enumerating the minimal dominating sets of $B(\mathcal{H})$ that exclude the vertex-set $\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ , and include the vertex $v$ . Symmetrically, the problem of enumerating the minimal edge covers of $\mathcal{H}$ is reduced to enumerating the minimal dominating sets of the tripartite graph $C(\mathcal{H})$ that results from $I(\mathcal{H})$ by adding a new vertex $v\notin\texttt{V}(\mathcal{I}(\mathcal{H}))$ as a neighbor to all vertices $\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ , and enumerating the minimal dominating sets of $C(\mathcal{H})$ that exclude the vertex-set $\mathord{\{u\mathrel{\mathop{\ordinarycolon}}u\in\texttt{V}(\mathcal{H})\}}$ , and include the vertex $v$ . In Section 5.3, we show how these restrictions are encoded.

Suppose that $\mathcal{H}$ is a hypergraph with treewidth $k$ . That is, the treewidth of the incidence graph ${\tt\mathrm{tw}}(I(\mathcal{H}))=k$ [22]. Next, we show that the treewidth of $B(\mathcal{H})$ and $C(\mathcal{H})$ is at most $k+1$ . This claim is directly implied by the following lemma.

Lemma 10.

Let $({\mathcal{T}},\chi)$ be a tree-decomposition for the graph $G$ , and let $U\subseteq\texttt{V}(G)$ . Let $G^{\prime}$ be the graph that results from $G$ by adding a vertex $v\notin\texttt{V}(G)$ as a neighbor to all vertices $U$ . That is, $\texttt{V}(G^{\prime})=\texttt{V}(G)\cup\mathord{\{v\}}$ and $\texttt{E}(G^{\prime})=\texttt{E}(G)\cup\mathord{\{(v,w)\mathrel{\mathop{% \ordinarycolon}}w\in U\}}$ . If the width of $({\mathcal{T}},\chi)$ is $k$ , then $G^{\prime}$ has a tree-decomposition whose width is $k^{\prime}\leq k+1$ .

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 $O(n)$ , regardless of the treewidth of the hypergraph ${\tt\mathrm{tw}}(I(\mathcal{H}))$ . Our reduction guarantees that the increase to the treewidth is at most one. That is, in our reduction ${\tt\mathrm{tw}}(B(\mathcal{H}))\leq{\tt\mathrm{tw}}(I(\mathcal{H}))+1$ (and ${\tt\mathrm{tw}}(C(\mathcal{H}))\leq{\tt\mathrm{tw}}(I(\mathcal{H}))+1$ ), 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 $G$ , which applies the following simple characterization.

Proposition 11.

A dominating set $D\subseteq\texttt{V}(G)$ is minimal if and only if for every $u\in D$ , one of the following holds: (i) $N(u)\cap D=\emptyset$ , or (ii) there exists a vertex $v\in N(u){\setminus}D$ , such that $N(v)\cap D=\mathord{\{u\}}$ .

Definition 12 ([51](Private Neighbor)).

Let $D\subseteq\texttt{V}(G)$ . A vertex $v\in\texttt{V}(G){\setminus}D$ is a private neighbor of $D$ if there exists a vertex $u\in D$ such that $N(v)\cap D=\mathord{\{u\}}$ . In this case we say that $v$ is $u$ ’s private neighbor. By private neighbors of $D$ we refer to the vertices in $\texttt{V}(G){\setminus}D$ that are private neighbors of $D$ .

Another way to state Proposition 11 is to say that $D$ is a minimal dominating set if and only if $D$ is dominating, and for every $u\in D$ that does not have a private neighbor, it holds that $N(u)\cap D=\emptyset$ . In other words, if $D\in{\mathcal{S}}(G)$ , then every vertex $u\in D$ either has a private neighbor $v\in\texttt{V}(G){\setminus}D$ where $N(v)\cap D=\mathord{\{u\}}$ , or $N(u)\cap D=\emptyset$ . Therefore, the minimal dominating set $D\in{\mathcal{S}}(G)$ partitions the vertices $\texttt{V}(G)$ into four categories (or labels):

1.

Vertices in $D$ that have a private neighbor in $\texttt{V}(G){\setminus}D$ are labeled $[1]_{\sigma}$ .
2.

Vertices $v\in D$ that have no private neighbor in $\texttt{V}(G){\setminus}D$ , ( $N(v)\cap D=\emptyset$ ), are labeled $\sigma_{I}$ .
3.

Vertices $v\in\texttt{V}(G){\setminus}D$ that are private neighbors of $D$ , ( $|N(v)\cap D|=1$ ), are labeled $[1]_{\omega}$ .
4.

All $v\in\texttt{V}(G){\setminus}D$ that are not private neighbors of $D$ , ( $|N(v)\cap D|\geq 2$ ), are labeled $[2]_{\rho}$ .

It is easy to see that distinct minimal dominating sets induce distinct labelings to the vertices of $G$ . Therefore, we view $D$ as assigning labels to vertices according to their category.

Example 13.

Consider the graph $G$ in Figure 3(a), and the minimal dominating set $D=\mathord{\{d,f,i\}}$ . Vertices $a, b, c, e$ , and $h$ have exactly one neighbor in $D$ , and hence are assigned the label $[1]_{\omega}$ ; since $N(g)\cap D=\mathord{\{f,i\}}$ , then $g$ is assigned the label $[2]_{\rho}$ . The private neighbors of $d$ are $\mathord{\{b,c,e\}}$ , and the private neighbors of $f$ are $\mathord{\{a,h\}}$ . Therefore, vertices $d$ and $f$ are assigned label $[1]_{\sigma}$ . Finally, $i$ is assigned label $\sigma_{I}$ because it has no private neighbors (i.e., $|N(g)\cap D|\geq 2$ ), and $N(i)\cap D=\emptyset$ .

Next, we refine our labeling as follows. Let $\texttt{V}(G)=\mathord{\{v_{1},\dots,v_{n}\}}$ , where the indices represent a complete ordering of $\texttt{V}(G)$ (in Section 4.1 we discuss this ordering and its properties). We let $V_{i}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mathord{\{v_{1% },\dots,v_{i}\}}$ denote the first $i\leq n$ vertices in the ordering.

Definition 14 (Labels Induced by minimal dominating set).

Let $D\in{\mathcal{S}}(G)$ be a minimal dominating set. We define the labels induced by $D$ on $V_{i}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mathord{\{v_{1% },\dots,v_{i}\}}$ as follows.

1.

Vertices in $D\cap V_{i}$ that have a private neighbor in $\texttt{V}(G){\setminus}D$ . Vertex $v\in V_{i}$ is labeled $[0]_{\sigma}$ if and only if $v\in D$ , $v$ has a private neighbor in $V_{i}{\setminus}D$ , and no private neighbors in $\texttt{V}(G){\setminus}V_{i}$ ; it is labeled $[1]_{\sigma}$ if and only if $v\in D$ , and it has a private neighbor in $\texttt{V}(G){\setminus}V_{i}$ .
2.

A vertex $v\in D\cap V_{i}$ is labeled $\sigma_{I}$ if and only if $v$ has no private neighbors in $\texttt{V}(G){\setminus}D$ , and $N(v)\cap D=\emptyset$ .
3.

Vertices $v\in V_{i}{\setminus}D$ that are private neighbors of $D$ , and hence $|N(v)\cap D|=1$ . Vertex $v\in V_{i}{\setminus}D$ is labeled $[0]_{\omega}$ if and only if $v$ has a single neighbor in $V_{i}\cap D$ . Otherwise, $v$ has a single neighbor in $(\texttt{V}(G){\setminus}V_{i})\cap D$ , and is labeled $[1]_{\omega}$ .
4.

Vertices $v\in V_{i}{\setminus}D$ where $|N(v)\cap D|\geq 2$ . Let $j\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\min\mathord{\{2,|N% (v)\cap V_{i}\cap D|\}}$ . Then $v$ has at least $2-j$ neighbors in $D\cap(\texttt{V}(G){\setminus}V_{i})$ , and is labeled $[2-j]_{\rho}$ .

Overall, we have eight labels that we partition to three groups: $F_{\sigma}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mathord{% \{[0]_{\sigma},[1]_{\sigma},\sigma_{I}\}}$ , $F_{\omega}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mathord{% \{[0]_{\omega},[1]_{\omega}\}}$ , and $F_{\rho}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mathord{\{[% 0]_{\rho},[1]_{\rho},[2]_{\rho}\}}$ . We let $F\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}F_{\sigma}\cup F_{% \omega}\cup F_{\rho}$ .

Definition 15 (Minimal Dominating set consistent with assignment; extendable assignment).

Let $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ denote a labeling to $V_{i}$ . A minimal dominating set $D\in{\mathcal{S}}(G)$ is consistent with $\theta^{i}$ if, for every $v\in V_{i}$ , the label that $D$ induces on $v$ is $\theta^{i}(v)$ (Definition 14). We say that the labeling $\theta^{i}$ is extendable if there exists a minimal dominating set $D\in{\mathcal{S}}(G)$ that is consistent with $\theta^{i}$ .

Example 16.

Consider the path $v_{1}-v_{2}-v_{3}$ . The labeling $\theta^{1}\mathrel{\mathop{\ordinarycolon}}\mathord{\{v_{1}{\leftarrow}\sigma_% {I}\}}$ is extendable because the minimal dominating set $D_{1}=\mathord{\{v_{1},v_{3}\}}$ is consistent with $\theta^{1}$ ; vertex $v_{1}\in D_{1}$ , $v_{1}$ does not have any private neighbors in $\texttt{V}(G){\setminus}D_{1}=\mathord{\{v_{2}\}}$ (because $v_{2}$ has two neighbors in $D_{1}$ ), and $N(v_{1})\cap D_{1}=\emptyset$ . On the other hand, the assignment $\theta^{2}\mathrel{\mathop{\ordinarycolon}}\mathord{\{v_{1}{\leftarrow}[0]_{% \sigma},v_{2}{\leftarrow}[0]_{\omega}\}}$ is not extendable because the only minimal dominating set that contains $v_{1}$ , and excludes $v_{2}$ , must contain $v_{3}$ , thus violating the constraint that $v_{2}$ have no dominating neighbors among $\texttt{V}(G){\setminus}V_{2}=\mathord{\{v_{3}\}}$ , or a single neighbor in the minimal dominating set (item (3) of Definition 14). Also, $\theta^{1}\mathrel{\mathop{\ordinarycolon}}\mathord{\{v_{1}{\leftarrow}[1]_{% \sigma}\}}$ is not extendable for the same reason; $v_{1}$ must contain a private neighbor, which can only be $v_{2}$ . If $v_{2}$ is not part of the solution, then $v_{3}$ must be included in it. But then, $v_{2}$ is no longer a private neighbor because both its neighbors (i.e., $v_{1}$ and $v_{3}$ ) are dominating, thus violating the constraint $\theta^{1}(v_{1})=[1]_{\sigma}$ .

We denote by $\theta^{0}$ the empty assignment, which is vacuously extendable. For every $i\in[1,n]$ , we denote by $\boldsymbol{\Theta}^{i}$ the set of extendable assignments $\theta^{i}\mathrel{\mathop{\ordinarycolon}}\mathord{\{v_{1},\dots,v_{i}\}}\rightarrow F$ . Formally:

\displaystyle\boldsymbol{\Theta}^{i}\mathrel{\stackrel{{\scriptstyle\textsf{% \tiny def}}}{{=}}}\mathord{\{\theta^{i}\mathrel{\mathop{\ordinarycolon}}% \mathord{\{v_{1},\dots,v_{i}\}}\rightarrow F\mathrel{\mathop{\ordinarycolon}}% \theta^{i}\text{ is extendable}\}}

\displaystyle\forall i\in[0,n]

(1)

Let $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ be an assignment. For brevity, we denote by $\texttt{V}_{\sigma}(\theta^{i})$ , and $\texttt{V}_{\omega}(\theta^{i})$ the vertices in $V_{i}$ that are assigned a label in $F_{\sigma}$ and $F_{\omega}$ , respectively. Formally, $\texttt{V}_{\sigma}(\theta^{i})\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def% }}}{{=}}}\mathord{\{v\in V_{i}\mathrel{\mathop{\ordinarycolon}}\theta^{i}(v)% \in F_{\sigma}\}}$ , $\texttt{V}_{\omega}(\theta^{i})\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def% }}}{{=}}}\mathord{\{v\in V_{i}\mathrel{\mathop{\ordinarycolon}}\theta^{i}(v)% \in F_{\omega}\}}$ , and $\texttt{V}_{\rho}(\theta^{i})\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def% }}}{{=}}}\mathord{\{v\in V_{i}\mathrel{\mathop{\ordinarycolon}}\theta^{i}(v)% \in F_{\rho}\}}$ .

Lemma 17.

The following holds: ${\mathcal{S}}(G)=\mathord{\{\texttt{V}_{\sigma}(\theta^{n})\mathrel{\mathop{% \ordinarycolon}}\theta^{n}\in\boldsymbol{\Theta}^{n}\}}$ .

Proof.

By bidirectional inclusion. Let $\theta^{n}\in\boldsymbol{\Theta}^{n}$ be an extendable labeling. Then there exists a $D\in{\mathcal{S}}(G)$ that is consistent with $\theta^{n}$ . By Definition 14 (items (1) and (2)), this means that $D\supseteq\texttt{V}_{\sigma}(\theta^{n})$ . If $v\notin\texttt{V}_{\sigma}(\theta^{n})$ , then by the consistency of $D$ , it holds that $v\notin D$ . Therefore, $D\subseteq\texttt{V}_{\sigma}(\theta^{n})$ , and thus $D=\texttt{V}_{\sigma}(\theta^{n})$ . Hence, $\texttt{V}_{\sigma}(\theta^{n})\in{\mathcal{S}}(G)$ .

Now, let $D\in{\mathcal{S}}(G)$ . We build the labeling $\theta^{n}\mathrel{\mathop{\ordinarycolon}}\texttt{V}(G)\rightarrow F$ as follows. For every $v\in\texttt{V}(G){\setminus}D$ , such that $|N(v)\cap D|\geq 2$ we assign the label $[0]_{\rho}$ . For every $v\in\texttt{V}(G){\setminus}D$ , such that $|N(v)\cap D|=1$ we assign the label $[0]_{\omega}$ . Since $D$ is dominating, then the the remaining (unlabeled) vertices must belong to $D$ . We assign the label $[0]_{\sigma}$ to every $v\in D$ that has a private neighbor in $\texttt{V}(G){\setminus}D$ (i.e., $v$ has a neighbor assigned $[0]_{\omega}$ ). By Proposition 11, the remaining vertices in $D$ do not have any neighbors in $D$ , and hence are assigned $\sigma_{I}$ . By construction, $D$ is consistent with $\theta^{n}$ , and hence $\theta^{n}\in\boldsymbol{\Theta}^{n}$ . Also by construction, $\texttt{V}_{\sigma}(\theta^{n})=D$ . Therefore, $D\in\mathord{\{\texttt{V}_{\sigma}(\theta^{n})\mathrel{\mathop{\ordinarycolon}% }\theta^{n}\in\boldsymbol{\Theta}^{n}\}}$ . $\hfill\blacktriangleleft$ According to Lemma 17, we describe an algorithm for enumerating the set $\mathord{\{\texttt{V}_{\sigma}(\theta^{n})\mathrel{\mathop{\ordinarycolon}}% \theta^{n}\in\boldsymbol{\Theta}^{n}\}}$ . We fix a complete order $Q=\langle v_{1},v_{2},\dots,v_{n}\rangle$ over $\texttt{V}(G)$ . In the preprocessing phase, the algorithm constructs a data structure $\mathcal{M}$ that receives as input a labeling $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ , and in time $O({\tt\mathrm{tw}}(G))$ returns ${\tt true}$ if and only if $\theta^{i}$ is extendable. Here, $V_{i}=\mathord{\{v_{1},\dots,v_{i}\}}$ are the first $i$ vertices of $Q$ .

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 $\theta^{0}$ , which is vacuously extendable, and the first vertex in the order $v_{1}$ . If $i=n+1$ , then the set $\texttt{V}_{\sigma}(\theta^{n})$ is printed in line 2. The algorithm then iterates over all eight labels in $F$ , and for each label $c_{i}\in F$ attempts to increment the extendable labeling $\theta^{i-1}\mathrel{\mathop{\ordinarycolon}}V_{i-1}\rightarrow F$ , to one or more labelings $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ , where $\theta^{i}(v_{i})=c_{i}$ . Assigning label $c_{i}$ to $v_{i}$ triggers an update to the labels of $v_{i}$ ’s neighbors in $V_{i-1}$ (i.e., $N(v_{i})\cap V_{i}$ ). The details of this update are specified in the procedure IncrementLabeling described in Section 4.2. The enumeration algorithm then utilizes the data structure $\mathcal{M}$ , built in the preprocessing phase. In line 6, the algorithm queries the data structure $\mathcal{M}$ , whether the resulting labeling $\theta^{i}$ is extendable. If and only if this is the case, does the algorithm recurs with the pair $(v_{i+1},\theta^{i})$ 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 $(\theta^{i-1},v_{i})$ where $\theta^{i-1}\in\boldsymbol{\Theta}^{i-1}$ is extendable. From this observation, we prove the following in the full version of this paper [39].

Theorem 18.

For all $i\in\mathord{\{1,\dots,n+1\}}$ , EnumDS is called with the pair $(\theta^{i-1},v_{i})$ if and only if $\theta^{i-1}\in\boldsymbol{\Theta}^{i-1}$ is extendable.

A corollary of Theorem 18 is that EnumDS is called with the pair $(\theta^{n},v_{n+1})$ if and only if $\theta^{n}\in\boldsymbol{\Theta}^{n}$ . From Lemma 17, we get that EnumDS prints $D\subseteq\texttt{V}(G)$ if and only if $D\in{\mathcal{S}}(G)$ .

Proposition 19.

Let $Q=\langle v_{1},\dots,v_{n}\rangle$ be a complete order over $\texttt{V}(G)$ such that the following holds for every $i\in\mathord{\{1,\dots,n\}}$ :

1.

IncrementLabeling runs in time $O({\tt\mathrm{tw}}(G))$ for every pair $(\theta^{i-1},v_{i})$ where $\theta^{i-1}\mathrel{\mathop{\ordinarycolon}}V_{i-1}\rightarrow F$ , and returns a constant number of labelings $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ .
2.

IsExtendable runs in time $O({\tt\mathrm{tw}}(G))$ .

Then the delay between the output of consecutive items in algorithm EnumDS is $O(n\cdot{\tt\mathrm{tw}}(G))$ .

In the following, we describe an order $Q=\langle v_{1},\dots,v_{n}\rangle$ , and a data structure $\mathcal{M}$ that meet the conditions of Proposition 19. We also show how $\mathcal{M}$ can be built in time $O(n|F|^{2{\tt\mathrm{tw}}(G)})$ .

Figure 1: Algorithm for enumerating minimal dominating sets in FPL-delay when parameterized by treewidth.

Figure 2: Returns true if and only if

\theta^{i}\in\boldsymbol{\Theta}^{i}

is extendable.

4.1 Ordering Vertices for Enumeration

Let $\left({\mathcal{T}},\chi\right)$ be a TD rooted at node $u_{1}$ . Define $P\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\langle u_{1},\dots% ,u_{|\texttt{V}({\mathcal{T}})|}\rangle$ to be a depth first order of $\texttt{V}({\mathcal{T}})$ . For every $i>1$ , $\texttt{pa}(u_{i})$ is a node $u_{j}\in\texttt{V}({\mathcal{T}})$ , with $j<i$ closer to the root $u_{1}$ . Define $B\mathrel{\mathop{\ordinarycolon}}\texttt{V}(G)\rightarrow\mathord{\{1,\dots,|% \texttt{V}({\mathcal{T}})|\}}$ to map every $v\in\texttt{V}(G)$ to the earliest bag $u\in\texttt{V}({\mathcal{T}})$ in the order $P$ , such that $v\in\chi(u)$ . By the running intersection property of TDs, the mapping $B\mathrel{\mathop{\ordinarycolon}}\texttt{V}(G)\rightarrow\mathord{\{1,\dots,|% \texttt{V}({\mathcal{T}})|\}}$ is well defined; every vertex $v\in\texttt{V}(G)$ is assigned a single node in $\texttt{V}({\mathcal{T}})$ . Let $Q=\langle v_{1},\dots,v_{n}\rangle$ be a complete order of $\texttt{V}(G)$ that is consistent with $B$ , such that if $B(v_{i})<B(v_{j})$ then $v_{i}\prec_{Q}v_{j}$ . There can be many such complete orders consistent with $B$ , and we choose one arbitrarily. With some abuse of notation, we denote by $B(v_{i})$ both the identifier of the node in the TD, and the bag $\chi(B(v_{i}))$ . The enumeration algorithm EnumDS in Figure 1 follows the order $Q$ .

Example 20.

Consider $G$ in Figure 3(a), and its nice TD in Figure 3(b). Then $B(c)=u$ , and $a\prec g\prec b\prec c\prec d\prec e$ in the order $Q$ . Also, see the mapping $B$ applied to the vertices of $G$ .

Lemma 21 establishes an important property of the order $Q$ , that is crucial for obtaining a delay of $O(nw)$ , where $w$ is the width of the TD. Proof is deferred to [39].

Lemma 21.

Let $v_{i}$ be the $i$ th vertex in $Q=\langle v_{1},\dots,v_{n}\rangle$ . Then $N(v_{i})\cap\mathord{\{v_{1},\dots,v_{i-1}\}}\subseteq B(v_{i})$ .

4.2 The IncrementLabeling Procedure

Let $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ be an assignment to the first $i$ vertices of $\texttt{V}(G)$ according to the complete order $Q$ over $\texttt{V}(G)$ defined in Section 4.1. Recall that $\texttt{V}_{\sigma}(\theta^{i})$ , $\texttt{V}_{\omega}(\theta^{i})$ , and $\texttt{V}_{\rho}(\theta^{i})$ are the vertices in $V_{i}$ that are assigned a label in $F_{\sigma}$ , $F_{\omega}$ , and $F_{\rho}$ by $\theta^{i}$ , respectively. Likewise, for every $a\in F$ , we denote by $\texttt{V}_{a}(\theta^{i})$ the vertices in $V_{i}$ that are assigned label $a$ in $\theta^{i}$ (e.g., $\texttt{V}_{\sigma_{I}}(\theta^{i})$ and $\texttt{V}_{[0]_{\omega}}(\theta^{i})$ are the vertices in $V_{i}$ assigned labels $\sigma_{I}$ and $[0]_{\omega}$ respectively in $\theta^{i}$ ). The following proposition follows almost immediately from Definition 14, and the definition of an extendable assignment (Definition 15).

Proposition 22.

Let $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ be an extendable assignment. For every $v_{j}\in V_{i}$ it holds:

1.

If $\theta^{i}(v_{j})=\sigma_{I}$ , then $\theta^{i}(w)\in F_{\rho}$ for every $w\in N(v_{j})\cap V_{i}$ .
2.

If $\theta^{i}(v_{j})=[x]_{\omega}$ where $x\in\mathord{\{0,1\}}$ , then $|N(v_{j})\cap\texttt{V}_{\sigma_{I}}(\theta^{i})|=0$ , and $|N(v_{j})\cap\texttt{V}_{\sigma}(\theta^{i})|=1-x$ .
3.

If $\theta^{i}(v_{j})=[1]_{\sigma}$ , then $|N(v_{j})\cap\texttt{V}_{\sigma_{I}}(\theta^{i})|=0$ , and $|N(v_{j})\cap\texttt{V}_{[1]_{\omega}}(\theta^{i})|=0$ .
4.

If $\theta^{i}(v_{j})=[0]_{\sigma}$ , then $|N(v_{j})\cap\texttt{V}_{\sigma_{I}}(\theta^{i})|=0$ , $|N(v_{j})\cap\texttt{V}_{[1]_{\omega}}(\theta^{i})|=0$ , and $|N(v_{j})\cap\texttt{V}_{[0]_{\omega}}(\theta^{i})|{\geq}1$ .
5.

If $\theta^{i}(v_{j})=[x]_{\rho}$ where $x\in\mathord{\{1,2\}}$ , then $|N(v_{j})\cap\texttt{V}_{\sigma}(\theta^{i})|=2-x$ ; and if $\theta^{i}(v_{j})=[0]_{\rho}$ , then $|N(v_{j})\cap\texttt{V}_{\sigma}(\theta^{i})|\geq 2$ .

IncrementLabeling receives as input a labeling $\theta^{i-1}\mathrel{\mathop{\ordinarycolon}}V_{i-1}\rightarrow F$ , which we assume to be extendable (see EnumDS in Figure 1), and a label $c_{i}\in F$ . It generates at most two new assignments $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ , where (1) $\theta^{i}(w)=\theta^{i-1}(w)$ for all $w\notin N(v_{i})$ , and (2) For all $w\in N(v_{i})\cap V_{i}$ it holds that $\theta^{i-1}(w)\in\texttt{V}_{a}(\theta^{i-1})$ if and only if $\theta^{i}(w)\in\texttt{V}_{a}(\theta^{i})$ where $a\in\mathord{\{\sigma_{I},\sigma,\omega,\rho\}}$ , and (3) $\theta^{i}(v_{i})=c_{i}$ . The procedure updates the labels of vertices $w\in N(v_{i})\cap V_{i}$ based on the value $c_{i}$ , so that the conditions of Proposition 22 are maintained in $\theta^{i}$ . If the conditions of Proposition 22 cannot be maintained following the assignment of label $c_{i}$ to $v_{i}$ , then IncrementLabeling returns an empty set, indicating that $\theta^{i-1}$ cannot be incremented with the assignment $\theta^{i}(v_{i})\leftarrow c_{i}$ 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 $c_{i}\in F_{\sigma}$ , and $w\in N(v_{i})\cap V_{i}$ where $\theta^{i-1}(w)=[1]_{\rho}$ , then $w$ ’s label is updated to $\theta^{i}(w)=[0]_{\rho}$ (item (5) of Proposition 22). If $c_{i}=[0]_{\sigma}$ , and $\theta^{i-1}(w)=[1]_{\omega}$ , then $w$ ’s label is updated to $\theta^{i}(w)=[0]_{\omega}$ (item (2) of Proposition 22). On the other hand, if $\theta^{i-1}(w)=[0]_{\omega}$ , then by item (2) of Proposition 22, it means that $|N(w)\cap\texttt{V}_{\sigma}(\theta^{i-1})|=1$ . Therefore, if $c_{i}\in F_{\sigma}$ , then $|N(w)\cap\texttt{V}_{\sigma}(\theta^{i})|=2$ , thus violating item (2) of Proposition 22 with respect to $\theta^{i}$ . In this case, the procedure will return an empty set, indicating that $\theta^{i-1}$ cannot be augmented with $v_{i}\leftarrow c_{i}$ , while maintaining the conditions of Proposition 22, which are required for the labeling to be extendable (Definition 15).

Lemma 23.

Procedure IncrementLabeling receives as input an extendable assignment $\theta^{i-1}\mathrel{\mathop{\ordinarycolon}}V_{i-1}\rightarrow F$ to the first $i-1$ vertices of $\texttt{V}(G)$ according to the complete order $Q$ , and a value $c_{i}\in F$ . There exist at most two extendable assignments $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ where (1) $\theta^{i}(w)=\theta^{i-1}(w)$ for all $w\notin N(v_{i})$ , and (2) For all $w\in N(v_{i})\cap V_{i}$ it holds that $\theta^{i-1}(w)\in\texttt{V}_{a}(\theta^{i-1})$ if and only if $\theta^{i}(w)\in\texttt{V}_{a}(\theta^{i})$ where $a\in\mathord{\{\sigma_{I},\sigma,\omega,\rho\}}$ , and (3) $\theta^{i}(v_{i})=c_{i}$ , 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 $(\theta^{i-1},c_{i})$ where $v_{j}\prec_{Q}v_{i}$ for all $j\in\mathord{\{1,\dots,i-1\}}$ is $O({\tt\mathrm{tw}}(G))$ .

The proofs of Lemmas 23 and 24 are deferred to the full version of this paper [39]. Proposition 19 defines two conditions sufficient for obtaining FPL-delay of $O(n\cdot{\tt\mathrm{tw}}(G))$ . In Section 4.1 we introduced the ordering $Q=\langle v_{1},\dots,v_{n}\rangle$ , which guarantees that the runtime of IncrementLabeling is in $O({\tt\mathrm{tw}}(G))$ (Lemma 24), thus meeting the first condition of Proposition 19. We now proceed to the second.

((a))

G

,

G_{u}

.

((b)) Disregarding the dotted edges, this is a nice TD

({\mathcal{T}},\chi)

for

G

. The nice disjoint branch TD for

G

results from adding the dotted edges, and removing nodes

t_{0}

,

t_{1}

, and their adjacent edges. The subtree

{\mathcal{T}}_{u}

corresponds to the induced graph

G_{u}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}G[\texttt{V}_{u}]

, where

\texttt{V}_{u}=\mathord{\{a,b,c,d,e\}}

. An order

Q

corresponding to this nice TD is

Q=\langle h,f,a,g,i,b,c,d,e\rangle

.

((c)) Trie for factor

\mathcal{M}_{u}\mathrel{\mathop{\ordinarycolon}}F^{\chi(u)}\rightarrow\mathord% {\{0,1\}}

for node

u

in the TD in Figure 3(b). The order used to construct the trie is

a\prec b\prec c

which is compatible with the order

Q

derived from the TD in Figure 3(b).

Figure 3: A graph

G

, its nice TD, and example of a trie representing a factor of the TD.

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 $({\mathcal{T}},\chi)$ with root node $r$ , in which each node $u\in\texttt{V}({\mathcal{T}})$ is one of the following types:

$\blacksquare$

Leaf node: a leaf of ${\mathcal{T}}$ where $\chi(u)=\emptyset$ .
$\blacksquare$

Introduce node: has one child node $u^{\prime}$ where $\chi(u)=\chi(u^{\prime})\cup\mathord{\{v\}}$ , and $v\notin\chi(u^{\prime})$ .
$\blacksquare$

Forget node: has one child node $u^{\prime}$ where $\chi(u)=\chi(u^{\prime}){\setminus}\mathord{\{v\}}$ , and $v\in\chi(u^{\prime})$ .
$\blacksquare$

Disjoint Join node: has two child nodes $u_{1}$ , $u_{2}$ where $\chi(u)=\chi(u_{1})\cup\chi(u_{2})$ and $\chi(u_{1}){\cap}\chi(u_{2}){=}\emptyset$ .

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 $u\in\texttt{V}({\mathcal{T}})$ is an assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ to the vertices of $\chi(u)$ , where $F$ is the set of labels described in Section 4 (see Definition 14).

Since the input graph $G$ 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 25). 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 $G$ 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 $G$ 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 7) 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 $O({\tt\mathrm{tw}}(G))$ , and allows us to obtain fixed-parameter-linear delay of $O(n\cdot{\tt\mathrm{tw}}(G))$ (see Proposition 19).

5.1 Factors in the TD

Let $({\mathcal{T}},\chi)$ be a TD of $G$ , and $u\in\texttt{V}({\mathcal{T}})$ . Recall that $G_{u}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}G[V_{u}]$ is the graph induced by $V_{u}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\bigcup_{t\in% \texttt{V}({\mathcal{T}}_{u})}\chi(t)$ . We define a labeling of the bag $\chi(u)$ to be an assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ . There are $|F|^{|\chi(u)|}$ possible labelings of $\chi(u)$ . In Section 4, we defined what it means for a minimal dominating set $D\in{\mathcal{S}}(G)$ to be consistent with a labeling. Next, we define what it means for a set of vertices $D_{u}\subseteq\texttt{V}_{u}$ to be consistent with an assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ .

Definition 26.

Let $u\in\texttt{V}({\mathcal{T}})$ , and $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ . A subset $D_{u}\subseteq\texttt{V}_{u}$ is consistent with $\varphi_{u}$ if the following holds for every $v\in\chi(u)$ :

1.

$v\in D_{u}$ if and only if $\varphi_{u}(v)\in F_{\sigma}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}% }}{{=}}}\mathord{\{[0]_{\sigma},[1]_{\sigma},\sigma_{I}\}}$ .
2.

If $\varphi_{u}(v)=[j]_{\omega}$ where $j\in\mathord{\{0,1\}}$ , then $|N(v)\cap D_{u}|\leq 1$ , and $|N(v)\cap(D_{u}{\setminus}\chi(u))|=j$ (i.e., $v$ has $j$ neighbors in $D_{u}{\setminus}\chi(u)$ ).
3.

If $\varphi_{u}(v)=[j]_{\rho}$ where $j\in\mathord{\{0,1,2\}}$ , then $v$ has at least $j$ neighbors in $D_{u}{\setminus}\chi(u)$ . That is, $|N(v)\cap(D_{u}{\setminus}\chi(u))|\geq j$ .
4.

If $\varphi_{u}(v)=[1]_{\sigma}$ , then $v$ has a neighbor $w\in N(v)\cap(\texttt{V}_{u}{\setminus}(D_{u}\cup\chi(u))$ , such that $N(w)\cap D_{u}=\mathord{\{v\}}$ . In addition, none of $v$ ’s neighbors in $\chi(u)$ are assigned label $[1]_{\omega}$ .
5.

If $\varphi_{u}(v)=[0]_{\sigma}$ , then for every $w\in N(v){\cap}(\texttt{V}_{u}{\setminus}(D_{u}{\cup}\chi(u)))$ , it holds that $|N(w)\cap D_{u}|\geq 2$ .
6.

If $\varphi_{u}(v)=\sigma_{I}$ , then every neighbor of $v$ in $V_{u}$ is assigned a label in $F_{\rho}$ .

In addition, for every $v\in\texttt{V}_{u}{\setminus}\chi(u)$ one of the following holds:

1.

$v\notin D_{u}$ and $N(v)\cap D_{u}\neq\emptyset$ (i.e., $v$ is dominated by $D_{u}$ ).
2.

$v\in D_{u}$ , and has a private neighbor in $V_{u}{\setminus}D_{u}$ . That is, there exists a $w\in N(v)\cap(\texttt{V}_{u}{\setminus}D_{u})$ such that $N(w)\cap D_{u}=\mathord{\{v\}}$ .
3.

$v\in D_{u}$ , does not have a private neighbor in $V_{u}{\setminus}D_{u}$ , and $N(v)\cap D_{u}=\emptyset$ .

We denote by $\mathcal{M}_{u}\mathrel{\mathop{\ordinarycolon}}F^{\chi(u)}\rightarrow\mathord% {\{0,1\}}$ a mapping that assigns every labeling $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ a Boolean indicating whether there exists a subset $D_{u}\subseteq V_{u}$ that is consistent with $\varphi_{u}$ according to Definition 26. That is, $\mathcal{M}_{u}(\varphi_{u})=1$ if and only if there exists a set $D_{u}\subseteq V_{u}$ that is consistent with $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ according to Definition 26. The factors of the TD are the mappings $\mathord{\{\mathcal{M}_{u}\mathrel{\mathop{\ordinarycolon}}u\in\texttt{V}({% \mathcal{T}})\}}$ .

Example 27.

Consider node $u$ marked (with a double circle) in Figure 3(b), and an assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ . Note that $N(a)\cap(\texttt{V}_{u}{\setminus}\chi(u))=N(a)\cap\mathord{\{d,e\}}=\emptyset$ . According to Definition 26, every consistent subset $D_{u}\subseteq\texttt{V}_{u}$ can induce only one of $\mathord{\{\sigma_{I},[0]_{\omega},[0]_{\sigma},[0]_{\rho}\}}$ to the vertex $a$ . Equivalently, for any $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ where $\varphi_{u}(a)\notin\mathord{\{\sigma_{I},[0]_{\omega},[0]_{\sigma},[0]_{\rho}\}}$ , it holds that $\mathcal{M}_{u}(\varphi_{u})=0$ .

Consider the labeling where $\varphi_{u}(a)=[0]_{\sigma}$ . If $\varphi_{u}(b)=[1]_{\omega}$ , then by Definition 26 and the fact that $N(b)\cap(\texttt{V}_{u}{\setminus}\chi(u))=\mathord{\{d\}}$ , in any $D_{u}\subseteq\texttt{V}_{u}$ that is consistent with $\varphi_{u}$ , it must hold that $d\in D_{u}$ . But then, $|N(b)\cap D_{u}|=2>1$ , violating the constraint that $|N(b)\cap D_{u}|\leq 1$ . Hence, no such consistent set $D_{u}$ exists, and $\mathcal{M}_{u}(\varphi_{u})=0$ . If $\varphi_{u}(a)=[0]_{\sigma}$ , $\varphi_{u}(b)=[0]_{\omega}$ , and $\varphi_{u}(c)=[1]_{\rho}$ , then by Definition 26 and the fact that $N(c)\cap(\texttt{V}_{u}{\setminus}\chi(u))=\mathord{\{d\}}$ , in any $D_{u}\subseteq\texttt{V}_{u}$ that is consistent with $\varphi_{u}$ , it must hold that $d\in D_{u}$ . Since $d\in D_{u}\cap N(b)$ , then $D_{u}$ cannot be consistent with the assignment $\varphi_{u}(b)=[0]_{\omega}$ . Therefore, $\mathcal{M}_{u}(\varphi_{u})=0$ .

Now, consider the assignment where $\varphi_{u}(a)=[0]_{\sigma}$ , and $\varphi_{u}(b)=\varphi_{u}(c)=[0]_{\omega}$ . In this case $\mathcal{M}_{u}(\varphi_{u})=1$ because the set $D_{u}=\mathord{\{a,e\}}$ is consistent with $\varphi_{u}$ according to Definition 26. Indeed, $N(b)\cap(D_{u}{\setminus}\chi(u))=N(c)\cap(D_{u}{\setminus}\chi(u))=\emptyset$ , hence $D_{u}$ is consistent with label $[0]_{\omega}$ on vertices $b$ and $c$ as required. Since $N(a){\cap}(\texttt{V}_{u}{\setminus}(D_{u}{\cup\chi(u)})=\emptyset$ , then $D_{u}$ is consistent with $\varphi_{u}(a)=[0]_{\sigma}$ . We now consider vertices $\texttt{V}_{u}{\setminus}\chi(u)=\mathord{\{d,e\}}$ . Observe that $N(d)\cap D_{u}=\mathord{\{e\}}$ , and thus $d$ is dominated by $D_{u}$ . Also, $e$ has a private neighbor in $\texttt{V}_{u}{\setminus}D_{u}$ . Indeed, $N(d)\cap D_{u}=\mathord{\{e\}}$ . Figure 3(c) presents other assignments $\varphi_{u}$ to the vertices of $\chi(u)$ where $\mathcal{M}_{u}(\varphi_{u})=1$ , along with the appropriate consistent subsets of vertices (i.e., according to Definition 26).

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 $({\mathcal{T}},\chi)$ , of width $w$ , can be represented using a nice disjoint branch TD $({\mathcal{T}}^{\prime},\chi^{\prime})$ , whose width is at most $2w$ , and how this representation is built in time $O(nw^{2})$ . We start with an example that provides some intuition regarding the requirement for a nice DBTD.

Example 28.

Let $u\in\texttt{V}({\mathcal{T}})$ be a regular (i.e., not disjoint) join node in a nice TD $({\mathcal{T}},\chi)$ , with children $u_{0}$ and $u_{1}$ (Definition 8). Hence, $\chi(u)=\chi(u_{0})=\chi(u_{1})$ . For simplicity, suppose that $\chi(u)=\mathord{\{v\}}$ . Consider the assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ , where $\varphi_{u}(v)=[1]_{\omega}$ . By definition, a subset $D_{u}\subseteq\texttt{V}_{u}$ that is consistent with $\varphi_{u}(v)$ (Definition 26) is such that $|D_{u}\cap N(v)|=1$ . This means that $D_{u}$ includes exactly one neighbor of $v$ in $G_{u_{0}}$ (and no neighbors of $v$ from $G_{u_{1}}$ ), or vice versa. Therefore, to infer whether there exists a subset $D_{u}\subseteq\texttt{V}_{u}$ that is consistent with the assignment $\varphi_{u}=\mathord{\{v\leftarrow[1]_{\omega}\}}$ (i.e., $\mathcal{M}_{u}(\varphi_{u})=1$ ), we need to assign distinct labels to $v$ in the two sub-trees ${\mathcal{T}}_{u_{0}}$ and ${\mathcal{T}}_{u_{1}}$ , corresponding to the induced subgraphs $G_{u_{0}}$ and $G_{u_{1}}$ respectively. Specifically, we need to assign $\varphi_{u_{0}}(v)=[1]_{\omega}$ and $\varphi_{u_{1}}(v)=[0]_{\omega}$ , or $\varphi_{u_{0}}(v)=[0]_{\omega}$ and $\varphi_{u_{1}}(v)=[1]_{\omega}$ . The transformation of Lemma 29 represents $v$ as two distinct vertices $v_{0},v_{1}$ in ${\mathcal{T}}_{u_{0}}$ and ${\mathcal{T}}_{u_{1}}$ respectively, while preserving the integrity of the assignment; that is, $|N(v)\cap D_{u}|=1$ .

The details of the algorithm that generates a nice DBTD from a nice TD $({\mathcal{T}},\chi)$ , 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 $u\in\texttt{V}({\mathcal{T}})$ with children $u_{0}$ and $u_{1}$ to a disjoint join node (see Definition 25). To that end, the algorithm adds a new node $u^{\prime}$ to ${\mathcal{T}}$ , such that $\chi(u^{\prime})\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\chi% (u)\cup\bigcup_{v\in\chi(u)}\mathord{\{v_{0},v_{1}\}}$ , where $v_{0}$ and $v_{1}$ are variables used to represent the neighbors of $v$ in $G[V_{u_{0}}]$ and $G[V_{u_{1}}]$ respectively. Every occurrence of $v$ in ${\mathcal{T}}_{u_{0}}$ is replaced with $v_{0}$ , and every occurrence of $v$ in ${\mathcal{T}}_{u_{1}}$ is replaced with $v_{1}$ . To maintain the niceness of the resulting TD, the algorithm adds $3|\chi(u)|-2$ additional nodes (of type forget and introduce, see details and illustration in [39]). Since $v_{0}$ and $v_{1}$ essentially represent vertex $v$ in $G[V_{u_{0}}]$ and $G[V_{u_{1}}]$ respectively, then certain constraints are placed on the assignments $\varphi_{u^{\prime}}\mathrel{\mathop{\ordinarycolon}}\chi(u^{\prime})\rightarrow F$ associated with node $u^{\prime}$ . For example, $\varphi_{u^{\prime}}(v)\in F_{a}$ if and only if $\varphi_{u^{\prime}}(v_{i})\in F_{a}$ for $a\in\mathord{\{\sigma_{I},\sigma,\rho,\omega\}}$ and $i\in\mathord{\{0,1\}}$ . Another such constraint, for example, is that $\varphi_{u^{\prime}}(v)=[1]_{\omega}$ if and only if $\varphi_{u^{\prime}}(v_{0})=[x_{0}]_{\omega}$ , $\varphi_{u^{\prime}}(v_{1})=[x_{1}]_{\omega}$ , and $x_{0}+x_{1}=1$ . 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 $O(|\chi(u^{\prime})|)$ .

Let $u\in\texttt{V}({\mathcal{T}})$ , and let $\kappa_{u}\mathrel{\mathop{\ordinarycolon}}F^{\chi(u)}\rightarrow\mathord{\{0,% 1\}}$ be the set of local constraints on $F^{\chi(u)}$ that can be verified in time $O(|\chi(u)|)$ . We say that an assignment $\varphi_{u}\in F^{\chi(u)}$ is consistent with $\kappa_{u}$ if $\kappa_{u}(\varphi_{u})=1$ . For a node $u\in\texttt{V}({\mathcal{T}})$ , and local constraints $\kappa_{u}\mathrel{\mathop{\ordinarycolon}}F^{\chi(u)}\rightarrow\mathord{\{0,% 1\}}$ , we let $K_{u}\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\mathord{\{% \varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F\mathrel{% \mathop{\ordinarycolon}}\kappa_{u}(\varphi_{u})=1\}}$ . For a given set of local constraints $\mathord{\{\kappa_{u}\mathrel{\mathop{\ordinarycolon}}u\in\texttt{V}({\mathcal% {T}})\}}$ , and letting $s=|F|$ , the effective width of $({\mathcal{T}},\chi)$ is defined:

{\tt\mathrm{eff{-}tw}}({\mathcal{T}},\chi)\mathrel{\stackrel{{\scriptstyle% \textsf{\tiny def}}}{{=}}}\max_{u\in\texttt{V}({\mathcal{T}})}\lceil\log_{s}|K% _{u}|\rceil

(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 $G$ has a nice TD $({\mathcal{T}},\chi)$ of width $w$ , then there is an algorithm that in time $O(nw^{2})$ constructs a nice disjoint-branch TD $({\mathcal{T}}^{\prime},\chi^{\prime})$ with the following properties:

1.

$\texttt{V}({\mathcal{T}})\subseteq\texttt{V}({\mathcal{T}}^{\prime})$ , where for every node $u\in\texttt{V}({\mathcal{T}})$ , there is a bijection between $\chi(u)$ and $\chi^{\prime}(u)$ .
2.

For every node $u\in\texttt{V}({\mathcal{T}})$ , and every $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ , it holds that $\mathcal{M}_{u}(\varphi_{u})=1$ if and only if $\mathcal{M}^{\prime}_{u}(\varphi^{\prime}_{u})=1$ , where $\varphi^{\prime}_{u}\mathrel{\mathop{\ordinarycolon}}\chi^{\prime}(u)\rightarrow F$ and $\mathcal{M}^{\prime}_{u}$ are the corresponding labeling and factor of node $u$ in $({\mathcal{T}}^{\prime},\chi^{\prime})$ .
3.

The effective width of $({\mathcal{T}}^{\prime},\chi^{\prime})$ is at most $2w$ .

Conditions (1) and (2) of Lemma 29 guarantee that for every node $u\in\texttt{V}({\mathcal{T}})$ , and $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ , a subset $D_{u}\subseteq V_{u}$ is consistent with $\varphi_{u}$ (in $({\mathcal{T}},\chi)$ ) according to Definition 26, if and only if $D_{u}$ is consistent with $\varphi^{\prime}_{u}$ (in $({\mathcal{T}}^{\prime},\chi^{\prime})$ ) according to Definition 26 (following the appropriate name-change to the vertices). This guarantees that, following the preprocessing phase, the generated TD $({\mathcal{T}}^{\prime},\chi^{\prime})$ can be used for enumerating the minimal dominating sets of $G$ . The proof of Lemma 29 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 $({\mathcal{T}},\chi)$ and a set of local constraints $\mathord{\{\kappa_{u}\mathrel{\mathop{\ordinarycolon}}u\in\texttt{V}({\mathcal% {T}})\}}$ , which computes the factor tables $\mathcal{M}_{u}\mathrel{\mathop{\ordinarycolon}}\varphi_{u}\rightarrow\mathord% {\{0,1\}}$ for every labeling $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ , and every node $u\in\texttt{V}({\mathcal{T}})$ , by dynamic programming. The factor tables account for the local constraints. That is, if $\mathcal{M}_{u}(\varphi_{u})=1$ then $\kappa_{u}(\varphi_{u})=1$ . We define $s\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}\max_{v\in\texttt{V% }(G)}|F_{v}|$ , where $F_{v}\subseteq F$ is the set of labels that may be assigned to $v$ .

Lemma 30.

Let $({\mathcal{T}},\chi)$ be a nice DBTD whose width is $w$ , and let $\mathord{\{\kappa_{u}\mathrel{\mathop{\ordinarycolon}}u\in\texttt{V}({\mathcal% {T}})\}}$ be a set of local constraints. There is an algorithm that in time $O(nws^{w})$ computes the factors of $({\mathcal{T}},\chi)$ such that for every $u\in\texttt{V}({\mathcal{T}})$ , and every labeling $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ , it holds that $\mathcal{M}_{u}(\varphi_{u})=1$ if and only if $\kappa_{u}(\varphi_{u})=1$ , and there exists a subset $D_{u}\subseteq V_{u}$ that is consistent with $\varphi_{u}$ according to Definition 26.

5.3 Factor Sizes and Runtime for trans-enum (proof of Corollary 2)

Recall that for every $v\in\texttt{V}(G)$ , we denote by $F_{v}\subseteq F$ the domain of $v$ . That is, $F_{v}$ is the set of labels that may be assigned to $v$ in any labeling $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ where $u\in\texttt{V}({\mathcal{T}})$ and $v\in\chi(u)$ . In Lemma 30, we establish that the dynamic programming over the nice DBTD takes time $O(nws^{w})$ where $w$ is the width of the DBTD, and $s=\max_{v\in\texttt{V}(G)}|F_{v}|$ . In Section 5.2, we show that if ${\tt\mathrm{tw}}(G)=k$ , then $G$ has an embedding to a disjoint-branch TD whose effective width is at most $w=2k$ . This allows us to prove Theorem 1. Next, we show that for trans-enum, every vertex can be assigned only one of $s=5$ labels (i.e., as opposed to $8$ labels), leading to better runtimes of the preprocessing phase, thus proving Corollary 2.

In Section 3, we reduced trans-enum on hypergraph $\mathcal{H}$ to dom-enum over the tripartite graph $B\mathrel{\stackrel{{\scriptstyle\textsf{\tiny def}}}{{=}}}B(\mathcal{H})$ , where $\texttt{V}(B)=\mathord{\{v\}}\cup\texttt{V}(\mathcal{H})\cup\mathord{\{y_{e}% \mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ . By Theorem 9, we are interested in minimal dominating sets $D\in{\mathcal{S}}(B)$ , where $D\subset\mathord{\{v\}}\cup\texttt{V}(\mathcal{H})$ , and $D\neq\texttt{V}(\mathcal{H})$ . In particular, $D\in{\mathcal{S}}(B)$ where $D\cap\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(\mathcal% {H})\}}=\emptyset$ . Therefore, vertices in $\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ can only be assigned labels in $F_{\omega}\cup F_{\rho}$ . If $w\in\texttt{V}(\mathcal{H})$ , then by construction $N(w)\subseteq\mathord{\{v\}}\cup\mathord{\{y_{e}\mathrel{\mathop{% \ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ . Consequently, vertices $w\in\texttt{V}(\mathcal{H})$ can have at most one neighbor in the minimal dominating set; namely the vertex $v$ . Therefore, vertices in $\texttt{V}(\mathcal{H})$ can only be assigned labels in $F_{\sigma}\cup F_{\omega}$ . Finally, the only dominating set of $B$ that excludes $v$ and $\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ , is $\texttt{V}(\mathcal{H})$ . Since we are interested only in minimal transversals that are strictly included in $\texttt{V}(\mathcal{H})$ , then $v$ must be dominating, and can only be assigned labels in $F_{\sigma}$ . So, we get that vertices in $\mathord{\{y_{e}\mathrel{\mathop{\ordinarycolon}}e\in\mathcal{E}(\mathcal{H})\}}$ can only be assigned labels from $F_{\omega}\cup F_{\rho}$ , vertices in $\texttt{V}(\mathcal{H})$ can only be assigned labels in $F_{\sigma}\cup F_{\omega}$ , and the vertex $v$ can only be assigned labels in $F_{\sigma}$ . Since $|F_{\sigma}\cup F_{\omega}|=|F_{\omega}\cup F_{\rho}|=5$ , and $|F_{\sigma}|=3$ , every vertex of $B$ can be assigned one of at most $5$ labels. Therefore, for trans-enum the runtime of the preprocessing phase is in $O(nw5^{w})$ . This proves Corollary 2.

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 30 we establish the correctness and runtime guarantees of the algorithm that receives as input a nice DBTD $({\mathcal{T}},\chi)$ , and a set of local constraints $\mathord{\{\kappa_{u}\mathrel{\mathop{\ordinarycolon}}u\in\texttt{V}({\mathcal% {T}})\}}$ , which computes the factor tables $\mathord{\{\mathcal{M}_{u}\mathrel{\mathop{\ordinarycolon}}u\in\texttt{V}({% \mathcal{T}})\}}$ where $\mathcal{M}_{u}\mathrel{\mathop{\ordinarycolon}}\varphi_{u}\rightarrow\mathord% {\{0,1\}}$ . We represent $\mathcal{M}_{u}$ as a trie where every root-to-leaf path in $\mathcal{M}_{u}$ represents an assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ , or a word in $F^{\chi(u)}$ , such that $\mathcal{M}_{u}(\varphi_{u})=1$ . Let $\chi(u)=\mathord{\{v_{1},\dots,v_{k}\}}$ where the indices represent a complete order over $\chi(u)$ . We view every assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ as a string: $\varphi_{u}(v_{1})\varphi_{u}(v_{2})\cdots\varphi_{u}(v_{k})$ over the alphabet $F$ . In our construction, every string in the trie has precisely $k$ characters from $F$ , where the first character represents the assignment to $v_{1}$ , the second character the assignment to $v_{2}$ , etc. The advantage of this representation is that given an assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ , we can check if $\mathcal{M}_{u}(\varphi_{u})=1$ in $O(k)$ time by traversing the trie from root to leaf to check whether the string $\varphi_{u}(v_{1})\cdots\varphi_{u}(v_{k})$ appears in the trie $\mathcal{M}_{u}$ . In the tabular representation, this requires traversing all assignments in the table, which, in the worst case, takes time $O(|F|^{k})$ . The order used to generate the tries is derived from the complete order $Q$ 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 $O(nw)$ where $n=|\texttt{V}(G)|$ and $w={\tt\mathrm{tw}}(G)$ . By Proposition 19, this requires showing that both IncrementLabeling and IsExtendable are correct and run in time $O(w)$ . The former is established in Lemmas 23 and 24. We present the IsExtendable procedure (Figure 2), prove its correctness, and show that it runs in time $O(w)$ . The input to IsExtendable is the pair $(\mathcal{M},\theta^{i})$ where $\mathcal{M}=({\mathcal{T}},\chi)$ is the nice DBJT (Definition 25) that is the output of the preprocessing phase described in Section 5, and $\theta^{i}\mathrel{\mathop{\ordinarycolon}}V_{i}\rightarrow F$ is an assignment which meets the conditions of Proposition 22. In Lemmas 29 and 30 we established that $\mathcal{M}=({\mathcal{T}},\chi)$ has the property that every node $u\in\texttt{V}({\mathcal{T}})$ is associated with a factor $\mathcal{M}_{u}\mathrel{\mathop{\ordinarycolon}}F^{\chi(u)}\rightarrow\mathord% {\{0,1\}}$ where $\mathcal{M}_{u}(\varphi_{u})=1$ if and only if there exists a subset $D_{u}\subseteq\texttt{V}_{u}$ that is consistent with the assignment $\varphi_{u}\mathrel{\mathop{\ordinarycolon}}\chi(u)\rightarrow F$ according to Definition 26. In Section 5.4, we showed how to check whether $\mathcal{M}_{u}(\varphi_{u})=1$ in time $O(|\chi(u)|)=O(w)$ .

Theorem 31.

IsExtendable returns true iff $\theta^{i}\in\boldsymbol{\Theta}^{i}$ is extendable, and runs in time $O({\tt\mathrm{tw}}(G))$ .

The proof of Theorem 31 relies on the fact that $\mathcal{M}=({\mathcal{T}},\chi)$ is a processed nice disjoint-branch TD. The proof is deferred to the full version of this paper [39].

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 $\gamma$ and $\beta$ -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.

[bib.bib1] [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.

[bib.bib2] [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.

[bib.bib3] [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.

[bib.bib4] [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.

[bib.bib5] [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.

[bib.bib6] [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.

[bib.bib7] [7] Leopoldo E. Bertossi. Database Repairing and Consistent Query Answering. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011. doi:10.2200/S00379ED1V01Y201108DTM020.

[bib.bib8] [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.

[bib.bib9] [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.

[bib.bib10] [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.

[bib.bib11] [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.

[bib.bib12] [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.

[bib.bib13] [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.

[bib.bib14] [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.

[bib.bib15] [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.

[bib.bib16] [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.

[bib.bib17] [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.

[bib.bib18] [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.

[bib.bib19] [19] David Duris. Some characterizations of $\gamma$ and $\beta$ -acyclicity of hypergraphs. Inf. Process. Lett., 112(16):617–620, 2012. doi:10.1016/j.ipl.2012.05.005.

[bib.bib20] [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.

[bib.bib21] [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.

[bib.bib22] [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.

[bib.bib23] [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.

[bib.bib24] [24] Ronald Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM, 30(3):514–550, 1983. doi:10.1145/2402.322390.

[bib.bib25] [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.

[bib.bib26] [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.

[bib.bib27] [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.

[bib.bib28] [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.

[bib.bib29] [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.

[bib.bib30] [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.

[bib.bib31] [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.

[bib.bib32] [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.

[bib.bib33] [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.

[bib.bib34] [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.

[bib.bib35] [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.

[bib.bib36] [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.

[bib.bib37] [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.

[bib.bib38] [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.

[bib.bib39] [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.

[bib.bib40] [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.

[bib.bib41] [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.

[bib.bib42] [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.

[bib.bib43] [43] Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. doi:10.1007/BFb0045375.

[bib.bib44] [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.

[bib.bib45] [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.

[bib.bib46] [46] Sebastian Kruse and Felix Naumann. Efficient discovery of approximate dependencies. Proc. VLDB Endow., 11(7):759–772, 2018. doi:10.14778/3192965.3192968.

[bib.bib47] [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.

[bib.bib48] [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.

[bib.bib49] [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.

[bib.bib50] [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.

[bib.bib51] [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.

[bib.bib52] [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.

[bib.bib53] [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.

[bib.bib54] [54] Günter Rote. Minimal dominating sets in a tree: Counting, enumeration, and extremal results. CoRR, abs/1903.04517, 2019. arXiv:1903.04517.

[bib.bib55] [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.

[bib.bib56] [56] Alexei Vazquez. Optimal drug combinations and minimal hitting sets. BMC Syst. Biol., 3:81, 2009. doi:10.1186/1752-0509-3-81.

[bib.bib57] [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.

[bib.bib58] [58] M. Weyer. Modifizierte parametrische komplexitätstheorie. PhD Thesis, Universität Freiburg, 2008.

[bib.bib59] [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.