Metric Dimension and Geodetic Set Parameterized by Vertex Cover

We mention here results concerning structural parameterizations of Metric Dimension and Geodetic Set, and refer the reader to the full version of [20] for a more comprehensive overview of applications and related work regarding these two problems.

As previously mentioned, Metric Dimension is $𝖶$[2]-hard parameterized by the solution size $k$, even in subcubic bipartite graphs [28]. Several other parameterizations have been studied for this problem, on which we elaborate next (see also [21, Figure 1]). It was proven that there is an $\mathrm{𝖷𝖯}$ algorithm parameterized by the feedback edge set number [18], and $\mathrm{𝖥𝖯𝖳}$ algorithms parameterized by the max leaf number [17], the modular-width and the treelength plus the maximum degree [2], the treedepth and the clique-width plus the diameter [23], and the distance to cluster (co-cluster, respectively) [21]. Recently, an $\mathrm{𝖥𝖯𝖳}$ algorithm parameterized by the treewidth in chordal graphs was given in [5]. On the negative side, Metric Dimension is $𝖶$[1]-hard parameterized by the pathwidth even on graphs of constant degree [4], para-$\mathrm{𝖭𝖯}$-hard parameterized by the pathwidth [33], and $𝖶$[1]-hard parameterized by the combined parameter feedback vertex set number plus pathwidth [21].

The parameterized complexity of Geodetic Set was first addressed in [31], in which it was observed that the reduction from [15] implies that the problem is $𝖶$[2]-hard parameterized by the solution size (even for chordal bipartite graphs). This motivated the authors of [31] to investigate structural parameterizations of Geodetic Set. They proved the problem to be $𝖶$[1]-hard for the combined parameters solution size, feedback vertex set number, and pathwidth, and $\mathrm{𝖥𝖯𝖳}$ for the parameters treedepth, modular-width (more generally, clique-width plus diameter), and feedback edge set number [31]. The problem was also shown to be $\mathrm{𝖥𝖯𝖳}$ on chordal graphs when parameterized by the treewidth [6].

We use standard graph-theoretic notation and refer the reader to [14] for any undefined notation. For an undirected graph $G$, the sets $V(G)$ and $E(G)$ denote its set of vertices and edges, respectively. Two vertices $u,v\in V(G)$ are adjacent or neighbors if $(u,v)\in E(G)$. The open neighborhood of a vertex $u\in V(G)$, denoted by $N(u):=N_G(u)$, is the set of vertices that are neighbors of $u$. The closed neighborhood of a vertex $u\in V(G)$ is denoted by $N[u]:=N_G[u]:=N_G(u)\cup \{u\}$. For any $X\subseteq V(G)$ and $u\in V(G)$, $N_X(u)=N_G(u)\cap X$. Any two vertices $u,v\in V(G)$ are true twins if $N[u]=N[v]$, and are false twins if $N(u)=N(v)$. For a subset $S$ of $V(G)$, we say that the vertices in $S$ are true (false, respectively) twins if, for any $u,v\in S$, $u$ and $v$ are true (false, respectively) twins. The distance between two vertices $u,v\in V(G)$ in $G$, denoted by $d(u,v):=d_G(u,v)$, is the length of a $(u,v)$-shortest path in $G$. For a subset $S$ of $V(G)$, we define $N[S]={\bigcup }_{v\in S}N[v]$ and $N(S)=N[S]\setminus S$. For a graph $G$, a set $X\subseteq V(G)$ is said to be a vertex cover if $V(G)\setminus X$ is an independent set. We denote by $\mathrm{𝚟𝚌}(G)$ the size of a minimum vertex cover in $G$. When $G$ is clear from the context, we simply say $\mathrm{𝚟𝚌}$. A vertex is simplicial if its neighborhood forms a clique. Observe that any simplicial vertex $v$ does not belong to any shortest path between any pair $x,y$ of vertices (both distinct from $v$). Hence, the following holds.

A subset of vertices $S^{\prime }\subseteq V(G)$ resolves a pair of vertices $u,v\in V(G)$ if there exists a vertex $w\in S^{\prime }$ such that $d(w,u)\ne d(w,v)$. A vertex $u\in V(G)$ is distinguished by a subset of vertices $S^{\prime }\subseteq V(G)$ if, for any $v\in V(G)\setminus \{u\}$, there exists a vertex $w\in S^{\prime }$ such that $d(w,u)\ne d(w,v)$.

