Solving Partial Dominating Set and Related Problems Using Twin-Width

Balabán, Jakub; Mock, Daniel; Rossmanith, Peter

doi:10.4230/LIPIcs.MFCS.2025.13

Solving Partial Dominating Set and Related Problems Using Twin-Width

Jakub Balabán

Faculty of Informatics, Masaryk University, Brno, Czech Republic Daniel Mock

Dept. of Computer Science, RWTH Aachen University, Germany Peter Rossmanith

Dept. of Computer Science, RWTH Aachen University, Germany

Abstract

Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are $\rm W[1]$ -hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form $\phi\equiv\exists x_{1}\cdots\exists x_{k}\sum_{\alpha\in I}\#y\,\psi_{\alpha}% (x_{1},\ldots,x_{k},y)\geq t$ , where $\psi_{\alpha}$ is a quantifier-free formula for each $\alpha\in I$ , $t$ is an arbitrary number, and $\#y$ is a counting quantifier, can be evaluated in time $f(d,k)n$ , where $n$ is the number of vertices and $d$ is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.

Keywords and phrases:

Partial Dominating Set, Partial Vertex Cover, meta-algorithm, counting logic, twin-width

Funding:

Jakub Balabán: Brno Ph.D. Talent Scholarship Holder – Funded by the Brno City Municipality.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Parameterized complexity and exact algorithms

Related Version:

Full Version: https://arxiv.org/abs/2504.18218 [3]

Acknowledgements:

We would like to thank one of the anonymous reviewers for suggesting a generalization of the logic we considered that also captures the Partial Vertex Cover problem.

Funding:

Daniel Mock and Peter Rossmanith: Supported by the Deutsche Forschungsgemeinschaft (DFG, German Science Foundation) – DFG-927/15-2

DOI:

10.4230/LIPIcs.MFCS.2025.13

Event:

50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Editors:

Paweł Gawrychowski, Filip Mazowiecki, and Michał Skrzypczak

Series and Publisher:

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

1 Introduction

Vertex Cover, Independent Set, and Dominating Set are well-known graph problems that have driven significant advancements in parameterized complexity theory. Despite being NP-complete, these problems motivated the development of new approaches, as the difficulty of finding solutions of size $k$ appears to increase significantly from one problem to the next [15]. On general graphs, Vertex Cover has been found to be fixed-parameter tractable, while Independent Set is $\rm W[1]$ -complete and Dominating Set is $\rm W[2]$ -complete. Consequently, researchers have designed faster algorithms for solving Vertex Cover on general graphs [9, 4, 7, 8, 10, 14, 36, 37, 40], while identifying more and more general graph classes that admit fixed-parameter algorithms for the other two problems. This progression started with planar graphs [1] and led to nowhere-dense graph classes via intermediate results [13, 19, 38, 12]. All three problems can be expressed in first-order logic, and significant advances have been made in meta-algorithm design to solve the first-order model-checking problem. This progression begins with bounded-degree graphs, continues through bounded genus, minor-closed, bounded expansion, nowhere-dense, and finally monadically stable classes [39, 22, 20, 11, 25, 16].

Twin-width is a recently introduced width measure that generalizes clique-width [6]. Classes of bounded twin-width do not contain bounded degree graph classes and are not necessarily monadically stable. They are therefore incomparable to the sparsity hierarchy. Bonnet et al. have developed a parameterized algorithm for first-order model-checking on classes of bounded twin-width [6]. Please note that, unlike tree-width, there is no efficient way known to compute or even approximate twin-width. Moreover, most twin-width based algorithms, including first-order model-checking, require as part of the input not only the graph but also a contraction sequence. The contraction sequence proves that the graph has small twin-width and guides an algorithm. This guidance can be compared to that of dynamic programming on tree decompositions. An optimal tree decomposition can, however, be relatively efficiently computed and even faster approximated. In the world of sparsity algorithms operating in classes of bounded expansion or nowhere-dense classes, the situation is even better: no underlying structure is needed; the algorithm works correctly on every graph but becomes slow when applied outside its scope.

While this represents a significant body of work on Vertex Cover, Independent Set, Dominating Set, and many other first-order expressible problems, the story does not end here. In Vertex Cover, you ask for $k$ nodes that cover all edges, and in Dominating Set, you seek $k$ nodes that dominate all other nodes. Generalizations of these problems are the partial versions: given $k$ and $t$ , are there $k$ nodes that cover $t$ edges or are there $k$ nodes that dominate $t$ nodes? These problems are known as Partial Vertex Cover and Partial Dominating Set; note that in the parameterized setting, $k$ is the parameter. As generalizations, they turn out to be harder than their complete counterparts. For example, while Vertex Cover is fixed-parameter tractable on general graphs, Partial Vertex Cover has been shown to be $\rm W[1]$ -hard [26], and while Dominating Set is fixed-parameter tractable on degenerate graphs, Partial Dominating Set is $\rm W[1]$ -hard [24]. However, it is fixed-parameter tractable with respect to $t$ even on general graphs [29]. Another example of how the partial variant can be harder are $c$ -closed graphs, where non-adjacent vertices share at most $c$ neighbors. Dominating Set is fixed-parameter tractable for bounded $c$ [30], while Partial Dominating Set becomes a hard problem even for $c=2$ [28].

Another sequence of papers has demonstrated that Partial Dominating Set can be solved in time $f(k)n^{O(1)}$ for larger and larger graph classes. Amini, Fomin, and Saurabh developed an algorithm with a running time of $O(f(k)\cdot t\cdot n^{C_{H}})$ for the class of $H$ -minor-free graphs, where $C_{H}$ is a constant dependent only on $H$ . The graph classes with bounded expansion and nowhere-dense graph classes introduced in the sparsity project by Nešetřil and Ossona de Mendez [35] contain all $H$ -minor-free classes. For bounded expansion, there exists a meta-algorithm that solves many problems, including Partial Dominating Set in linear fixed-parameter tractable time, i.e., in $f(k)n$ steps [18]. Additionally, for nowhere-dense classes, there is a more restricted meta-algorithm that is general enough to solve Partial Dominating Set in time $O(f(k)n^{1+\epsilon})$ for every $\epsilon>0$ [17].

The “simpler” Partial Vertex Cover has not seen as much attention, but has still been investigated as well; see, for example [32, 21, 33].

Our contribution.

We demonstrate that both Partial Dominating Set and Partial Vertex Cover can be solved efficiently on graph classes with bounded twin-width. To achieve this, we develop two dynamic programming algorithms that work along a contraction sequence provided as part of the input. Interestingly, both algorithms share similarities in their complexity, while usually Partial Vertex Cover is the much easier problem. The algorithms are based on ideas developed by Bonnet et al. in order to solve the (complete) Dominating Set problem on bounded twin-width [5].

Having separate algorithms for related problems is not ideal and it would be beneficial to have them emerge as special cases within a more comprehensive framework. Again, the language of logic could facilitate this. We present a meta-algorithm that solves the model-checking problem for formulas of the form $\phi\equiv\exists x_{1}\cdots\exists x_{k}\#y\,\psi(x_{1},\ldots,x_{k},y)\geq t$ where $\psi$ must be quantifier-free (this logic was considered in [17]). Such a formula is true in a graph $G=(V,E)$ if it contains nodes $v_{1},\ldots,v_{k}$ such that $\psi(v_{1},\ldots,v_{k},u)$ holds for at least $t$ many nodes $u\in V$ . For instance, with $\psi(x_{1},\ldots,x_{k},y)=\bigvee_{i=1}^{k}(E(x_{i},y)\lor x_{i}=y)$ , we can solve Partial Dominating Set. With a quantifier-free $\psi$ , we can express numerous other intriguing problems, including Connected Partial Dominating Set and Independent Partial Dominating Set, as well as more exotic ones like “Are there $k$ nodes that are all part of triangles and dominate at least $t$ of all other nodes?” or “How many vertices do we have to delete in order to get a $2$ -independent set of size $k$ ?” (see [27, 2] for applications). The time needed to decide $G\models\phi$ is $d^{O(k^{2}d)}n$ , which is linear FPT time. “Linear” means that the input has to be shorter than the classical encoding of the underlying graph as an adjacency list or adjacency matrix. While graphs of bounded twin-width can have a quadratic number of edges, they can still be encoded via their much shorter contraction sequence [6, 23]. Note that our single-purpose algorithm for Partial Dominating Set achieves a better running time of $(kd)^{\mathcal{O}(kd)}n$ .

Our meta-algorithm can, in fact, model-check even more general formulas, namely formulas of the form $\phi\equiv\exists x_{1}\cdots\exists x_{k}\sum_{\alpha\in I}\#y\,\psi_{\alpha}% (x_{1},\ldots,x_{k},y)\geq t$ , where $\psi_{\alpha}$ is a quantifier-free formula for each $\alpha\in I$ . Such a formula $\phi$ is true if the sum of the numbers of vertices $y$ satisfying the formulas $\psi_{\alpha}$ is at least $t$ . Using such a formula, we can also express the Partial Vertex Cover problem, see Example 15.

Finally, let us remark that if we take a power of a graph, then its twin-width remains small [6]. This simple observation allows us to tackle the “distance- $r$ ” variants of Partial Dominating Set as well by using transductions.

2 Preliminaries

For integers $i$ and $j$ , we let $[i,j]:=\{n\in\mathbb{N}\colon i\leq n\leq j\}$ and $[i]:=[1,i]$ . We study finite, simple and undirected graphs with non-empty vertex set.

Twin-width.

A trigraph $G$ is a graph whose edge set is partitioned into a set of black and red edges. The set of red edges is denoted $R(G)$ , and the set of black edges $B(G)$ ; standard graphs are viewed as trigraphs with no red edges. The red graph $G^{R}$ of $G$ is the graph $(V(G),R(G))$ and the black graph $G^{B}$ of $G$ is the graph $(V(G),B(G))$ . Any graph-theoretic notion with a color adjective (black or red) has its standard meaning applied in the corresponding graph. For example, the red degree of $u\in V(G)$ in $G$ is its degree in $G^{R}$ .

Given a trigraph $G$ , a contraction of two distinct vertices $u,v\in V(G)$ is the operation which produces a new trigraph by (1) removing $u, v$ and adding a new vertex $w$ , (2) adding a black edge $w x$ for each $x\in V(G)$ such that $x u$ , $xv\in B(G)$ , and (3) adding a red edge $w y$ for each $y\in V(G)$ such that $yu\in R(G)$ , or $yv\in R(G)$ , or $y$ contains only a single black edge to either $v$ or $u$ . A sequence $C=(G=G_{1},\ldots,G_{n})$ is a contraction sequence of $G$ if it is a sequence of trigraphs such that $|V(G_{n})|=1$ and for all $i\in[n-1]$ , $G_{i+1}$ is obtained from $G_{i}$ by contracting two vertices. The width of a contraction sequence $C$ is the maximum red degree over all vertices in all trigraphs in $C$ . The twin-width of $G$ is the minimum width of any contraction sequence of $G$ . An example of a contraction sequence is provided in Figure 1.

Figure 1: A contraction sequence of width 2 for the leftmost graph, consisting of

6

trigraphs.

If a contraction sequence $C=(G_{1},\ldots,G_{n})$ of $G$ is clear from context, then for each $i\in[n]$ and $u\in V(G_{i})$ , we call the set of vertices of $G$ contracted to $u$ the bag of $u$ and we denote it $\beta(u)$ . Formally, $\beta(u)=\{u\}$ if $u\in V(G)$ , and $\beta(u)=\beta(v)\cup\beta(w)$ if there is $i\in[2,n]$ such that $u\in V(G_{i})$ , $v,w\in V(G_{i-1})$ , and $u$ is created by contracting $v$ and $w$ . Note that if a vertex appears in multiple trigraphs in $C$ , then its bag is the same in all of them. If $T\subseteq V(G_{i})$ for some $i\in[n]$ , then we use $\beta(T)$ to denote $\bigcup_{u\in T}\beta(T)$ .

