Hitting Geodesic Intervals in Structurally Restricted Graphs

To illustrate connections to other problems, we first observe that some known facts imply (in)tractability of some cases of HGI. (Some of them will be useful later.)

1. 1.

   WHGI parameterized by $|T|$ is fixed-parameter tractable.

2. 2.

   WHGI on trees is polynomial-time solvable.

3. 3.

   If Vertex Cover is $\mathrm{NP}$-complete on a graph class $𝒞$, then so is HGI.

4. 4.

   HGI on complete graphs is $\mathrm{NP}$-complete.

5. 5.

   HGI on $r\times r$ grids is $\mathrm{NP}$-complete.

The first one is an easy observation that this is a special case of Hitting Set parameterized by the number of subsets to be hit, which is fixed-parameter tractable (see [8, Theorem 6.1]). The second follows from the fact that the following more general problem is polynomial-time solvable (see, e.g., the discussion by Jansen [19]): given a set of subtrees of a tree, find a minimum vertex set that intersects all subtrees in the set.

The third and fourth observations come from the equivalence of an instance $⟨(V,E),k⟩$ of Vertex Cover and the instances $⟨(V,E),\left(\genfrac{}{}{0pt}{}{V}{2}\right),k⟩$ and $⟨(V,\left(\genfrac{}{}{0pt}{}{V}{2}\right)),E,k⟩$ of HGI, where $\left(\genfrac{}{}{0pt}{}{V}{2}\right)=\{\{u,v\}\mid u,v\in V,u\ne v\}$. The equivalence holds since the only way to interrupts an adjacent pair is to pick one of them.

The fifth fact can be shown by observing an interesting connection to a geometric problem. Piercing Rectangles asks, given axis-parallel rectangles $R_1,\mathrm{\dots },R_r$ in the plane and an integer $k$, whether there is a set of $k$ points that intersects all rectangles $R_i$ (see [1]). It is known that even if all coordinates are integers, each rectangle is a $2\times 2$ square, and all rectangles are placed in a region of $cr\times cr$ for some constant $c$, this problem is NP-complete [16].¹¹1In [16], the problem is described as a point-set covering problem by $2\times 2$ squares, which is equivalent to the one described here because in each problem one object hits or covers another object if the $L_{\mathrm{\infty }}$ distance between their centers is at most $1$. Such an instance of Piercing Rectangles can be transformed to an equivalent instance $⟨G,T,k⟩$ of HGI by setting $G$ to the $cr\times cr$ grid and adding the pair of two opposite corners of each rectangle $R_i$ to $T$. Observe that a geodesic interval $I_G[u,v]$ for $u$ and $v$ is the set of vertices in the axis-parallel rectangle having $u$ and $v$ at opposite corners.

Their main results can be summarized as follows.

1. 1.

   HGI is W[2]-complete parameterized by the solution size $k$.

2. 2.

   HGI is fixed-parameter tractable parameterized by $k$ plus cluster vertex deletion number.

3. 3.

   HGI is fixed-parameter tractable parameterized by $k$ plus neighborhood diversity.

4. 4.

   WHGI is fixed-parameter tractable parameterized by feedback edge set number.

5. 5.

   WHGI is fixed-parameter tractable parameterized by vertex cover number.

Their first result complements the fixed-parameter tractability with respect to $|T|$ as in nontrivial instances. Note that this result implies the W[2]-completeness of WHGI parameterized by $k$ even on complete graphs (consider the reduction from HGI that replaces each nonedge with a huge-weight edge). In their second and third results, having $k$ in the parameter is necessary because of the NP-completeness of HGI on complete graphs. Their fourth result generalizes polynomial-time solvability on trees. Note that they did not explicitly mention the weighted case for feedback edge set number, but their algorithm works without any modifications for the weighted case as well.

Since vertex cover number is an upper bound on the solution size $k$, the parameterization solely by vertex cover number is equivalent to the one by $k$ plus vertex cover number. Thus, most of the known positive results (except for the one parameterized by feedback edge set number) have “plus $k$” in their parameters.

As open questions, Aravind and Saxena [2] asked for the complexity of HGI parameterized by treewidth, pathwidth, feedback vertex set number, and distance to path forest.

Our first results demonstrate that HGI is NP-complete even if the target graph classes are highly restricted, and thus answer the open questions of Aravind and Saxena [2] in a negative way. More precisely, we show that the problem is NP-complete on the following classes:

1. 1.

   graphs of vertex-deletion distance $1$ to the class of disjoint unions of $5$-vertex paths;

2. 2.

   graphs of vertex-deletion distance $1$ to the class of paths;

3. 3.

   graphs of vertex-deletion distance $1$ to the class of disjoint unions of triangles;

4. 4.

   graphs of bandwidth $4$ and maximum degree $5$.