An instance of a parameterized problem $\mathrm{\Pi }$ comprises an input $I$, which is an input of the classical instance of the problem, and an integer $\mathrm{\ell }$, which is called the parameter. A problem $\mathrm{\Pi }$ is said to be fixed-parameter tractable or in $\mathrm{𝖥𝖯𝖳}$ if given an instance $(I,\mathrm{\ell })$ of $\mathrm{\Pi }$, we can decide whether or not $(I,\mathrm{\ell })$ is a Yes-instance of $\mathrm{\Pi }$ in $f(\mathrm{\ell })\cdot {|I|}^{𝒪(1)}$ time, for some computable function $f$ whose value depends only on $\mathrm{\ell }$.

A kernelization algorithm for $\mathrm{\Pi }$ is a polynomial-time algorithm that takes as input an instance $(I,\mathrm{\ell })$ of $\mathrm{\Pi }$ and returns an equivalent instance $(I^{\prime },{\mathrm{\ell }}^{\prime })$ of $\mathrm{\Pi }$, where $|I^{\prime }|,{\mathrm{\ell }}^{\prime }\le f(\mathrm{\ell })$, where $f$ is a function that depends only on $\mathrm{\ell }$. If such an algorithm exists for $\mathrm{\Pi }$, we say that $\mathrm{\Pi }$ admits a kernel of size $f(\mathrm{\ell })$. If $f$ is a polynomial or exponential function of $\mathrm{\ell }$, we say that $\mathrm{\Pi }$ admits a polynomial or exponential kernel, respectively. If $\mathrm{\Pi }$ is a graph problem, then $I$ contains a graph, say $G$, and $I^{\prime }$ contains a graph, say $G^{\prime }$. In this case, we say that $\mathrm{\Pi }$ admits a kernel with $f(\mathrm{\ell })$ vertices if the number of vertices of $G^{\prime }$ is at most $f(\mathrm{\ell })$.

It is typical to describe a kernelization algorithm as a series of reduction rules. A reduction rule is a polynomial-time algorithm that takes as an input an instance of a problem and outputs another (usually reduced) instance. A reduction rule said to be applicable on an instance if the output instance is different from the input instance. A reduction rule is safe if the input instance is a Yes-instance if and only if the output instance is a Yes-instance.

The Exponential Time Hypothesis (ETH) roughly states that $n$-variable 3-SAT cannot be solved in $2^{o(n)}$ time. For more on parameterized complexity and related terminologies, we refer the reader to the recent book by Cygan et al. [12].

Our lower bound proofs consist of reductions from the 3-Partitioned-3-SAT problem. This version of 3-SAT was introduced in [32] and is defined as follows.

3-Partitioned-3-SAT Input: A formula $\psi$ in $3$-CNF form, together with a partition of the set of its variables into three disjoint sets $X^{\alpha }$, $X^{\beta }$, $X^{\gamma }$, with $|X^{\alpha }|=|X^{\beta }|=|X^{\gamma }|=N$, and such that no clause contains more than one variable from each of $X^{\alpha },X^{\beta }$, and $X^{\gamma }$. Question: Determine whether $\psi$ is satisfiable.

We start with the results for Metric Dimension, which are then followed by those for Geodetic Set. For each, we first present the algorithms and then the reductions. Since space requirements prohibit us from presenting our reductions in detail, we give an outline that discusses the main technical ideas behind our reductions for getting the lower-bound results for both Metric Dimension and Geodetic Set. For the complete formal proofs, we refer the reader to the full version of this paper [19].

Since $u,v,x$ are false twins, $N(u)=N(v)=N(x)$. This implies that, for any vertex $w\in V(G)\setminus \{u,v,x\}$, $d(w,v)=d(w,u)=d(w,x)$. Hence, any resolving set that excludes at least two vertices in $\{u,v,x\}$ cannot resolve all three pairs $\{u,v\}$, $\{u,x\}$, and $\{v,x\}$. As the vertices in $\{u,v,x\}$ are distance-wise indistinguishable from the remaining vertices, we can assume, without loss of generality, that any resolving set contains both $u$ and $x$. Hence, any pair of vertices in $V(G)\setminus \{u,x\}$ that is resolved by $x$ is also resolved by $u$. In other words, if $S$ is a resolving set of $G$, then $S\setminus \{x\}$ is a resolving set of $G-\{x\}$. This implies the correctness of the forward direction. The correctness of the reverse direction trivially follows from the fact that we can add $x$ into a resolving set of $G-\{x\}$ to obtain a resolving set of $G$. $◀$