Basic profiles.

Now we define basic profiles, inspired by the $k$ -profiles in the Dominating Set algorithm from [5]. Intuitively, a profile describes a “type” of a subsolution we compute during our dynamic algorithms. For each profile, we will compute a subsolution that is, in some sense, best for the profile. In the end, we can read the answer to our problem from the profiles associated with the last trigraph $G_{n}$ in the contraction sequence.

In the following sections, we will expand the basic profiles with extra information in two different ways: to extended profiles, which we will use to solve Partial Dominating Set and Partial Vertex Cover in Section 3, and to virtual profiles, which we will use for the model-checking in Section 4. Note that the $k$ -profiles in [5] can also be viewed as extensions of our basic profiles. After defining the basic profiles, we will prove some of their properties, which we will later generalize to the extended and virtual profiles.

Let us fix a graph $G$ , a contraction sequence $(G=G_{1},\ldots,G_{n})$ of width $d$ , and an integer $k\in\mathbb{N}$ .

Definition 1.

If $i\in[n]$ , then a basic $i$ -profile is a pair $(T,D)$ such that $T\subseteq V(G_{i})$ , $|T|\leq k(d+1)$ , $T$ is connected in $G_{i}^{R}$ , $D\subseteq T$ , and $|D|\leq k$ .

For example, in the Partial Vertex Cover algorithm, $k$ will be the number of covering vertices, $D$ will be the set such that the covering vertices are in $\beta(D)$ , and $T$ is the “context” in which the cover is considered, i.e., we are interested in which edges of $G[\beta(T)]$ are covered (this intuition will be formalized in Definition 5).

Figure 2: Right: A basic

i

-profile

\pi=(T,D)

. Vertices of

T

are colored in gray, and vertices of

D

have thick boundary. The new vertex of

G_{i}

is represented by the bigger disc. Left: A

D^{\prime}

-decomposition

\{(T_{1},D_{1}),\ldots,(T_{4},D_{4})\}

of

\pi

. The sets

T_{1},\ldots,T_{4}

are represented by the colors blue, green, yellow, and pink. Vertices of

D^{\prime}

have thick boundary, and the two vertices to be contracted are inside a dashed rectangle.

Now we define how a basic $i$ -profile can be decomposed into several basic $(i-1)$ -profiles, again inspired by [5]. Later, we will analogously define decompositions for extended and virtual profiles.

Let $i\in[2,n]$ , let $v\in V(G_{i})$ be the new vertex in $G_{i}$ , let $u_{1},u_{2}\in V(G_{i-1})$ be the two vertices contracted into $v$ , let $\pi=(T,D)$ be a basic $i$ -profile such that $v\in T$ , and let $T^{\prime}=(T\setminus v)\cup\{u_{1},u_{2}\}$ . We say that a set $D^{\prime}\subseteq T^{\prime}$ is compatible with $\pi$ if $D\setminus\{v\}=D^{\prime}\setminus\{u_{1},u_{2}\}$ , $|D^{\prime}|\leq k$ , and $v\in D$ if and only if $u_{1}\in D^{\prime}$ or $u_{2}\in D^{\prime}$ . Note that the condition $|D^{\prime}|\leq k$ is necessary only to prohibit the case $|D|=k$ and $u_{1},u_{2}\in D^{\prime}$ .

We say that a set $\{(T_{1},D_{1}),\ldots,(T_{m},D_{m})\}$ of basic $(i-1)$ -profiles is a $D^{\prime}$ -decomposition of $\pi$ , see Figure 2, if:

1.

The sets $T_{1},\ldots,T_{m}$ are pairwise disjoint.
2.

$T^{\prime}=\bigcup_{j\in[m]}T_{j}$ , $D^{\prime}=\bigcup_{j\in[m]}D_{j}$ , and $D^{\prime}$ is compatible with $\pi$ .
3.

If $x\in T_{j}$ and $y\in D_{\ell}$ for $j\neq\ell$ , then $xy\notin R(G_{i-1})$ .

Let us give some intuition behind condition 3. If $y\in D_{\ell}$ , then there is a dominating (resp. covering) vertex $y^{\prime}\in\beta(y)$ . If $xy\in R(G_{i-1})$ , then we would not know which vertices of $\beta(x)$ are dominated by $y^{\prime}$ (resp. how many edges in $\{x^{\prime}y^{\prime}\colon x^{\prime}\in\beta(x)\}$ are covered by $y^{\prime}$ ). Hence, the connections between profiles must be homogeneous (either a black edge or a non-edge).

Now let us prove that a small decomposition always exists (and can be found efficiently).

Lemma 2.

If $i\in[2,n]$ , $V(G_{i})\setminus V(G_{i-1})=\{v\}$ , $V(G_{i-1})\setminus V(G_{i})=\{u_{1},u_{2}\}$ , $\pi=(T,D)$ is a basic $i$ -profile such that $v\in T$ , $T^{\prime}=(T\setminus v)\cup\{u_{1},u_{2}\}$ , and $D^{\prime}\subseteq T^{\prime}$ is compatible with $\pi$ , then there is a $D^{\prime}$ -decomposition $\mathcal{D}$ of $\pi$ containing at most $d+2$ basic $(i-1)$ -profiles. Moreover, $\mathcal{D}$ can be found in time $\mathcal{O}(kd^{2})$ .

Proof.

Let $\{T_{1},\ldots,T_{m}\}$ be the connected components of $T^{\prime}$ in $G_{i-1}^{R}$ and let $D_{j}=T_{j}\cap D^{\prime}$ for each $j\in[m]$ . Observe that $(T_{j},D_{j})$ is a basic $(i-1)$ -profile if and only if $|T_{j}|\leq k(d+1)$ . Hence, if $|T_{j}|\leq k(d+1)$ for each $j\in[m]$ , then $\{(T_{1},D_{1}),\ldots,(T_{m},D_{m})\}$ is a $D^{\prime}$ -decomposition of $\pi$ ; condition 3 is satisfied because there are no red edges between distinct $T_{j}$ and $T_{\ell}$ . Let $j\in[m]$ and observe that since $T$ is connected in $G_{i}^{R}$ , there is a vertex $u\in T_{j}$ such that either $uv\in R(G_{i})$ or $u\in\{u_{1},u_{2}\}$ . Since $v$ has red degree at most $d$ in $G_{i}$ , we have $m\leq d+2$ as required.

Now suppose that $|T_{j}|>k(d+1)$ for some $j\in[m]$ . Since $|T|\leq k(d+1)$ and $T_{j}\subseteq T^{\prime}$ , we deduce that $|T_{j}|=k(d+1)+1$ , $m=j=1$ , and $(T_{j},D_{j})=(T^{\prime},D^{\prime})$ . Since each vertex in $D^{\prime}$ has red degree at most $d$ in $G_{i-1}$ and $|D^{\prime}|\leq k$ , there is a vertex $w\in T^{\prime}\setminus D^{\prime}$ such that $wx\notin R(G_{i-1})$ for each $x\in D^{\prime}$ . Let $\{T_{1}^{\prime},\ldots,T_{p}^{\prime}\}$ be the connected components of $T^{\prime}\setminus\{w\}$ in $G_{i-1}^{R}$ and let $D_{j}^{\prime}=T_{j}^{\prime}\cap D^{\prime}$ for each $j\in[p]$ . Now observe that $\{(T_{1}^{\prime},D_{1}^{\prime}),\ldots,(T_{p}^{\prime},D_{p}^{\prime})\}\cup% \{(\{w\},\emptyset)\}$ is a $D^{\prime}$ -decomposition of $\pi$ . Since $T_{j}^{\prime}$ contains a vertex adjacent to $w$ in $G_{i-1}^{R}$ for each $j\in[p]$ , we have $p+1\leq d+2$ as required.

Observe that the proof naturally translates into an algorithm finding the desired decomposition and that all the operations can be performed in time linear in $|T^{\prime}|+|R(G_{i-1}[T^{\prime}])|$ . Since $|T^{\prime}|\leq k(d+1)+1$ and each vertex of $T^{\prime}$ has red degree at most $d$ in $G_{i-1}$ , there are $\mathcal{O}(kd^{2})$ red edges in $G_{i-1}[T^{\prime}]$ , and so the stated running time is achieved. $\hfill\blacktriangleleft$

Now we prove that the number of basic $i$ -profiles containing any fixed vertex of $G_{i}$ is small.

Lemma 3.

If $i\in[n]$ and $v\in V(G_{i})$ , then the number of basic $i$ -profiles $(T,D)$ such that $v\in T$ is in $d^{\mathcal{O}(kd)}$ . Moreover, such profiles can be enumerated in time $d^{\mathcal{O}(kd)}$ .

3 Partial Dominating Set and Vertex Cover

In this section, we show that the following parameterized problems are fixed-parameter tractable. When a graph $G$ is clear from context, we denote the closed neighborhood of $S\subseteq V(G)$ in $G$ by $N[S]$ , i.e., $N[S]=S\cup\{u\in V(G)\colon u$ has a neighbor in $S\}$ .
Partial Dominating Set using twin-width
Input: A graph $G$ , a contraction sequence for $G$ of width $d$ , integers $k$ and $t$
Question: Is there a set $S\subseteq V(G)$ of size $k$ such that $|N[S]|\geq t$ ?
Parameter: $k+d$
Partial Vertex Cover using twin-width
Input: A graph $G$ , a contraction sequence for $G$ of width $d$ , integers $k$ and $t$
Question: Is there a set $S\subseteq V(G)$ of size $k$ such that at least $t$ edges have an endpoint in $S$ ?
Parameter: $k+d$

Henceforth, we refer to these problems simply as Partial Dominating Set and Partial Vertex Cover.

3.1 Extended Profiles

For both of these problems, we will need a notion of a profile, obtained by extending basic profiles introduced in Section 2. Let us fix a graph $G$ , a contraction sequence $(G=G_{1},\ldots,G_{n})$ of width $d$ , and an integer $k$ .

Definition 4.

Let $i\in[n]$ and let $\pi=(T,D)$ be basic $i$ -profile. An extended $i$ -profile is a tuple $\pi^{\prime}=(T,D,M,f)$ such that $M\subseteq T$ and $f\colon T\rightarrow[0,k]$ is a function such that $\sum_{u\in T}f(u)\leq k$ and for each $u\in T$ , $f(u)\leq|\beta(u)|$ , and $D=\{u\in T\colon f(u)\neq 0\}$ .

Informally, the function $f$ specifies the distribution of the dominating (resp. covering) vertices across $D$ , and the set $M$ specifies which bags we want to dominate vertices in. Note that for Partial Vertex Cover, $M$ will not be used, i.e., $M=\emptyset$ will always hold (this allows us to use the same definition of a profile for both problems). The following definition formalizes this idea.

Definition 5.

Let $i\in[n]$ and let $\pi=(T,D,M,f)$ be an extended $i$ -profile. A set $S\subseteq\beta(T)$ is a solution of $\pi$ if for every $u\in T$ , $f(u)=|S\cap\beta(u)|$ . We define the dominating-set-value of $S$ in $\pi$ as $|N[S]\cap\beta(M)|$ and the vertex-cover-value of $S$ in $\pi$ as $|\{uv\in E(G)\colon u\in S,v\in\beta(T)\}|$ .

Note that each set $S\subseteq V(G)$ can be a solution of more than one extended $i$ -profile for each $i\in[n]$ . Indeed, $S$ determines only $D$ and $f$ , whereas there are more choices of $T$ and $M$ ( $T$ can be any small red-connected set containing $D$ ). However, it will always be clear from context which profile a solution belongs to, and so we will often simply say, e.g., the dominating-set-value of $S$ (omitting “in $\pi$ ”).