Our main technical contribution here is the first one, which already implies that HGI is paraNP-complete for most of the structural parameters studied in the literature (see Figure 1 (left)) as the graphs there have distance to path forest $1$ and vertex integrity $6$. The second one is an easy corollary of the first. The third one, which improves the vertex integrity bound to $4$, is based on the same idea as the first. The fourth one can be obtained from the third by a minor modification.

To cope with the rather hopeless situation discussed above, we consider the setting where the solution size $k$ is also part of the parameter. In this setting, we present the following positive results.

1. 1.

   HGI is fixed-parameter tractable parameterized by $k$ plus modular-width.

2. 2.

   WHGI is fixed-parameter tractable parameterized by $k$ plus vertex integrity.

3. 3.

   WHGI is fixed-parameter tractable parameterized by the minimum vertex multiway-cut size of the set of terminal vertices $V(T)$.

The first result for $k$ plus modular-width generalizes the one for $k$ plus neighborhood diversity [2]. The second and third results are achieved by a single algorithm that solves WHGI when a small separator of a special kind is given as part of the input. After presenting the algorithm, we show that the two cases can be handled by this algorithm without the assumption that the separator is given as part of the input (see Section 4.2.2 for details). Observe that the second result generalizes the one parameterized solely by vertex cover number [2] since vertex cover number is an upper bound of both $k$ and vertex integrity. The third result generalizes the one parameterized by $|T|$, which can be seen as an example of the conceptual framework of Jansen and Swennenhuis [20] for parameterizing terminal-involved problems with a parameter structurally smaller than the number of terminals. Although the third result does not explicitly have $k$ in the parameter, we can see that its parameter is an upper bound of $k$.

Figure 1 (right) shows the complexity of HGI parameterized by solution size $k$ plus a structural parameter. As we can see, it is not well understood yet, and many cases remain unsettled.

As mentioned above, there are many unsettled cases in the “plus $k$” setting. Actually, we do not know any intractability result like “HGI is W-hard parameterized by $k$ plus X” for any structural graph parameter X.

As intermediate steps toward this direction, we present two intractability results for the following cases, where $k$ is part of the parameter, implicitly or explicitly.

1. 1.

   HGI is W[2]-complete parameterized by the minimum vertex multicut size of the set of terminal pairs $T$.

2. 2.

   HGI is W[2]-complete parameterized by $k$ even if $T=\left(\genfrac{}{}{0pt}{}{Q}{2}\right)$ for some $Q\subseteq V$.

The first one implicitly has $k$ in the parameter since such a cut size is an upper bound of $k$. Also, it is a lower bound of the minimum vertex multiway-cut size of $V(T)$. In this sense, this intractability result tightens the gap between the W[2]-completeness parameterized solely by $k$ [2] and our fixed-parameter tractability result parameterized by the minimum vertex multiway-cut size of $V(T)$.

The second result shows that a natural restriction of HGI is still W[2]-complete parameterized solely by $k$, where we want to hit pairwise geodesic intervals among a given vertex subset $Q\subseteq V$. This result is shown by a modification of the proof of the first result.

Let $⟨G=(V,E),T,k⟩$ be an instance of HGI. Observe that the vertex set of each connected component $C$ of $G$ is a module of $G$, and thus $\mathrm{𝗆𝗐}(C)\le \mathrm{𝗆𝗐}(G)$. Hence, we may assume that $G$ is connected; otherwise we solve each connected component of $G$ independently for all $k^{\prime }\le k$ and combine the answers for them.

Let $M_1,\mathrm{\dots },M_p$ be a partition of $V$ into modules of $G$ with $2\le p\le \mathrm{𝗆𝗐}(G)$. It is known that such a partition can be computed in linear time [24]. Note that, although the definition of modular-width requires a complete recursive structure, our algorithm described below only needs a partition at the very first level.

For each $\{u,v\}\in T$, we take a set $J(u,v)$ and initialize it by $I_G[u,v]$. Now we set $ℐ=\{J(u,v)\mid \{u,v\}\in T\}$. Our goal is to find a hitting set $S$ of $ℐ$ with size at most $k$. To this end, we make two phases of branching that make the rest of the problem almost trivially polynomial-time solvable. Although we do not explicitly state the trivial termination conditions in each step, we stop and reject a branch if it results in or $\mathrm{\varnothing }\in ℐ$.

We first branch on the $2^p$ candidates of the set of modules that $S$ intersects, which we call ${ℳ}_S$. We assume that $S$ is chosen in such a way that $|{ℳ}_S|$ is maximized. According to ${ℳ}_S$, we update $ℐ$ as follows.

• $\mathrm{■}$

  Add each $M_i\in {ℳ}_S$ into $ℐ$.

• $\mathrm{■}$

  For each $\{u,v\}\in T$, if there is $M_i\in {ℳ}_S$ with $M_i\subseteq J(u,v)$, then remove $J(u,v)$ from $ℐ$.

