PACE Solver Description:
Bad Dominating Set Maker

We reduce both Dominating Set and Hitting Set to the following problem:

Problem

Directed Constrained Domination

Input:

A directed graph $G=(V,A)$, a subsumed set $S\subseteq V$ and a dominated set $D\subseteq V$.

Want:

A set $DS(G)\subseteq V\setminus S$ of minimum size, such that $\forall v\in V\setminus D,\exists u\in DS(G),uv\in A$.

Note that $A$ can contain arcs in both directions between two vertices, as well as self-loops. The transformation from Dominating Set to Directed Constrained Domination is trivial: the vertex set is the same, every edge is replaced by arcs in both directions, and no vertex is flagged as subsumed or dominated. Moreover, each vertex gets a self-loop.

For Hitting Set, create a dominated vertex for each element of the universe (i.e., the vertices of the hypergraph), and then a subsumed vertex for each set (i.e., each hyperedge). Add arcs from each dominated vertex to the subsumed vertices representing the sets it belongs to in the Hitting Set instance. Thus, any set will be hit if and only if the solution for Directed Constrained Domination contains a vertex belonging to this set. We have been made aware that a similar generalization of dominating set and some of our reduction rules have been presented in a recent IJCAI paper [10].

In the following, we assume any directed graph $G$ to be implicitly accompanied by its labeling of subsumed and dominated vertices, and denote a solution to the corresponding Directed Constrained Domination problem as $DS(G)$. We use $[k]$ to denote $\{1,\mathrm{\dots },k\}$ for $k\in \mathbb{N}$. For a vertex $v$ or set of vertices $X$, we define $N_{\text{out}}(v)$ and $N_{\text{out}}(X)$ as its out-neighborhood and $N_{\text{in}}(v)$ and $N_{\text{in}}(X)$ as its in-neighborhood (including self-loops).

Observe that the corresponding Max Sat instances (see Section 3) before and after applying the reduction rules are exactly the same. $◀$

The following two rules, following principles identified in rules 6 and 7 of [7], require more care when translating to our setting. Our first special rule is a generalization of rule number 6, considering that we do not have control over the maximal size of out-neighborhoods, and thus we need to compute a very local dominating set instead of simply counting elements. For efficient implementation, we want to apply the second special reduction rule several times without applying the subsumption reduction rule 6 between uses. Because of this, we need to make sure that some vertices do not have the same in-neighborhoods before reducing.

Note that, instead of applying this last reduction rule in one go, we instead iteratively apply it to individually remove leaf blocks of the block-cut-tree [4], and restrict this to blocks containing at most 25% of all vertices. This simplifies the implementation while avoiding multiple computations of a solution for large blocks, and also allows us to short-cut the computations in cases where we conclude that an optimal solution has already been found.

We use the htd library with the mindegree strategy to seek a nice tree-decomposition of small width [1]. If we obtain such a decomposition, we use a dynamic program to solve the instance in time $𝒪(3^{\text{tw}})$. To achieve this running time, our approach combines two different setups of the approach described in [8].

Namely, for join nodes, we consider tables where the state of the vertices are $1$, $0_{\mathrm{?}}$ and $0_0$, whereas for introduce and forget nodes we consider the states $1$, $0_1$ and $0_0$. $1$ means the vertex is selected in the solution, $0_1$ that it is not in the solution but neighbor to a vertex in the solution, $0_0$ that it is neither in the solution nor has a neighbor in the solution. The additional $0_{\mathrm{?}}$ state (which is introduced to make the table computation at join nodes faster) corresponds to a vertex not selected in the solution, without information about its neighborhood. Our algorithm then translates the tables from one format to another according to the type of node we encounter in the tree decomposition. Additionally, we need to restrict the possible states for some vertices to adapt the algorithm to our needs: any subsumed vertex cannot be given state $1$, and any dominated vertex can be given the state $0_1$ (or $0_{\mathrm{?}}$) for free.

We remark that some instances are encoding Vertex Cover in the following sense: if all the vertices with incoming arcs (i.e., the vertices needing to be dominated) have in-degree exactly $2$, the instance corresponds to an instance of Vertex Cover where vertices with outgoing arcs are vertices, and vertices with ingoing arcs are edges between their two neighbors (a vertex can serve as an edge and a vertex simultaneously in this sense). For such instances with less than $1000$ unsubsumed vertices, we run the exact solver Peaty for a maximum of 5 minutes [6].

As final step we encode a remaining instance as SAT formula and use EvalMaxSAT to solve it [2]. The encoding is straight-forward, representing each vertex with a clause ensuring that at least one of its in-neighbors is selected. The selection of any vertex has a weight of $-1$, meaning as few vertices as possible are selected.

To improve the performance in our setting, we provide two adjustments. First, we use an adaptative time-out for the core improvement subroutine of the solver, to spend less time when we believe the lower bound to be already optimal. The second improvement takes care of providing an alternative initial lower bound to the solver: we look for a large matching in the accessory graph where there is an edge between two vertices if this pair is exactly the in-neighborhood of some vertex in the Directed Constrained Domination instance. Such a matching always provides an initial core for the Solver.