Let us give a quick informal overview of how the profiles will be used to solve Partial Dominating Set. During the algorithm, we proceed through each time $i$ ranging from $1$ to $n$ and compute for each extended $i$ -profile $\pi$ its optimal value; that is, the maximum value $t$ such that a solution of $\pi$ dominates $t$ vertices from $\beta(M)$ . To compute the optimal value, we need to decompose the profile: each decomposition is a small set of extended $(i-1)$ -profiles, see Section 3.2 for a formal definition. Crucially, each solution of $\pi$ is described by some decomposition, and the best solution described by a decomposition $\mathcal{D}=\{\pi_{1},\ldots,\pi_{m}\}$ can be computed from the optimal solutions of the profiles in $\mathcal{D}$ (which were computed in the previous iteration). Hence, the optimal solution of $\pi$ can be computed by trying all possible decompositions. More precisely, we do not try all decompositions but only one decomposition of each “type”. Finally, to determine how many vertices can be dominated by a set of size $k$ in $G$ , it suffices to examine the optimal value of one particular $n$ -profile $\pi$ (note that $G_{n}$ consists of a single vertex, and so it is easy to define $\pi$ explicitly). We get this value at the end of the run of Algorithm 1.

Let us now show that the number of extended $i$ -profiles containing any fixed vertex of $G_{i}$ is bounded.

Lemma 6.

If $i\in[n]$ and $v\in V(G_{i})$ , then the number of extended $i$ -profiles $(T,D,M,f)$ such that $v\in T$ is in $2^{\mathcal{O}(kd\log(kd))}$ . Moreover, such profiles can be enumerated in time $2^{\mathcal{O}(kd\log(kd))}$ .

3.2 Extended Decompositions

Now we generalize the $D^{\prime}$ -decompositions defined in Section 2 to extended profiles.

Let $i\in[2,n]$ , let $v\in V(G_{i})$ be the new vertex in $G_{i}$ , let $u_{1},u_{2}\in V(G_{i-1})$ be the two vertices contracted into $v$ , let $\pi_{0}=(T,D)$ be a basic $i$ -profile such that $v\in T$ , let $T^{\prime}=T\setminus\{v\}\cup\{u_{1},u_{2}\}$ , and let $\pi=(T,D,M,f)$ be an extended $i$ -profile. Let $\hat{M}=M\setminus\{v\}\cup\{u_{1},u_{2}\}$ if $v\in M$ , and $\hat{M}=M$ otherwise. We say that a function $f^{\prime}\colon T^{\prime}\rightarrow[0,k]$ is compatible with $\pi$ if $f(v)=f^{\prime}(u_{1})+f^{\prime}(u_{2})$ , $f^{\prime}(u_{1})\leq|\beta(u_{1})|$ , $f^{\prime}(u_{2})\leq|\beta(u_{2})|$ , and for each $u\in T\setminus\{v\}$ , $f(u)=f^{\prime}(u)$ . Note that there is at least one function compatible with $\pi$ because $f(v)\leq|\beta(v)|$ .

Let us fix a function $f^{\prime}$ compatible with $\pi$ , let $D^{\prime}=\{u\in T^{\prime}\colon f^{\prime}(u)\neq 0\}$ , and let $M^{\prime}$ be the set defined as follows.

M^{\prime}=\{u\in\hat{M}\colon u\text{ has no black neighbor in }D^{\prime}% \text{ in }G_{i-1}\}.

(1)

We say that a set of extended $(i-1)$ -profiles $\mathcal{D}=\{(T_{j},D_{j},M_{j},f_{j})\colon j\in[m]\}$ is an $f^{\prime}$ -decomposition of $\pi$ if $f^{\prime}=\bigcup_{j\in[m]}f_{j}$ , $D^{\prime}=\bigcup_{j\in[m]}D_{j}$ , $M^{\prime}=\bigcup_{j\in[m]}M_{j}$ , and $\{(T_{1},D_{1}),\ldots,(T_{m},D_{m})\}$ is a $D^{\prime}$ -decomposition of $\pi_{0}$ .

$\blacktriangleright$ Remark 7.

Equation 1 allows us to avoid double-counting in the algorithm for Partial Dominating Set. Indeed, if $u\in\hat{M}$ has a black neighbor $w$ in $D^{\prime}$ , then all vertices in $\beta(u)$ are dominated by some vertex in $\beta(w)$ . Hence, if we added $u$ to some $M_{j}$ , then vertices in $\beta(u)$ would be counted as dominated twice.

Now we prove that a small $f^{\prime}$ -decomposition exists for each $f^{\prime}$ compatible with $\pi$ .

Lemma 8.

If $i\in[2,n]$ , $V(G_{i})\setminus V(G_{i-1})=\{v\}$ , $V(G_{i-1})\setminus V(G_{i})=\{u_{1},u_{2}\}$ , $\pi=(T,D,M,f)$ is an extended $i$ -profile such that $v\in T$ , $T^{\prime}=T\setminus\{v\}\cup\{u_{1},u_{2}\}$ , and $f^{\prime}\colon T^{\prime}\rightarrow[0,k]$ is a function compatible with $\pi$ , then there is an $f^{\prime}$ -decomposition $\mathcal{D}$ of $\pi$ with cardinality at most $d+2$ . Moreover, $\mathcal{D}$ can be found in time $\mathcal{O}(k^{2}d^{2})$ .

The following lemma shows that a solution of a profile $\pi$ can be constructed by “merging” the solutions of profiles in a decomposition of $\pi$ .

Lemma 9.

If $i\in[2,n]$ , $\pi$ is an extended $i$ -profile, $\{\pi_{j}\colon j\in[m]\}$ is an $f^{\prime}$ -decomposition of $\pi$ , and $S_{j}$ is a solution of $\pi_{j}$ for each $j\in[m]$ , then $S:=\bigcup_{j\in[m]}S_{j}$ is a solution of $\pi$ .

3.3 Partial Dominating Set

Let $(G,C=(G_{1},\ldots,G_{n}),k,t)$ be an instance of the Partial Dominating Set problem; recall that $C$ is a contraction sequence of width $d$ . In this section, we show that Algorithm 1 solves the problem in time $(dk)^{\mathcal{O}(dk)}n$ , see Theorem 13. For an outline of the algorithm, see Section 3.1.

We will use the notion of extended profiles, see Definition 4, and the notion of solutions, see Definition 5. Instead of the dominating-set-value of a solution, we will say simply the value. We say that a solution $S$ is an optimal solution of an extended profile $\pi$ if no other solution of $\pi$ has higher value than $S$ .

Before presenting the algorithm, let us make two key observations.

Lemma 10.

Let $i\in[2,n]$ , $\pi$ be an extended $i$ -profile, $\{(T_{j},D_{j},M_{j},f_{j})\colon j\in[m]\}$ be an $f^{\prime}$ -decomposition of $\pi$ , $S$ be a solution of $\pi$ , and $S_{j}=S\cap\beta(T_{j})$ for each $j\in[m]$ . For each $j\in[m]$ :

a)

The value of $S_{j}$ equals $|N[S]\cap\beta(M_{j})|$ .
b)

If $u\in T_{j}$ has a black neighbor in $D_{\ell}$ for some $\ell\in[m]$ , then $\beta(u)\subseteq N[S]$ .

Proof.

For a), let us fix $j\in[m]$ . It suffices to prove that $N[S_{j}]\cap\beta(M_{j})=N[S]\cap\beta(M_{j})$ . Suppose for contradiction that there are vertices $u_{0}\in\beta(M_{j})$ and $v_{0}\in S\setminus S_{j}$ such that $u_{0}v_{0}\in E(G)$ . Let $u,v\in V(G_{i-1})$ be such that $u_{0}\in\beta(u)$ and $v_{0}\in\beta(v)$ , and observe that $v\in D_{\ell}$ for some $\ell\in[m]$ , $\ell\neq j$ . Since $u\in M_{j}$ , $u v$ is not a black edge in $G_{i-1}$ , see Equation (1). However, $u v$ is not a red edge in $G_{i-1}$ either, by condition 3 in the definition of a basic decomposition in Section 2. This is a contradiction with $u_{0}v_{0}\in E(G)$ .

For b), let us fix $j\in[m]$ and $u\in T_{j}$ that has a black neighbor $v\in D_{\ell}$ for some $\ell\in[m]$ . By Definition 4, $f^{\prime}(v)\neq 0$ and there is a vertex $w\in\beta(v)\cap S$ . Hence, $\beta(u)\subseteq N(w)\subseteq N[S]$ as required. $\hfill\blacktriangleleft$

Algorithm 1 Algorithm for Partial Dominating Set.

Now we show that in each iteration of the loop on lines 10-17 in Algorithm 1, a solution of the currently processed profile $\pi$ and its value are computed. Informally, for each profile $\pi_{j}$ in the decomposition of $\pi$ , we avoid double-counting dominated vertices in $\beta(\hat{M}\cap T_{j})$ by partitioning $\hat{M}\cap T_{j}$ into two subsets, $M_{j}$ and $C_{j}$ : $\beta(M_{j})$ contains vertices dominated “from inside”, i.e., via a red edge considered in one of the previous iterations, and $\beta(C_{j})$ contains those dominated “from outside”, i.e., via a black edge to $D^{\prime}$ .

Lemma 11.

Let $i\in[2,n]$ , $\pi$ be an extended $i$ -profile, $f^{\prime}$ be a function compatible with $\pi$ , and $\nu$ and $S$ be the values computed by Algorithm 1 on line 16 in the iteration processing $f^{\prime}$ . If for each extended $(i-1)$ -profile $\pi^{\prime}$ , $S^{\prime}$ is a solution of $\pi^{\prime}$ of value $\nu^{\prime}$ , where $(S^{\prime},\nu^{\prime})$ is the pair computed in $\sigma_{i-1}(\pi^{\prime})$ , then $S$ is a solution of $\pi$ of value $\nu$ .

Proof.

Let $\pi=(T,D,M,f)$ and let $\{\pi_{j}\colon j\in[m]\}$ be the $f^{\prime}$ -decomposition of $\pi$ found on line 11 in the iteration processing $f^{\prime}$ . For each $j\in[m]$ , let $T_{j},D_{j},M_{j},f_{j},S_{j},\nu_{j}$ , and $C_{j}$ be the values computed on lines 13 and 14. By Lemma 9, $S$ is a solution of $\pi$ . To simplify notation, let $\delta(A):=|N[S]\cap\beta(A)|$ for any $A\subseteq V(G_{i})$ or $A\subseteq V(G_{i-1})$ . Now it suffices to show that $\nu=\delta(M)$ .

Let $\hat{M}$ be defined as in the algorithm, see line 9, and observe that $\delta(M)=\delta(\hat{M})$ . Since $T_{1},\ldots,T_{m}$ are pairwise disjoint, it suffices to show that for each $j\in[m]$ , $\textsf{value}_{j}$ computed on line 15 equals $\delta(\hat{M}\cap T_{j})$ . Let us fix $j\in[m]$ , and observe that $\hat{M}\cap T_{j}=M_{j}\cup C_{j}$ and $M_{j}\cap C_{j}=\emptyset$ , see Equation (1) and line 14. By Lemma 10 a, we have $\nu_{j}=\delta(M_{j})$ because $\nu_{j}$ is the value of $S_{j}$ . By Lemma 10 b, $\beta(u)\subseteq N[S]$ for each $u\in C_{j}$ , which implies $\delta(C_{j})=|\beta(C_{j})|$ . Hence, $\textsf{value}_{j}=\delta(M_{j})+\delta(C_{j})=\delta(\hat{M}\cap T_{j})$ , and $\nu=\delta(M)$ as required. $\hfill\blacktriangleleft$