Given a graph $G$, let $X\subseteq V(G)$ be a minimum vertex cover of $G$. If such a vertex cover is not given, then we can find a $2$-factor approximate vertex cover in polynomial time. Let $I:=V(G)\setminus X$. By the definition of a vertex cover, the vertices of $I$ are pairwise non-adjacent.

The kernelization algorithm exhaustively applies Reduction Rule 1. Now, consider an instance on which 1 is not applicable. If the budget is negative, then the algorithm returns a trivial No-instance of constant size. Otherwise, for any $Y\subseteq X$, there are at most two vertices $u,v\in I$ such that $N(u)=N(v)=Y$. This implies that the number of vertices in the reduced instance is at most $|X|+2\cdot 2^{|X|}=2^{\mathrm{𝚟𝚌}+1}+\mathrm{𝚟𝚌}$. $◀$

Next, we present an $\mathrm{𝖷𝖯}$-algorithm parameterized by the vertex cover number. This algorithm, along with the kernelization algorithm above, imply¹¹1Note that the application of 1 does not increase the vertex cover number. that Metric Dimension admits an algorithm running in $2^{𝒪({\mathrm{𝚟𝚌}}^2)}\cdot n^{𝒪(1)}$ time.

The algorithm starts by computing a minimum vertex cover $X$ of $G$ in $2^{𝒪(\mathrm{𝚟𝚌})}\cdot n^{𝒪(1)}$ time using an $\mathrm{𝖥𝖯𝖳}$ algorithm for the Vertex Cover problem, for example the one in [11] or [27]. Let $I:=V(G)\setminus X$. Then, in polynomial time, it computes a largest subset $F$ of $I$ such that, for every vertex $u$ in $F$, $I\setminus F$ contains a false twin of $u$. By the arguments in the previous proof, if there are false twins in $I$, say $u,v$, then any resolving set contains at least one of them. Hence, it is safe to assume that any resolving set contains $F$. If , then the algorithm returns No. Otherwise, it enumerates every subset of vertices of size at most $|X|$ in $X\cup (I\setminus F)$. If there exists a subset $A\subseteq X\cup (I\setminus F)$ such that $A\cup F$ is a resolving set of $G$ of size at most $k$, then it returns $A\cup F$. Otherwise, it returns No.

In order to prove that the algorithm is correct, we prove that $X\cup F$ is a resolving set of $G$. It is easy to see that, for a pair of distinct vertices $u,v$, if $u\in X\cup F$ and $v\in V(G)$, then the pair is resolved by $u$. It remains to argue that every pair of distinct vertices in $(I\setminus F)\times (I\setminus F)$ is resolved by $X\cup F$. Note that, for any two vertices $u,v\in I\setminus F$, $N(u)\ne N(v)$ as otherwise $u$ can be moved to $F$, contradicting the maximality of $F$. Hence, there is a vertex in $X$ that is adjacent to $u$, but not adjacent to $v$, resolving the pair $⟨u,v⟩$. This implies the correctness of the algorithm. The running time of the algorithm easily follows from its description. $◀$

Toward a contradiction, assume that such a kernelization algorithm exists. Consider the following algorithm for 3-Partitioned-$3$-SAT. Given a 3-Partitioned-$3$-SAT formula on $N$ variables, it uses Theorem 6 to obtain an equivalent instance of $(G,k)$ such that $\mathrm{𝚟𝚌}(G)+k=𝒪(\sqrt{N})$ and $|V(G)|=2^{𝒪(\sqrt{N})}$. Then, it uses the assumed kernelization algorithm to construct an equivalent instance $(H,k^{\prime })$ such that $H$ has $2^{o(\mathrm{𝚟𝚌}(G)+k)}$ vertices and $k^{\prime }\le k$. Finally, it uses a brute-force algorithm, running in ${|V(H)|}^{𝒪(k^{\prime })}$ time, to determine whether the reduced instance, or equivalently the input instance of 3-Partitioned-3-SAT, is a Yes-instance. The correctness of the algorithm follows from the correctness of the respective algorithms and our assumption. The total running time of the algorithm is $2^{𝒪(\sqrt{N})}+{(|V(G)|+k)}^{𝒪(1)}+{|V(H)|}^{𝒪(k^{\prime })}=2^{𝒪(\sqrt{N})}+{(2^{𝒪(\sqrt{N})})}^{𝒪(1)}+{(2^{o(\sqrt{N})})}^{𝒪(\sqrt{N})}=2^{o(N)}$. But this contradicts the ETH. $◀$

The reduction, presented in Section 4.2, uses tools introduced in the next subsection.