• $\mathrm{■}$

  For each $\{u,v\}\in T$ and $M_i\notin {ℳ}_S$, update $J(u,v)$ as $J(u,v)≔J(u,v)\setminus M_i$.

We now see that, for every $\{u,v\}\in T$, if $u$ and $v$ belong to different modules, say $M_i$ and $M_j$, then $J(u,v)\subseteq \{u,v\}$ after the update above. Observe that $I_G[u,v]=\{u,v\}\cup {\bigcup }_{M\in ℳ}M$ for some $ℳ\subseteq \{M_1,\mathrm{\dots },M_p\}\setminus \{M_i,M_j\}$. Since $J(u,v)\in ℐ$, we have $ℳ\cap {ℳ}_S=\mathrm{\varnothing }$, and thus $J(u,v)\subseteq \{u,v\}$.

Let ${ℐ}^{\prime }$ be the subset of $ℐ$ consisting of the sets $J(u,v)$ such that $\{u,v\}\in E$ or $u$ and $v$ belong to different modules. Observe that every hitting set $S$ of $ℐ$ with size at most $k$ contains a minimal hitting set $S^{\prime }$ of ${ℐ}^{\prime }$ with size at most $k$. We list all possible candidates for $S^{\prime }$ and branch on them. Since each member of ${ℐ}^{\prime }$ has size at most $2$, we can use the algorithm of Damaschke [9] for enumerating all minimal vertex covers of size at most $k$ in $O(|{ℐ}^{\prime }|+k^2{2}^k)$ time. It gives us all (at most $2^k$) minimal hitting sets of ${ℐ}^{\prime }$ with size at most $k$ (or answers that there is no such a set). After we pick one candidate $S^{\prime }$, we decrease $k$ by $|S^{\prime }|$ and update $ℐ$ by removing all elements hit by $S^{\prime }$. In particular, we remove all $J(u,v)\in {ℐ}^{\prime }$ from $ℐ$.

We first show that, at this point, each member of $ℐ$ is a subset of some module $M_i$. This is trivial for the members of ${ℳ}_S$. For $J(u,v)\in ℐ$, we have $\{u,v\}\notin E$ and there is a module $M_i$ such that $u,v\in M_i$. This implies that ${\mathrm{dist}}_G(u,v)=2$ since $M_i$ has an adjacent module by the connectivity of $G$. Thus, $I_G[u,v]$ consists of the modules adjacent to $M_i$ and a subset of $M_i$. Since $J(u,v)\in ℐ$ now, the adjacent modules do not belong to ${ℳ}_S$. This implies that $J(u,v)\subseteq M_i$.

For $i\in [p]$, let ${ℐ}_i$ be the (possibly empty) subset of $ℐ$ consisting of the members that are subsets of $M_i$. Since ${ℐ}_1,\mathrm{\dots },{ℐ}_p$ form a partition of $ℐ$ with disjoint universes, we can handle them separately. That is, if we know a minimum hitting set $S_i$ of ${ℐ}_i$ for each $i\in [p]$, then we can set $S=S^{\prime }\cup {\bigcup }_{i\in [p]}{S}_i$.

We now claim that, under the assumption that ${ℳ}_S$ and $S^{\prime }$ are correct ones, each nonempty ${ℐ}_i$ admits a hitting set of size $1$. Suppose to the contrary that a minimum hitting set $S_i$ of ${ℐ}_i$ has size at least $2$ for some $i\in [p]$. Let $M_j$ be a module adjacent to $M_i$, and let $v_i\in S_i$ and $v_j\in M_j$. Let $S_i^{\prime }=(S_i\setminus \{v_i\})\cup \{v_j\}$ and $R=(S\setminus S_i)\cup S_i^{\prime }$. Observe that $S_i^{\prime }$ hits ${ℐ}_i$: it contains at least one vertex of $M_i$, which hits $M_i$; and $v_j\in M_j$ hits all $J(u,v)\in {ℐ}_i$ since ${\mathrm{dist}}_G(u,v)=2$. This implies that $R$ interrupts all pairs in $T$ as $S$ does. However, this contradicts the assumption on $S$ since $R$ intersects one more module ($M_j$) than $S$. Thus, we can conclude that at least one of ${ℳ}_S$ and $S^{\prime }$ is not correct.

Given the observation above, we can solve the rest of the current branch in polynomial time as follow. If there are at most $k$ indices $i\in [p]$ such that ${ℐ}_i$ is nonempty and each of them admits a hitting set of size $1$, then return yes. Otherwise, we reject the current branch.

We first branch on $2^p$ cases. In each case, we take $O^{\ast }(2^k)$ time to enumerate at most $2^k$ candidates for the next branch. We branch on these candidates and take polynomial time in each of them. In total, the running time is $O^{\ast }(2^{p+k})$. $◀$