Now we show that we are able to find an optimal solution for each profile. The idea is to describe an optimal solution with a function $f^{\prime}$ compatible with the considered profile, and then to show that the solution found in the iteration processing $f^{\prime}$ is optimal as well.

Lemma 12.

For each $i\in[n]$ and each extended $i$ -profile $\pi$ , if the final value of $\sigma_{i}(\pi)$ computed by Algorithm 1 is $(S,\nu)$ , then $S$ is an optimal solution of $\pi$ and $\nu$ is the value of $S$ .

Proof.

Let $i\in[n]$ and $\pi=(T,D,M,f)$ be an extended $i$ -profile. We proceed by induction on $i$ . First, suppose that $i=1$ . Since there are no red edges in $G_{1}=G$ and $T$ is connected in $G^{R}$ , we know that $T=\{u\}$ for some $u\in V(G)$ . Notice that $D,M\in\{\emptyset,\{u\}\}$ and $f\in\{\{(u,0)\},\{(u,1)\}\}$ . In particular, $\pi$ has only one solution, namely $D$ , and the value of $D$ is $|D\cap M|$ as required, see line 1. Now suppose that $i>1$ . Let $v\in V(G_{i})$ be the new vertex in $G_{i}$ and let $u_{1},u_{2}\in V(G_{i-1})$ be the two vertices contracted into $v$ . If $v\notin T$ , then $\pi$ is also an $(i-1)$ -profile. By induction hypothesis, $\sigma_{i-1}(\pi)$ is an optimal solution of $\pi$ , which ensures that $\sigma_{i}(\pi)$ is also an optimal solution of $\pi$ , see line 6. Hence, let us assume that $v\in T$ and let $T^{\prime}=(T\setminus v)\cup\{u_{1},u_{2}\}$ . By induction hypothesis and Lemma 11, $\pi$ has a solution since there is a function compatible with $\pi$ .

Let $S^{*}$ be an optimal solution of $\pi$ , let $\nu^{*}$ be the value of $S^{*}$ , and let $f^{\prime}\colon T^{\prime}\rightarrow[0,k]$ be defined as $f^{\prime}(u)=|S^{*}\cap\beta(u)|$ . Observe that by Definition 5, $f^{\prime}(u)=f(u)$ for each $u\in T\setminus\{v\}$ , and $f(v)=|S^{*}\cap\beta(v)|=|S^{*}\cap\beta(u_{1})|+|S^{*}\cap\beta(u_{2})|=f^{% \prime}(u_{1})+f^{\prime}(u_{2})$ , i.e., $f^{\prime}$ is compatible with $\pi$ . Let us consider the iteration of the loop on lines 5-17 processing $\pi$ and the iteration of the loop on lines 10-17 processing $f^{\prime}$ . Let $\{\pi_{j}\colon j\in[m]\}$ be the $f^{\prime}$ -decomposition of $\pi$ found on line 11. For each $j\in[m]$ , let $T_{j},D_{j},M_{j},f_{j},S_{j},\nu_{j}$ , and $C_{j}$ be as in the algorithm. Let $\nu$ and $S$ be the values computed on line 16. By Lemma 11, $S$ is a solution of $\pi$ with value $\nu$ . Similarly to the proof of Lemma 11, we denote $\delta(A)=|N[S]\cap\beta(A)|$ and $\delta^{*}(A)=|N[S^{*}]\cap\beta(A)|$ for any $A\subseteq V(G_{i})$ or $A\subseteq V(G_{i-1})$ .

Suppose for contradiction that $\nu<\nu^{*}$ , i.e., $\delta(M)<\delta^{*}(M)$ , see Definition 5. Let $\hat{M}$ be as in the algorithm, see line 9, and observe that $\delta(M)=\delta(\hat{M})$ and $\delta^{*}(M)=\delta^{*}(\hat{M})$ . Hence, there must be $j\in[m]$ such that $\delta(\hat{M}\cap T_{j})<\delta^{*}(\hat{M}\cap T_{j})$ ; let us fix such a $j$ . By Lemma 10 b, if $u\in C_{j}$ , then $\beta(u)\subseteq N[S]\cap N[S^{*}]$ . Hence, $\delta(C_{j})=|\beta(C_{j})|=\delta^{*}(C_{j})$ , which implies $\delta(M_{j})<\delta^{*}(M_{j})$ because $\hat{M}\cap T_{j}=C_{j}\cup M_{j}$ and $M_{j}\cap C_{j}=\emptyset$ . Let $S_{j}^{*}=S^{*}\cap\beta(T_{j})$ and observe that $S_{j}^{*}$ is a solution of $\pi_{j}$ . By Lemma 10 a, $\delta(M_{j})$ is the value of $S_{j}$ and $\delta^{*}(M_{j})$ is the value of $S_{j}^{*}$ . By induction hypothesis, $S_{j}$ is an optimal solution of $\pi_{j}$ , which is a contradiction with $\delta(M_{j})<\delta^{*}(M_{j})$ . Hence, $\nu=\nu^{*}$ , and $S$ is an optimal solution of $\pi$ , too.

After the iteration of the loop on lines 10-17 processing $f^{\prime}$ , $\sigma_{i}(\pi)=(S,\nu)$ because $S$ is an optimal solution of $\pi$ . Observe that the second component of $\sigma_{i}(\pi)$ cannot change in any of the following iterations because $\nu$ is always the value of some solution of $\pi$ by Lemma 11. Hence, after all functions compatible with $\pi$ have been processed, $\sigma_{i}(\pi)$ is indeed an optimal solution of $\pi$ and its value, as desired. $\hfill\blacktriangleleft$

Using Lemma 12, it is easy to show the correctness of Algorithm 1.

Theorem 13.

Algorithm 1 decides the Partial Dominating Set problem in time $2^{\mathcal{O}(kd\log(kd))}\cdot n$ .

Proof.

Let $\iota=(G,C=(G=G_{1},\ldots,G_{n}),k,t)$ be the input instance, where $C$ is contraction sequence of width $d$ . Let $V(G_{n})=\{u\}$ and let $\pi=(\{u\},\{u\},\{u\},\{(u,k)\})$ . Note that $\pi$ is an extended $n$ -profile unless $n<k$ , in which case, $\iota$ is trivially a NO instance. By Lemma 12, $S$ is an optimal solution of $\pi$ with value $\nu$ , where $(S,\nu)$ is the pair computed by Algorithm 1 on line 18. By Definition 5, $|S|=k$ and $\nu=|N[S]\cap\beta(\{u\})|=|N[S]|$ . Hence, $\iota$ is a YES instance if and only if $\nu\geq t$ , as required.

Now need to argue that Algorithm 1 achieves the desired running time. As an optimization, we maintain a single function $\sigma$ (instead of $\sigma_{i}$ for each $i\in[n]$ ). Since there are $\mathcal{O}(n)$ extended $1$ -profiles, line 1 can be performed in time $\mathcal{O}(n)$ . There are $n-1$ iterations of the outermost loop (i.e., the loop on lines 2-17); let us consider the iteration processing $i\in[2,n]$ and let $v$ be the new vertex in $G_{i}$ . Let $\pi=(T,D,M,f)$ be an extended $i$ -profile. Since $\sigma(\pi)$ has already been computed if $v\notin T$ , it suffices to consider only profiles such that $v\in T$ ; these profiles can be enumerated in time $2^{\mathcal{O}(kd\log(kd))}$ by Lemma 6. There are at most $k+1$ functions $f^{\prime}$ compatible with $\pi$ and for each of them, we can find an $f^{\prime}$ -decomposition of size at most $m\leq d+2$ in time $\mathcal{O}(k^{2}d^{2})$ by Lemma 8. Hence, the running time of one iteration of the outermost loop is $2^{\mathcal{O}(kd\log(kd))}$ , which implies that the total running time is $2^{\mathcal{O}(kd\log(kd))}\cdot n$ as required. $\hfill\blacktriangleleft$

3.4 Partial Vertex Cover

In this section, we prove the following theorem.

Theorem 14.

There is an algorithm that, given a graph $G$ , a contraction sequence $(G_{1}=G,\ldots,G_{n})$ of width $d$ , and two integers $k$ and $t$ , decides the Partial Vertex Cover problem in time $2^{\mathcal{O}(kd\log(kd))}\cdot n$ .

Because of similarity to the proof of Theorem 13, we only informally discuss the differences. The details can be found in the full version of the paper [3]. One difference mentioned already in Section 3.1 is that it suffices to consider extended $i$ -profiles $\pi=(T,D,M,f)$ such that $M=\emptyset$ .

Recall that the vertex-cover-value of a solution $S\subseteq\beta(T)$ is the number of edges in $G[\beta(T)]$ covered by $S$ , see Definition 5. Hence, if $\mathcal{D}=\{(T_{j},D_{j},\emptyset,f_{j})\colon j\in[m]\}$ is a decomposition of $\pi$ , then the edges in $G[\beta(T_{j})]$ covered by $S$ are covered also by $S\cap\beta(T_{j})$ . This means that when merging solutions of profiles in $\mathcal{D}$ , we must only add the number $\delta_{j\ell}$ of covered edges with one endpoint in $\beta(T_{j})$ and the other in $\beta(T_{\ell})$ for distinct $j,\ell\in[m]$ . Since there cannot be a red edge connecting $D_{j}$ and $T_{\ell}$ by definition of a basic decomposition, we can compute $\delta_{j\ell}$ by inspecting the black edges between $T_{j}$ and $T_{\ell}$ . Observe that a black edge $uv\in B(G_{i-1})$ semi-induces a complete bipartite graph between $\beta(u)$ and $\beta(v)$ in $G$ . Because we have to avoid double-counting, we obtain the following equation:

\delta_{j\ell}=\sum_{u\in T_{j}}\sum_{\begin{subarray}{c}v\in T_{\ell},\\ uv\in B(G_{i-1})\end{subarray}}f_{j}(u)\cdot|\beta(v)|+f_{\ell}(v)\cdot|\beta(% u)|-f_{j}(u)\cdot f_{\ell}(v)

Using this equation, we can compute an optimal solution of $\pi$ . The rest of the proof of Theorem 14 is analogous to the proof of Theorem 13.

4 ( $\exists^{*}\sum\#$ QF) Model Checking

We now turn our attention to the framework mentioned in the introduction. For a background in (counting) logic, we refer the readers to [31]. We consider a generalization of a fragment of the counting logic FO(>0), namely problems expressible by formulas of the form $\exists x_{1}\cdots\exists x_{k}\sum_{\alpha\in I}\#y\,\psi_{\alpha}(x_{1},% \dots,x_{k},y)\geq t$ for some quantifier-free formulas $\psi_{\alpha}$ , $\alpha\in I$ , and $t\in\mathbb{N}$ . Such a formula is true in a graph $G$ if there are vertices $v_{1},\ldots,v_{k}\in V(G)$ such that $\sum_{\alpha\in I}\#y\,\psi_{\alpha}(v_{1},\dots v_{k},y)\geq t$ , where $\#y\,\psi_{\alpha}(v_{1},\dots,v_{k},y)$ is the number of vertices $w\in V(G)$ such that $\psi_{\alpha}(v_{1},\dots,v_{k},w)$ holds in $G$ .

We are interested in giving an FPT algorithm on graph classes of bounded twin-width to solve the model-checking problem for this logic.
( $\exists^{*}\sum\#$ QF)Model Checking using twin-width
Input: A graph $G$ , a contraction sequence for $G$ of width $d$ , a finite set $I$ , a quantifier-free formula $\psi_{\alpha}$ with $k+1$ free variables for each $\alpha\in I$ , and $t\in\mathbb{N}$
Question: Are there vertices $v_{1},\dots,v_{k}\in V(G)$ such that $G\models\sum_{\alpha\in I}\#y\,\psi_{\alpha}(v_{1}\dots v_{k},y)\geq t$ ?
Parameter: $k+d$ ¹¹1Note that we assume that each formula $\psi_{\alpha}$ is normalized, i.e., there is no shorter formula equivalent to $\psi_{\alpha}$ . Without this assumption, the parameter would have to be $k+d+\sum_{\alpha\in I}|\psi_{\alpha}|$ .

It is not hard to express Partial Dominating Set in this logic, see Section 1. Let us illustrate how Partial Vertex Cover can be expressed.

Example 15.

We can express Partial Vertex Cover with $I=[k]$ and the following formulas. For $\alpha\in I$ , let $\psi_{\alpha}(x_{1},\dots,x_{k},y)\equiv E(x_{\alpha},y)\land\bigwedge_{\gamma% \in[\alpha-1]}y\neq x_{\gamma}$ . Intuitively, $\psi_{\alpha}$ counts the number of edges covered by $x_{\alpha}$ . To avoid double-counting, the potential edge $x_{\alpha}x_{\gamma}$ is counted by $\psi_{\alpha}$ only if $\alpha<\gamma$ (and otherwise it is counted by $\psi_{\gamma}$ ).

4.1 Virtual Profiles

In Section 3, we used extended profiles, which were obtained by “extending” basic profiles introduced in Section 2. In our model checking algorithm, we will again “extend” the basic profiles in a certain way. This time, however, these profiles will need to contain even more information than the extended profiles. Intuitively, the reason behind this change is that the $k$ existential variables in the considered formula are not interchangeable, whereas the $k$ vertices in a partial dominating set (or vertex cover) are. Hence, a part of a virtual profile is a function $f$ , which describes where each existential variable should be realized.

However, we need to be able to capture the fact that some variables may be realized in a part of $G$ not covered by the profile; this is done by adding a bounded number of “virtual” vertices and edges ( $\mathcal{V}$ and $\mathcal{E}$ ). Note that the virtual vertices are “new objects”; e.g., $V(G)\cap\mathcal{V}=\emptyset$ . Moreover, we need to remember which atomic formulas ( $x_{a}=x_{b}$ , $E(x_{a},x_{b})$ , and negations of these two) are satisfied by which existential variables: this information is encoded in a vertex-labeled graph $H$ . Note that if a virtual profile has a solution, then $H$ must be compatible with $f$ and $\mathcal{E}$ .

Definition 16.

Let $i\in[n]$ and let $(T,D)$ be a basic $i$ -profile. A virtual $i$ -profile is a tuple $\pi=(T,D,\mathcal{V},\mathcal{E},f,H)$ , where:

$\blacksquare$

$\mathcal{V}$ is the set of at most $k$ virtual vertices.
$\blacksquare$

$\mathcal{E}\subseteq\{uv\colon u\in\mathcal{V}\cup T,v\in\mathcal{V}\}$ is the set of virtual edges.
$\blacksquare$

$f\colon[k]\rightarrow D\cup\mathcal{V}$ is a surjective function such that $|f^{-1}(u)|\leq|\beta(u)|$ for each $u\in D$ .
$\blacksquare$

$H$ is a graph with at most $k$ vertices with vertex set labeled as $\{h_{1},\ldots,h_{k}\}$ .

The expanded graph of $\pi$ , denoted $G_{\pi}$ , is the graph with vertex set $\beta(T)\cup\mathcal{V}$ and edge set $E(G[\beta(T)])\cup\{uv\in\mathcal{E}\colon u,v\in\mathcal{V}\}\cup\{u_{0}v% \colon uv\in\mathcal{E},v\in\mathcal{V},u\in T,u_{0}\in\beta(u)\}$ . A tuple $\mathbf{s}=(s_{1},\ldots,s_{k})\in V(G_{\pi})^{k}$ is a solution of $\pi$ if:

$\blacksquare$

for each $a\in[k]$ , $s_{a}=f(a)$ if $f(a)\in\mathcal{V}$ , and $s_{a}\in\beta(f(a))$ if $f(a)\in D$ ;
$\blacksquare$

the function $s_{a}\mapsto h_{a}$ is an isomorphism from $G_{\pi}[\{s_{1},\ldots,s_{k}\}]$ to $H$ .

The value of $\mathbf{s}$ is defined as $\sum_{\alpha\in I}|\{u\in\beta(T)\colon G_{\pi}\models\psi_{\alpha}(s_{1},% \ldots,s_{k},u)\}|$ . A solution $\mathbf{s}$ of $\pi$ is optimal if no other solution of $\pi$ has higher value than $\mathbf{s}$ .

The expanded graph $G_{\pi}$ illustrates the concept of virtual profiles: the subgraph of $G$ induced by the bags from $T$ is expanded with the virtual vertices. The virtual vertices are uniformly connected to vertices from each bag in $T$ as dictated by $\mathcal{E}$ . A solution $\mathbf{s}$ of $\pi$ must then adhere to $\pi$ in the following way: each $s_{a}$ in $\mathbf{s}$ has to be the correct virtual vertex or a vertex from the correct bag as dictated by $f$ ; and $\mathbf{s}$ has to induce the desired subgraph $H$ in the expanded graph $G_{\pi}$ . When an optimal solution has been computed for each virtual profile, we can find the answer to the problem by inspecting an $n$ -profile $\pi^{*}$ such that $\mathcal{V}$ and $\mathcal{E}$ are empty, $T=V(G_{n})$ and $\beta(T)=V(G)$ , and $f$ is the unique function from $[k]$ to $V(G_{n})$ . In contrast to the case of Partial Dominating Set, the profile $\pi^{*}$ is not unique; one has to try all possible choices of $H$ .

Now we show that the number of virtual profiles is bounded.

Lemma 17.

If $i\in[n]$ and $v\in V(G_{i})$ , then the number of virtual $i$ -profiles $(T,D,\mathcal{V},\mathcal{E},f,H)$ such that $v\in T$ is in $2^{\mathcal{O}(k^{2}d\log(d))}$ . Moreover, such profiles can be enumerated in time $2^{\mathcal{O}(k^{2}d\log(d))}$ .

4.2 Virtual Decompositions

To achieve our goal of finding optimal solutions of virtual profiles, we continue similarly as in the previous section about Partial Dominating Set and Partial Vertex Cover. We will again need a notion of a decomposition for our virtual profiles. However, we must ensure that the profiles in the decomposition are “compatible” with each other with respect to the virtual vertices. Informally, the virtual edges must correspond to the black edges between the profiles in $G_{i-1}$ .

Let $i\in[2,n]$ , let $v\in V(G_{i})$ be the new vertex in $G_{i}$ , let $u_{1},u_{2}\in V(G_{i-1})$ be the two vertices contracted into $v$ , let $\pi_{0}=(T,D)$ be a basic $i$ -profile such that $v\in T$ , let $\pi=(T,D,\mathcal{V},\mathcal{E},f,H)$ be a virtual $i$ -profile, let $T^{\prime}=T\setminus\{v\}\cup\{u_{1},u_{2}\}$ , and let $\mathcal{E}^{\prime}=\{uw\in\mathcal{E}\colon u,w\in T^{\prime}\cup\mathcal{V}% \}\cup\{u_{1}w,u_{2}w\colon vw\in\mathcal{E}\}$ . We say that a function $f^{\prime}\colon[k]\rightarrow T^{\prime}\cup\mathcal{V}$ is compatible with $\pi$ if $f^{\prime}(a)\in\{u_{1},u_{2}\}$ when $f(a)=v$ , and $f^{\prime}(a)=f(a)$ otherwise.

Figure 3: Leftmost: A graph

H

with vertex set

\{h_{1},\ldots,h_{6}\}

. The circle representing

h_{a}

contains the digit

a

. Middle left: A virtual

i

-profile

\pi=(T,D,\mathcal{V},\mathcal{E},f,H)

for

k=6

. Virtual vertices are represented by violet stars and virtual edges by violet lines.

T

is the set of all non-virtual vertices. For each

a\in[6]

, the vertex

f(a)

contains the digit

a

.

D

is the set

f(\{2,5\})

. Middle: The circles, and black and red edges represent

G_{i-1}[T^{\prime}]

, the violet star is the vertex in

\mathcal{V}

, and the violet lines represent

\mathcal{E}^{\prime}

. The digits represent the function

f^{\prime}

. The set

T^{\prime}

has two red-connected components:

T_{1}

colored in green and

T_{2}

colored in orange. Middle right: The profile

(T_{1},D_{1},\mathcal{V}_{1},\mathcal{E}_{1},f_{1},H)

. Note that the facts that

f_{1}(5)=f_{1}(6)

and

f_{1}(3)f_{1}(4)\notin\mathcal{E}_{1}

follow from

H

; they cannot be deduced from

T

or

T^{\prime}

. Rightmost: The profile

(T_{2},D_{2},\mathcal{V}_{2},\mathcal{E}_{2},f_{2},H)

.

If a function $f^{\prime}$ is compatible with $\pi$ , then a set $\{\pi_{j}=(T_{j},D_{j},\mathcal{V}_{j},\mathcal{E}_{j},f_{j},H)\colon j\in[m]\}$ of virtual $(i-1)$ -profiles is an $f^{\prime}$ -decomposition if $D^{\prime}=\operatorname{range}(f^{\prime})\cap T^{\prime}$ , $\{(T_{1},D_{1}),\ldots,(T_{m},D_{m})\}$ is a $D^{\prime}$ -decomposition of $\pi_{0}$ , and for each $j\in[m]$ :

$\blacksquare$

$\mathcal{V}_{j}=\mathcal{V}\cup\{h_{a}\colon f^{\prime}(a)\in D^{\prime}% \setminus D_{j}\}$ .
$\blacksquare$

$f_{j}(a)=f^{\prime}(a)$ if $f^{\prime}(a)\in D_{j}\cup\mathcal{V}$ , and $f_{j}(a)=h_{a}$ if $f^{\prime}(a)\in D^{\prime}\setminus D_{j}$ .
$\blacksquare$
$\mathcal{E}_{j}$ is the union of the following sets.
- –
  
  $\{uw\in\mathcal{E}^{\prime}\colon u,w\in\mathcal{V}\cup T_{j}\}$ .
- –
  
  $\{uh_{a}\colon u\in\mathcal{V}\cup T_{j},f^{\prime}(a)=w\in D^{\prime}% \setminus D_{j},uw\in\mathcal{E}^{\prime}\cup B(G_{i-1})\}$ .
- –
  
  $\{h_{a}h_{b}\in E(H)\colon f^{\prime}(a),f^{\prime}(b)\in D^{\prime}\setminus D% _{j}\}$ .

The intuition behind this construction of $\pi_{j}$ is that for each vertex in $D^{\prime}\setminus D_{j}$ , which are the vertices with some variable assigned to them, we add a new virtual vertex to $\mathcal{V}_{j}$ , and $\mathcal{E}_{j}$ contains $\mathcal{E}^{\prime}$ “restricted” to $T_{j}$ (the first term), edges between a new virtual vertex $h_{a}$ and an “old” virtual vertex $u\in\mathcal{V}$ or a vertex $u\in T_{j}$ (the second term), and edges between two new virtual vertices (the third term). Note that we used the vertices of $H$ to label the new virtual vertices, which means that two new virtual vertices $h_{a}$ and $h_{b}$ may be equal even when $a\neq b$ ; this ensures the possibility of an isomorphism from a solution of $\pi_{j}$ to $H$ . See Figure 3 for an illustration of a virtual decomposition.

Again, we prove that a small $f^{\prime}$ -decomposition exists for each $f^{\prime}$ compatible with $\pi$ .

Lemma 18.

If $i\in[2,n]$ , $V(G_{i})\setminus V(G_{i-1})=\{v\}$ , $V(G_{i-1})\setminus V(G_{i})=\{u_{1},u_{2}\}$ , $\pi=(T,D,\mathcal{V},\mathcal{E},f,H)$ is a virtual $i$ -profile such that $v\in T$ , $T^{\prime}=T\setminus\{v\}\cup\{u_{1},u_{2}\}$ , and $f^{\prime}\colon[k]\rightarrow T^{\prime}\cup\mathcal{V}$ is a function compatible with $\pi$ , then there is an $f^{\prime}$ -decomposition $\mathcal{D}$ of $\pi$ with cardinality at most $d+2$ . Moreover, $\mathcal{D}$ can be found in time $\mathcal{O}(k^{2}d^{2})$ .

4.3 Combining Solutions

In Section 3, we obtained a solution for an extended $i$ -profile $\pi$ by simply taking the union of solutions of profiles in a decomposition of $\pi$ . In this section, combining solutions is more complicated because each solution is a tuple, which may contain some virtual vertices.

Definition 19.

Let $i\in[n]$ , let $\pi_{1}=(T_{1},D_{1},\mathcal{V}_{1},\mathcal{E}_{1},f_{1},H)$ and $\pi_{2}=(T_{2},D_{2},\mathcal{V}_{2},\mathcal{E}_{2},f_{2},H)$ be two virtual $i$ -profiles, and let $\mathbf{s}^{1}=(s_{1}^{1},\ldots,s_{k}^{1})$ and $\mathbf{s}_{2}=(s_{1}^{2},\ldots,s_{k}^{2})$ be solutions of $\pi_{1}$ and $\pi_{2}$ , respectively. By $\mathbf{s}^{1}\oplus\mathbf{s}^{2}$ , we denote the tuple $(s_{1},\ldots,s_{k})\in(\beta(D_{1})\cup V(G_{\pi_{2}}))^{k}$ such that for each $a\in[k]$ , $s_{a}=s_{a}^{1}$ if $f_{1}(a)\in D_{1}$ , and $s_{a}=s_{a}^{2}$ otherwise.

Note that in general, the operation $\oplus$ is neither associative nor commutative. However, we will use it only to combine solutions of profiles in a decomposition (and when restricted to such inputs, $\oplus$ is both associative and commutative, which will be implicit in the proof of the following lemma). Let $\mathbf{s}=\bigoplus_{j\in[m]}\mathbf{s}^{j}=\mathbf{s}^{1}\oplus(\mathbf{s}^{% 2}\oplus\ldots)$ . Formally, $\mathbf{s}=\mathbf{s}^{1}$ if $m=1$ and $\mathbf{s}=\mathbf{s}^{1}\oplus\bigoplus_{j\in[2,m]}\mathbf{s}^{j}$ otherwise.

Lemma 20.

If $i\in[2,n]$ , $\pi$ is a virtual $i$ -profile, $\{\pi_{j}\colon j\in[m]\}$ is an $f^{\prime}$ -decomposition of $\pi$ , and $\mathbf{s}^{j}$ is a solution of $\pi_{j}$ for each $j\in[m]$ , then $\mathbf{s}=\bigoplus_{j\in[m]}\mathbf{s}^{j}$ is a solution of $\pi$ . Moreover, if $\nu_{j}$ is the value of $\mathbf{s}_{j}$ , then the value of $\mathbf{s}$ is $\sum_{j\in[m]}\nu_{j}$ .

Proof.

Let $\pi=(T,D,\mathcal{V},\mathcal{E},f,H)$ and $\mathbf{s}=(s_{1},\ldots,s_{k})$ . For each $j\in[m]$ , let $\pi_{j}=(T_{j},D_{j},\mathcal{V}_{j},\mathcal{E}_{j},f_{j},H)$ and let $\mathbf{s}_{j}=(s_{1}^{j},\ldots,s_{k}^{j})$ . For each $j\in[m]$ , let $G^{j}:=G_{\pi_{j}}$ .

First, let $a\in[k]$ be such that $f(a)\in\mathcal{V}$ . Observe that for each $j\in[m]$ , $f(a)=f^{\prime}(a)=f_{j}(a)=s_{a}^{j}$ , which means that $s_{a}=f(a)$ as desired (because $s_{a}=s_{a}^{j}$ for some $j\in[m]$ by Definition 19). Second, let $a\in[k]$ be such that $f(a)\in D$ and let $j\in[m]$ be the unique index such that $u:=f^{\prime}(a)=f_{j}(a)\in D_{j}$ . By Definition 19, $s_{a}=s_{a}^{j}\in\beta(u)$ because $f_{\ell}(a)\notin D_{\ell}$ for each $\ell\in[m]\setminus\{j\}$ . By definition of $f^{\prime}$ , if $u\in V(G_{i-1})\cap V(G_{i})$ , then $f(a)=u$ . Otherwise, $f(a)$ is the new vertex in $G_{i}$ , and $s_{a}\in\beta(u)\subseteq\beta(f(a))$ . In both cases, $s_{a}\in\beta(f(a))$ as desired.

Now we need to show that the function $s_{a}\mapsto h_{a}$ is an isomorphism from $G_{\pi}[\{s_{1},\ldots,s_{k}\}]$ to $H$ . Let us fix $a,b\in[k]$ . Since $\mathbf{s}_{j}$ is a solution of $\pi_{j}$ for each $j\in[m]$ , it suffices to show that $s_{a}s_{b}\in E(G_{\pi})\leftrightarrow s_{a}^{j}s_{b}^{j}\in E(G^{j})$ and $s_{a}=s_{b}\leftrightarrow s_{a}^{j}=s_{b}^{j}$ for some $j\in[m]$ . First, if $s_{a},s_{b}\in\mathcal{V}$ or $s_{a},s_{b}\in\beta(T_{j})$ for some $j\in[m]$ , then $s_{a}=s_{a}^{j}$ and $s_{b}=s_{b}^{j}$ , and $s_{a}s_{b}\in E(G_{\pi})\leftrightarrow s_{a}s_{b}\in E(G)\cup\mathcal{E}% \leftrightarrow s_{a}^{j}s_{b}^{j}\in E(G^{j})$ as required. Moreover, we clearly have $s_{a}=s_{b}\leftrightarrow s_{a}^{j}=s_{b}^{j}$ ; note that in all other cases, $s_{a}\neq s_{b}$ and $s_{a}^{j}\neq s_{b}^{j}$ . Second, if $s_{a}\in\mathcal{V}$ and $s_{b}\in\beta(u)\subseteq\beta(u^{\prime})$ for some $u\in T_{j}$ , $j\in[m]$ , and $u^{\prime}\in T$ , then $s_{a}s_{b}\in E(G_{\pi})\leftrightarrow s_{a}u^{\prime}\in\mathcal{E}% \leftrightarrow s_{a}u\in\mathcal{E}_{j}\leftrightarrow s_{a}s_{b}\in E(G^{j})$ . Finally, assume that $j,\ell\in[m]$ , $j\neq\ell$ , and $s_{a}\in\beta(T_{j}),s_{b}\in\beta(T_{\ell})$ . Let $u=f^{\prime}(a)=f_{j}(a)$ and $v=f^{\prime}(b)=f_{\ell}(b)$ . By definition of a solution, we have $s_{a}\in\beta(u)$ and $s_{b}\in\beta(v)$ . Recall that $D^{\prime}=\bigcup_{p\in[m]}D_{p}$ , that $u,v\in D^{\prime}$ , and that $\{(T_{p},D_{p})\colon p\in[m]\}$ is a $D^{\prime}$ -decomposition of the basic $i$ -profile $(T,D)$ . Hence, by condition 3 in the definition of a $D^{\prime}$ -decomposition, see Section 2, $uv\notin R(G_{i-1})$ . Now $s_{a}s_{b}\in E(G_{\pi})\leftrightarrow s_{a}s_{b}\in E(G)\leftrightarrow uv% \in B(G_{i-1})\leftrightarrow uh_{b}\in\mathcal{E}_{j}\leftrightarrow s_{a}^{j% }s_{b}^{j}\in E(G^{j})$ as required. Note that after the third equivalence, we could have used $h_{a}v\in\mathcal{E}_{\ell}$ and continued analogously. We have shown that $\mathbf{s}$ is a solution of $\pi$ .

What remains to be shown is that the value of $\mathbf{s}$ equals $\sum_{j\in[m]}\nu_{j}$ . Since $\beta(T)=\beta(T^{\prime})$ , where $T^{\prime}=\bigcup_{j\in[m]}T_{j}$ , it suffices to show that for each $j\in[m]$ , $u\in\beta(T_{j})$ and $\alpha\in I$ , $G_{\pi}\models\psi_{\alpha}(s_{1},\ldots,s_{k},u)$ if and only if $G^{j}\models\psi_{\alpha}(s_{1}^{j},\ldots,s_{k}^{j},u)$ . Using the isomorphisms to $H$ , we obtain that $s_{a}\mapsto s_{a}^{j}$ is an isomorphism from $G_{\pi}[\{s_{1},\ldots,s_{k}\}]$ to $G^{j}[\{s_{1}^{j},\ldots,s_{k}^{j}\}]$ . Hence, it suffices to show that for each $a\in[k]$ , (1) $u=s_{a}\leftrightarrow u=s_{a}^{j}$ , and (2) $us_{a}\in E(G_{\pi})\leftrightarrow us_{a}^{j}\in E(G^{j})$ . If $s_{a}=s_{a}^{j}$ , then (1) clearly holds, and if $s_{a}\neq s_{a}^{j}$ , then $s_{a}\notin\beta(T_{j})$ and $s_{a}^{j}\in\mathcal{V}_{j}$ , which implies $u\notin\{s_{a},s_{a}^{j}\}$ . Now let us focus on (2). Let $u_{j}\in T_{j}$ and $u^{\prime}\in T$ be such that $u\in\beta(u_{j})\subseteq\beta(u^{\prime})$ . If $s_{a}=s_{a}^{j}\in\beta(T_{j})$ , then $us_{a}\in E(G_{\pi})\leftrightarrow us_{a}\in E(G)\leftrightarrow us_{a}\in E(% G^{j})$ as required. If $s_{a}=s_{a}^{j}\notin\beta(T_{j})$ , then $s_{a}\in\mathcal{V}$ , and $us_{a}\in E(G_{\pi})\leftrightarrow u^{\prime}s_{a}\in\mathcal{E}% \leftrightarrow u_{j}s_{a}\in\mathcal{E}_{j}\leftrightarrow us_{a}\in E(G^{j})$ as required. Finally, suppose $s_{a}\neq s_{a}^{j}$ , i.e., $s_{a}\in\beta(T)\setminus\beta(T_{j})$ , and $s_{a}^{j}=h_{a}\in\mathcal{V}_{j}$ . Let $w=f^{\prime}(a)$ and observe that, by definition of a solution, $s_{a}\in\beta(w)$ . Since $w\in D^{\prime}$ , we have $u_{j}w\notin R(G_{i-1})$ , see condition 3 in the definition of a $D^{\prime}$ -decomposition. Hence, we have $us_{a}\in E(G_{\pi})\leftrightarrow us_{a}\in E(G)\leftrightarrow u_{j}w\in B(% G_{i-1})\leftrightarrow u_{j}h_{a}\in\mathcal{E}_{j}\leftrightarrow uh_{a}=us_% {a}^{j}\in E(G^{j})$ as required. We have proven that the value of $\mathbf{s}$ is $\sum_{j\in[m]}\nu_{j}$ as desired. $\hfill\blacktriangleleft$

4.4 Model Checking Algorithm

Algorithm 2 Algorithm for (

\exists^{*}\sum\#

QF)Model Checking.

Now we can start proving the correctness of Algorithm 2. First, let us show that the algorithm computes an optimal solution for each virtual profile $\pi$ (or it discovers that $\pi$ has no solution).

Lemma 21.

For each $i\in[n]$ and each virtual $i$ -profile $\pi$ , if the final value of $\sigma_{i}(\pi)$ computed by Algorithm 2 is $(\mathbf{s},\nu)$ , then $\mathbf{s}$ is an optimal solution of $\pi$ and $\nu$ is the value of $\mathbf{s}$ . On the other hand, if $\sigma_{i}(\pi)=(\textsf{null},0)$ , then $\pi$ has no solution.

Using Lemma 21, it is easy to show the correctness of Algorithm 2.

Theorem 22.

Algorithm 2 decides the ( $\exists^{*}\sum\#$ QF)Model Checking using twin-width problem in time $2^{\mathcal{O}(k^{2}d\log(d))}n$ .

Proof.

Suppose that the algorithm is given a graph $G$ , a contraction sequence $(G_{1}=G,\ldots,G_{n})$ of width $d$ , and a formula $\phi\equiv\exists x_{1}\cdots\exists x_{k}\sum_{\alpha\in I}\#y\,\psi_{\alpha}% (x_{1},\ldots,x_{k},y)\geq t$ . Let us say that a graph $H$ with vertex set labeled as $\{h_{1},\ldots,h_{k}\}$ is a template graph. Let us consider an iteration of the loop on lines 19-21 processing a template graph $H$ , let $\pi_{H}=(\{u\},\{u\},\emptyset,\emptyset,f,H)$ be as on line 20, and let $(\mathbf{s}_{H},\nu_{H})$ be the tuple computed on line 20. By Lemma 21, $\mathbf{s}_{H}$ is an optimal solution of $\pi_{H}$ with value $\nu_{H}$ , or $(\mathbf{s}_{H},\nu_{H})=(\textsf{null},0)$ if $\pi_{H}$ has no solution. Since there are no virtual vertices in $\pi_{H}$ , if $\pi_{H}$ has a solution, then $\mathbf{s}_{H}$ is a tuple in $V(G)^{k}$ , and $\nu_{H}=\sum_{\alpha\in I}|\{u\in V(G)\colon G\models\psi_{\alpha}(\mathbf{s},% u)\}|$ .

Let $(\mathbf{s},\nu)$ the final value of $(\textsf{solution, count)}$ computed by Algorithm 2. If $\mathbf{s}=\textsf{null}$ and $\nu=0$ , then $\pi_{H}$ has no solution for any template graph $H$ , which means that for any tuple $\mathbf{s}^{\prime}\in V(G)^{k}$ , $\sum_{\alpha\in I}|\{u\in V(G)\colon G\models\psi_{\alpha}(\mathbf{s}^{\prime}% ,u)\}|=0$ , and $(G,\phi)$ is a YES-instance if and only if $t=0$ . Otherwise, $\mathbf{s}\in V(G)^{k}$ , $\nu=\sum_{\alpha\in I}|\{u\in V(G)\colon G\models\psi_{\alpha}(\mathbf{s},u)\}|$ , and $\nu=\max\{\nu_{H}\colon H$ is a template graph $\}$ . Clearly, for each tuple $(s_{1},\ldots,s_{k})\in V(G)^{k}$ , there is a template graph $H$ such that $s_{a}\mapsto h_{a}$ is an isomorphism from $G[\{s_{1},\ldots,s_{k}\}]$ to $H$ , which means that $(G,\phi)$ is a YES-instance if and only if $\nu\geq t$ . This shows the correctness of Algorithm 2.

Now we need to argue that Algorithm 2 achieves the desired running time. As in the proof of Theorem 13, we maintain a single function $\sigma$ (instead of $\sigma_{i}$ for each $i\in[n]$ ). First, observe that by Lemma 17, there are at most $2^{\mathcal{O}(k^{2}d\log(d))}\cdot n$ virtual $1$ -profiles. Hence, executing the for loop on lines 1-4 takes time at most $2^{\mathcal{O}(k^{2}d\log(d))}\cdot n$ . Second, observe that there are $n-1$ iterations of the loop on lines 5-17; let us consider the iteration processing $i\in[2,n]$ and let $v$ be the new vertex in $G_{i}$ . Let $\pi=(T,D,\mathcal{V},\mathcal{E},f,H)$ be a virtual $i$ -profile. Since $\sigma(\pi)$ has already been computed if $v\notin T$ , it suffices to consider only profiles such that $v\in T$ ; these profiles can be enumerated in time $2^{\mathcal{O}(k^{2}d\log(d))}$ by Lemma 17. There are at most $2^{k}$ functions $f^{\prime}$ compatible with $\pi$ and for each of them, we can find an $f^{\prime}$ -decomposition of size at most $m\leq d+2$ in time $\mathcal{O}(k^{2}d^{2})$ by Lemma 18. Hence, the running time of one iteration of the loop is $2^{\mathcal{O}(kd\log(kd))}$ . Finally, since there are $2^{\mathcal{O}(k^{2})}$ choices of $H$ , executing the loop on lines 19-21 takes time $2^{\mathcal{O}(k^{2})}$ . In total, the running time is $2^{\mathcal{O}(k^{2}d\log(d))}\cdot n$ as required. $\hfill\blacktriangleleft$

5 Conclusion

We have demonstrated that several optimization problems requiring counting can be efficiently solved on graphs with small twin-width. This encompasses not only well-known problems such as Partial Vertex Cover and Partial Dominating Set, but also all problems expressible by a restricted fragment of first-order counting logic. It would be desirable to extend this result by providing a more comprehensive fragment that accommodates additional problems. For bounded expansion, we can utilize formulas of the form $\exists x_{1}\cdots\exists x_{k}\#y\,\phi(x_{1},\ldots,x_{k})$ , where $\phi$ is an arbitrary first-order formula rather than a quantifier-free one, and even slightly more complex formulas [18, 34]. Can we achieve the same for graphs of bounded twin-width? Moreover, we can handle even more complicated formulas with nested counting quantifiers approximately [18]. Once again, does the same or a similar result hold true for bounded twin-width? It should be noted that the best result for nowhere-dense classes is basically the same as our result for twin-width [17].

References

[1] Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. Algorithmica, 33(4):461–493, 2002. doi:10.1007/S00453-001-0116-5.
[2] Hagit Attiya and Jennifer L. Welch. Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley series on parallel and distributed computing. Wiley, 2004.
[3] Jakub Balabán, Daniel Mock, and Peter Rossmanith. Solving partial dominating set and related problems using twin-width. CoRR, abs/2504.18218, 2025. doi:10.48550/arXiv.2504.18218.
[4] R. Balasubramanian, Michael R. Fellows, and Venkatesh Raman. An improved fixed-parameter algorithm for vertex cover. Inf. Process. Lett., 65(3):163–168, 1998. doi:10.1016/S0020-0190(97)00213-5.
[5] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set, min dominating set, and coloring. SIAM J. Comput., 53(5):1602–1640, 2024. doi:10.1137/21M142188X.
[6] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 601–612. IEEE, 2020. doi:10.1109/FOCS46700.2020.00062.
[7] L. Sunil Chandran and Fabrizio Grandoni. Refined memorization for vertex cover. Inf. Process. Lett., 93(3):123–131, 2005. doi:10.1016/J.IPL.2004.10.003.
[8] Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. J. Algorithms, 41(2):280–301, 2001. doi:10.1006/JAGM.2001.1186.
[9] Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736–3756, 2010. doi:10.1016/J.TCS.2010.06.026.
[10] Jianer Chen, Lihua Liu, and Weijia Jia. Improvement on vertex cover for low-degree graphs. Networks, 35(4):253–259, 2000. doi:10.1002/1097-0037(200007)35:4\%3C253::AID-NET3\%3E3.0.CO;2-K.
[11] Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 10-12 July 2007, Wroclaw, Poland, Proceedings, pages 270–279. IEEE Computer Society, 2007. doi:10.1109/LICS.2007.31.
[12] Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In Ravi Kannan and K. Narayan Kumar, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India, volume 4 of LIPIcs, pages 157–168. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2009. doi:10.4230/LIPIcs.FSTTCS.2009.2315.
[13] Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866–893, 2005. doi:10.1145/1101821.1101823.
[14] Rodney G. Downey and Michael R. Fellows. Fixed parameter tractability and completeness III: some structural aspects of the W hierarchy. In Klaus Ambos-Spies, Steven Homer, and Uwe Schöning, editors, Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992, pages 191–225. Cambridge University Press, 1992.
[15] Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. doi:10.1007/978-1-4612-0515-9.
[16] Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, and Szymon Torunczyk. First-order model checking on monadically stable graph classes. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 21–30. IEEE, 2024. doi:10.1109/FOCS61266.2024.00012.
[17] Jan Dreier, Daniel Mock, and Peter Rossmanith. Evaluating restricted first-order counting properties on nowhere dense classes and beyond. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 43:1–43:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ESA.2023.43.
[18] Jan Dreier and Peter Rossmanith. Approximate evaluation of first-order counting queries. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1720–1739. SIAM, 2021. doi:10.1137/1.9781611976465.104.
[19] John A. Ellis, Hongbing Fan, and Michael R. Fellows. The dominating set problem is fixed parameter tractable for graphs of bounded genus. J. Algorithms, 52(2):152–168, 2004. doi:10.1016/J.JALGOR.2004.02.001.
[20] Jörg Flum and Martin Grohe. Fixed-parameter tractability, definability, and model-checking. SIAM J. Comput., 31(1):113–145, 2001. doi:10.1137/S0097539799360768.
[21] Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Tomohiro Koana. FPT approximation and subexponential algorithms for covering few or many edges. Inf. Process. Lett., 185:106471, 2024. doi:10.1016/J.IPL.2024.106471.
[22] Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM, 48(6):1184–1206, 2001. doi:10.1145/504794.504798.
[23] Jakub Gajarský, Michal Pilipczuk, Wojciech Przybyszewski, and Szymon Torunczyk. Twin-width and types. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 123:1–123:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.ICALP.2022.123.
[24] Petr A. Golovach and Yngve Villanger. Parameterized complexity for domination problems on degenerate graphs. In Hajo Broersma, Thomas Erlebach, Tom Friedetzky, and Daniël Paulusma, editors, Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers, volume 5344 of Lecture Notes in Computer Science, pages 195–205, 2008. doi:10.1007/978-3-540-92248-3_18.
[25] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 89–98. ACM, 2014. doi:10.1145/2591796.2591851.
[26] Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of vertex cover variants. Theory Comput. Syst., 41:501–520, October 2007. doi:10.1007/s00224-007-1309-3.
[27] Mrinmoy Hota, Madhumangal Pal, and Tapan Kumar Pal. An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs. Comput. Optim. Appl., 18(1):49–62, 2001. doi:10.1023/A:1008791627588.
[28] Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh. Further exploiting c-closure for FPT algorithms and kernels for domination problems. SIAM J. Discret. Math., 37(4):2626–2669, 2023. doi:10.1137/22M1491721.
[29] Joachim Kneis, Daniel Mölle, and Peter Rossmanith. Partial vs. complete domination: $t$ -dominating set. In Jan van Leeuwen, Giuseppe F. Italiano, Wiebe van der Hoek, Christoph Meinel, Harald Sack, and Frantisek Plasil, editors, SOFSEM 2007: Theory and Practice of Computer Science, 33rd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings, volume 4362 of Lecture Notes in Computer Science, pages 367–376. Springer, 2007. doi:10.1007/978-3-540-69507-3_31.
[30] Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting $c$-closure in kernelization algorithms for graph problems. SIAM J. Discret. Math., 36(4):2798–2821, 2022. doi:10.1137/21M1449476.
[31] Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–12. IEEE Computer Society, 2017. doi:10.1109/LICS.2017.8005133.
[32] Vahan Mkrtchyan and Garik Petrosyan. On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs. J. Graph Algorithms Appl., 26(1):91–110, 2022. doi:10.7155/JGAA.00584.
[33] Vahan Mkrtchyan, Garik Petrosyan, K. Subramani, and Piotr Wojciechowski. On the partial vertex cover problem in bipartite graphs - a parameterized perspective. Theory Comput. Syst., 68(1):122–143, 2024. doi:10.1007/S00224-023-10152-W.
[34] Daniel Mock and Peter Rossmanith. Solving a family of multivariate optimization and decision problems on classes of bounded expansion. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2024, June 12-14, 2024, Helsinki, Finland, volume 294 of LIPIcs, pages 35:1–35:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SWAT.2024.35.
[35] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-27875-4.
[36] Rolf Niedermeier and Peter Rossmanith. Upper bounds for vertex cover further improved. In Christoph Meinel and Sophie Tison, editors, STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings, volume 1563 of Lecture Notes in Computer Science, pages 561–570. Springer, 1999. doi:10.1007/3-540-49116-3_53.
[37] Rolf Niedermeier and Peter Rossmanith. On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms, 47(2):63–77, 2003. doi:10.1016/S0196-6774(03)00005-1.
[38] Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 694–705. Springer, 2009. doi:10.1007/978-3-642-04128-0_62.
[39] Detlef Seese. Linear time computable problems and first-order descriptions. Math. Struct. Comput. Sci., 6(6):505–526, 1996. doi:10.1017/s0960129500070079.
[40] Ulrike Stege, Iris van Rooij, Alexander Hertel, and Philipp Hertel. An o(pn + 1.151 ${}^{\mbox{p}}$ )-algorithm for p-profit cover and its practical implications for vertex cover. In Prosenjit Bose and Pat Morin, editors, Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings, volume 2518 of Lecture Notes in Computer Science, pages 249–261. Springer, 2002. doi:10.1007/3-540-36136-7_23.

[bib.bib1] [1] Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs. Algorithmica, 33(4):461–493, 2002. doi:10.1007/S00453-001-0116-5.

[bib.bib2] [2] Hagit Attiya and Jennifer L. Welch. Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley series on parallel and distributed computing. Wiley, 2004.

[bib.bib3] [3] Jakub Balabán, Daniel Mock, and Peter Rossmanith. Solving partial dominating set and related problems using twin-width. CoRR, abs/2504.18218, 2025. doi:10.48550/arXiv.2504.18218.

[bib.bib4] [4] R. Balasubramanian, Michael R. Fellows, and Venkatesh Raman. An improved fixed-parameter algorithm for vertex cover. Inf. Process. Lett., 65(3):163–168, 1998. doi:10.1016/S0020-0190(97)00213-5.

[bib.bib5] [5] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: max independent set, min dominating set, and coloring. SIAM J. Comput., 53(5):1602–1640, 2024. doi:10.1137/21M142188X.

[bib.bib6] [6] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 601–612. IEEE, 2020. doi:10.1109/FOCS46700.2020.00062.

[bib.bib7] [7] L. Sunil Chandran and Fabrizio Grandoni. Refined memorization for vertex cover. Inf. Process. Lett., 93(3):123–131, 2005. doi:10.1016/J.IPL.2004.10.003.

[bib.bib8] [8] Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. J. Algorithms, 41(2):280–301, 2001. doi:10.1006/JAGM.2001.1186.

[bib.bib9] [9] Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736–3756, 2010. doi:10.1016/J.TCS.2010.06.026.

[bib.bib10] [10] Jianer Chen, Lihua Liu, and Weijia Jia. Improvement on vertex cover for low-degree graphs. Networks, 35(4):253–259, 2000. doi:10.1002/1097-0037(200007)35:4\%3C253::AID-NET3\%3E3.0.CO;2-K.

[bib.bib11] [11] Anuj Dawar, Martin Grohe, and Stephan Kreutzer. Locally excluding a minor. In 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 10-12 July 2007, Wroclaw, Poland, Proceedings, pages 270–279. IEEE Computer Society, 2007. doi:10.1109/LICS.2007.31.

[bib.bib12] [12] Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In Ravi Kannan and K. Narayan Kumar, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India, volume 4 of LIPIcs, pages 157–168. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2009. doi:10.4230/LIPIcs.FSTTCS.2009.2315.

[bib.bib13] [13] Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866–893, 2005. doi:10.1145/1101821.1101823.

[bib.bib14] [14] Rodney G. Downey and Michael R. Fellows. Fixed parameter tractability and completeness III: some structural aspects of the W hierarchy. In Klaus Ambos-Spies, Steven Homer, and Uwe Schöning, editors, Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992, pages 191–225. Cambridge University Press, 1992.

[bib.bib15] [15] Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. doi:10.1007/978-1-4612-0515-9.

[bib.bib16] [16] Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, and Szymon Torunczyk. First-order model checking on monadically stable graph classes. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 21–30. IEEE, 2024. doi:10.1109/FOCS61266.2024.00012.

[bib.bib17] [17] Jan Dreier, Daniel Mock, and Peter Rossmanith. Evaluating restricted first-order counting properties on nowhere dense classes and beyond. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands, volume 274 of LIPIcs, pages 43:1–43:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ESA.2023.43.

[bib.bib18] [18] Jan Dreier and Peter Rossmanith. Approximate evaluation of first-order counting queries. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1720–1739. SIAM, 2021. doi:10.1137/1.9781611976465.104.

[bib.bib19] [19] John A. Ellis, Hongbing Fan, and Michael R. Fellows. The dominating set problem is fixed parameter tractable for graphs of bounded genus. J. Algorithms, 52(2):152–168, 2004. doi:10.1016/J.JALGOR.2004.02.001.

[bib.bib20] [20] Jörg Flum and Martin Grohe. Fixed-parameter tractability, definability, and model-checking. SIAM J. Comput., 31(1):113–145, 2001. doi:10.1137/S0097539799360768.

[bib.bib21] [21] Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Tomohiro Koana. FPT approximation and subexponential algorithms for covering few or many edges. Inf. Process. Lett., 185:106471, 2024. doi:10.1016/J.IPL.2024.106471.

[bib.bib22] [22] Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM, 48(6):1184–1206, 2001. doi:10.1145/504794.504798.

[bib.bib23] [23] Jakub Gajarský, Michal Pilipczuk, Wojciech Przybyszewski, and Szymon Torunczyk. Twin-width and types. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 123:1–123:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.ICALP.2022.123.

[bib.bib24] [24] Petr A. Golovach and Yngve Villanger. Parameterized complexity for domination problems on degenerate graphs. In Hajo Broersma, Thomas Erlebach, Tom Friedetzky, and Daniël Paulusma, editors, Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers, volume 5344 of Lecture Notes in Computer Science, pages 195–205, 2008. doi:10.1007/978-3-540-92248-3_18.

[bib.bib25] [25] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 89–98. ACM, 2014. doi:10.1145/2591796.2591851.

[bib.bib26] [26] Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of vertex cover variants. Theory Comput. Syst., 41:501–520, October 2007. doi:10.1007/s00224-007-1309-3.

[bib.bib27] [27] Mrinmoy Hota, Madhumangal Pal, and Tapan Kumar Pal. An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs. Comput. Optim. Appl., 18(1):49–62, 2001. doi:10.1023/A:1008791627588.

[bib.bib28] [28] Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh. Further exploiting c-closure for FPT algorithms and kernels for domination problems. SIAM J. Discret. Math., 37(4):2626–2669, 2023. doi:10.1137/22M1491721.

[bib.bib29] [29] Joachim Kneis, Daniel Mölle, and Peter Rossmanith. Partial vs. complete domination: $t$ -dominating set. In Jan van Leeuwen, Giuseppe F. Italiano, Wiebe van der Hoek, Christoph Meinel, Harald Sack, and Frantisek Plasil, editors, SOFSEM 2007: Theory and Practice of Computer Science, 33rd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings, volume 4362 of Lecture Notes in Computer Science, pages 367–376. Springer, 2007. doi:10.1007/978-3-540-69507-3_31.

[bib.bib30] [30] Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting $c$-closure in kernelization algorithms for graph problems. SIAM J. Discret. Math., 36(4):2798–2821, 2022. doi:10.1137/21M1449476.

[bib.bib31] [31] Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–12. IEEE Computer Society, 2017. doi:10.1109/LICS.2017.8005133.

[bib.bib32] [32] Vahan Mkrtchyan and Garik Petrosyan. On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs. J. Graph Algorithms Appl., 26(1):91–110, 2022. doi:10.7155/JGAA.00584.

[bib.bib33] [33] Vahan Mkrtchyan, Garik Petrosyan, K. Subramani, and Piotr Wojciechowski. On the partial vertex cover problem in bipartite graphs - a parameterized perspective. Theory Comput. Syst., 68(1):122–143, 2024. doi:10.1007/S00224-023-10152-W.

[bib.bib34] [34] Daniel Mock and Peter Rossmanith. Solving a family of multivariate optimization and decision problems on classes of bounded expansion. In Hans L. Bodlaender, editor, 19th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2024, June 12-14, 2024, Helsinki, Finland, volume 294 of LIPIcs, pages 35:1–35:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.SWAT.2024.35.

[bib.bib35] [35] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-27875-4.

[bib.bib36] [36] Rolf Niedermeier and Peter Rossmanith. Upper bounds for vertex cover further improved. In Christoph Meinel and Sophie Tison, editors, STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings, volume 1563 of Lecture Notes in Computer Science, pages 561–570. Springer, 1999. doi:10.1007/3-540-49116-3_53.

[bib.bib37] [37] Rolf Niedermeier and Peter Rossmanith. On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms, 47(2):63–77, 2003. doi:10.1016/S0196-6774(03)00005-1.

[bib.bib38] [38] Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Solving dominating set in larger classes of graphs: FPT algorithms and polynomial kernels. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 694–705. Springer, 2009. doi:10.1007/978-3-642-04128-0_62.

[bib.bib39] [39] Detlef Seese. Linear time computable problems and first-order descriptions. Math. Struct. Comput. Sci., 6(6):505–526, 1996. doi:10.1017/s0960129500070079.

[bib.bib40] [40] Ulrike Stege, Iris van Rooij, Alexander Hertel, and Philipp Hertel. An o(pn + 1.151 ${}^{\mbox{p}}$ )-algorithm for p-profit cover and its practical implications for vertex cover. In Prosenjit Bose and Pat Morin, editors, Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings, volume 2518 of Lecture Notes in Computer Science, pages 249–261. Springer, 2002. doi:10.1007/3-540-36136-7_23.

Solving Partial Dominating Set and Related Problems Using Twin-Width

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our contribution.

2 Preliminaries

Twin-width.

Basic profiles.

Definition 1.

Lemma 2.

Proof.

Lemma 3.

3 Partial Dominating Set and Vertex Cover

3.1 Extended Profiles

Definition 4.

Definition 5.

Lemma 6.

3.2 Extended Decompositions

▶ Remark 7.

Lemma 8.

Lemma 9.

3.3 Partial Dominating Set

Lemma 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

Proof.

Theorem 13.

Proof.

3.4 Partial Vertex Cover

Theorem 14.

4 (∃∗∑#QF) Model Checking

Example 15.

4.1 Virtual Profiles

Definition 16.

Lemma 17.

4.2 Virtual Decompositions

Lemma 18.

4.3 Combining Solutions

Definition 19.

Lemma 20.

Proof.

4.4 Model Checking Algorithm

Lemma 21.

Theorem 22.

Proof.

5 Conclusion

References

$\blacktriangleright$ Remark 7.

4 ( $\exists^{*}\sum\#$ QF) Model Checking