Keywords

1 Introduction

Various theoretical and practical motivations have led to generalizations of many classical graph optimization problems to their distance-based variants. Informally, this means that the adjacency property used to defined a feasible solution to the problem is replaced with a relaxed property based on distances in the graph.

For a concrete example, consider the Vertex Cover problem. A vertex cover in a graph G is a set of vertices intersecting all edges. For a non-negative integer k, a distance-k vertex cover in a graph G is a set C of vertices such that every edge has an endpoint which is at distance at most k from a vertex in C. Note that a distance-0 vertex cover is the same thing as a vertex cover. The Distance-\(k\) Vertex Cover problem is the problem of deciding, given a graph G and an integer \(\ell \), whether G contains a distance-k vertex of size at most \(\ell \). Motivated by an application in network monitoring, where links between hosts (edges in the network graph) can be monitored from hosts (vertices) at distance at most k, the problem was first studied in 2008, under the name Beacon Placement Problem, by Sasaki et al. [33]. They showed that the problem is NP-complete for all \(k\ge 2\) and provided a greedy heuristic for the corresponding minimization problem. NP-completeness for \(k = 1\) was established in 2003 by Horton and López-Ortiz [18]. Our terminology, Distance-\(k\) Vertex Cover, follows the work of Busch et al. [8] from 2010, where it was proved that for the class of dually chordal graphs, the problem is NP-complete for \(k = 0\) but solvable in polynomial time for any fixed integer \(k\ge 1\).

The case \(k = 0\) corresponds to the Vertex Cover problem, which is equivalent to the Independent Set problem and has been the subject of great interest in algorithmic graph theory. One of the key questions in this area, investigated for decades, is whether for every positive integer p, the Vertex Cover problem can be solved in polynomial time in the class of graphs not containing a p-vertex path as an induced subgraph. While the solution for \(p = 4\) has been known at least since 1981 [12], the cases of \(p = 5\) and \(p = 6\) were settled only in 2014 and in 2019, respectively, by Lokshantov et al. [24] and Grzesik et al. [17]. The question is currently still open for all \(p\ge 7\), but Gartland and Lokshtanov recently developed a quasi-polynomial time algorithm for every fixed p [16]. Going beyond forbidden induced paths, the following more general question is also open: Is the Vertex Cover problem polynomial-time solvable in the class of H-free graphs whenever every component of H is either a path or a subdivision of the claw? While this restriction on H is necessary for the polynomial-time solvability (unless \(\P = \textsf {NP}\)) [1], it is not known whether it is also sufficient. Also for the cases when H is not a path, only few partial results are known, see, e.g., [2, 5].

Our Focus. We study the Distance-\(k\) Vertex Cover problem for \(k\ge 1\). Contrary to the case \(k = 0\), the distance-based generalizations have received only limited attention in the literature so far. We already mentioned the work of Busch et al. [8] and an application in network monitoring [33]. Canales et al. gave an extremal result regarding minimum distance 2-vertex covers of maximal outerplanar graphs [10]. This result was further generalized to all k by Alvarado et al. [3]. Nonetheless, the complexity of the problem for restricted inputs remains poorly understood. Our main goal is to fill this gap by providing a systematic study of the complexity of the problem. We do this by analyzing the Distance-\(k\) Vertex Cover problem for \(k\ge 1\) in classes of H-free graphs, that is, in classes of graphs defined by a single forbidden induced subgraph H.

Our Results. For integers \(k\ge 1\), \(s\ge 0\), and \(t\ge 1\), we denote by \(P_k+sP_t\) the disjoint union of a k-vertex path and s copies of the t-vertex path. We develop the following computational complexity dichotomies for Distance-\(k\) Vertex Cover in classes of H-free graphs.

  • A dichotomy for \(k = 1\) and arbitrary graph H: the Distance-\(1\) Vertex Cover problem is solvable in polynomial time in the class of H-free graphs if H is an induced subgraph of \(P_4+sP_2\) for some \(s\ge 0\), and NP-complete otherwise.

  • A dichotomy for any \(k \ge 2\) and arbitrary graph H: the Distance-\(k\) Vertex Cover problem is solvable in polynomial time in the class of H-free graphs if H is an induced subgraph of \(P_{2k+2}+sP_k\) for some \(s\ge 0\), and NP-complete otherwise.

In polynomially solvable cases, the degrees of the polynomials expressing the running times of our algorithms depend on k and s. However, this is not the case when H is connected. We obtain the following result.

  • A dichotomy for any \(k \ge 1\) and connected graph H: the Distance-\(k\) Vertex Cover problem is solvable in time \(\mathcal {O}((|V(G)|+|E(G)|)^2)\) in the class of H-free graphs if H is an induced subgraph of \(P_{2k+2}\), and NP-complete otherwise.

To derive the NP-completeness results, we introduce a distance-based generalization of the notion of edge dominating set and establish the NP-completeness of the corresponding decision problems. As a corollary of our approach, we show that for all \(k\ge 1\), polynomial-time solvability of the Distance-\(k\) Vertex Cover problem in the class of strongly chordal graphs established in [8] cannot be generalized to the class of chordal graphs, unless \(\P = \textsf {NP}\). Our polynomial-time algorithms are based on properties of minimum dominating sets in \(P_t\)-free graphs established by Camby and Schaudt [9].

Related Work. Besides vertex cover, distance-based generalizations of several other graph concepts were studied in the literature, including matchings [8, 35], dominating sets [11, 14, 19, 27], independent sets [4, 11, 14, 15, 21, 26, 30, 31], and cliques [25, 29].

To the best of our knowledge, the first systematic study aimed towards developing a complexity dichotomy for distance-based generalizations of some classical graph optimization problem was done in 2017 by Bacsó et al. [4]. They considered a natural distance generalization of the notion of independent set: given a positive integer k, a set S of vertices in a graph G is a distance-k independent set (also known as a k-scattered set) if any two distinct vertices in S are at distance at least k from each other. Bacsó et al. gave a complete characterization of graphs H such that, assuming ETH, the maximum size of a distance-k independent set on H-free graphs can be computed in subexponential time in the size of the input.

We remark that the notion of vertex cover has also been generalized with respect to the length of paths that need to be intersected. A k-path vertex cover is a set of vertices intersecting every path of order k [6, 7, 23, 37]. An equivalent notion, known as k-path transversal, is defined as set of vertices whose removal leaves a graph that does not contain a path of order k [22].

Structure of the Paper. After summarizing the necessary preliminaries in Sect. 2, we develop NP-completeness results in Sect. 3 and polynomial-time algorithms in Sect. 4. The main results of the paper – the complexity dichotomies – are derived in Sect. 5. Due to lack of space, proofs of results marked by \(\blacklozenge \) are omitted.

2 Preliminaries

Let G be a graph. The order of G is the number of vertices in it. For a vertex \(v\in V(G)\), we denote by \(N_G(v)\) (or simply N(v) if the graph is clear from the context) the set of neighbors of v in G, by \(N_G[v]\) (or simply N[v]) the set \(N_G(v)\cup \{v\}\). The degree of a vertex v is the cardinality of N(v). For a positive integer k, we denote by \(P_k\) the path graph of order k. The length of a path or a cycle is the number of edges in it. The girth of a graph G is the minimum length of a cycle in G (or \(\infty \) is G is acyclic). The distance between two vertices u and v in G is defined as the length of a shortest path between u and v (or \(\infty \) if there is no u, v-path in G). Given two sets \(A, B \subseteq V(G)\), we denote by \(\textsf {dist}_G(A,B)\) the minimum over all distances in G between a vertex in A and a vertex in B. When clear from context, we may simply write \(\textsf {dist}(A,B)\). For simplicity, if A contains a unique element a, then we may simply write \(\textsf {dist}(a,B)\), and similarly for B.

A distance-k vertex cover in G is a set C of vertices such that for all edges \(e \in E(G)\), it holds \(\textsf {dist}(e,C) \le k\). We denote by \(\tau _k(G)\) the size of a minimum distance-k vertex cover of G. For an integer \(k \ge 0\), the Distance-\(k\) Vertex Cover problem is formally defined as follows.

figure a

In particular, Vertex Cover is the same as Distance-\(0\) Vertex Cover.

An induced subgraph of a graph G is any graph H such that \(V(H)\subseteq V(G)\) and \(E(H) = \{\{u,v\}\in E(G) : u,v\in V(H)\}\). Given a graph G and a set \(S\subseteq V(G)\), we denote by G[S] the subgraph of G induced by S, that is, the unique induced subgraph of G with vertex set S. Given two graphs G and H, we say that G is H-free if no induced subgraph of G is isomorphic to H. More generally, for graphs \(H_1,\ldots , H_p\), we say that G is \(\{H_1,\ldots , H_p\}\)-free if G is \(H_i\)-free for all \(i\in \{1,\ldots , p\}\). The claw is the graph with four vertices and three edges, all having an endpoint in common. Given two graphs G and H, we denote by \(G+H\) their disjoint union. For a non-negative integer s, we denote by sG the disjoint union of s copies of G.

An induced matching in a graph G is a set M of edges of G such that no two of them share an endpoint (that is, M is a matching) and G contains no edge whose endpoints belong to different edges of M.

The line graph of a graph G is the graph, denoted by L(G), with vertex set E(G) in which two distinct vertices are adjacent if and only if the corresponding edges of G have an endpoint in common. It is well known, and easily observed, that line graphs are claw-free. A graph is chordal if it does not contain an induced cycle of length at least four, bipartite if its vertex set can be partitioned into two independent sets, planar if it can be drawn on the plane with no edges crossing, and cubic if every vertex has degree three. A linear forest is a disjoint union of paths. The operation of subdividing en edge \(\{u,v\}\) in a graph G means deleting the edge and introducing a new vertex w adjacent precisely to u and v.

Given a positive integer k and a graph G, a set \(S\subseteq V(G)\) is a distance-k dominating set in G if every vertex in G is at distance at most k from S. A dominating set in a graph G is a distance-1 dominating set, and a connected dominating set is a dominating set S such that the induced subgraph G[S] is connected.

3 NP-Completeness Results

3.1 When H Is Not a Linear Forest

There are two reasons why the forbidden induced subgraph H may fail to be a linear forest: either because it is not a forest, that is, it contains a cycle, or because it contains an induced claw. We first consider the case when H contains a claw and later the case when H contains a cycle.

When H Contains a Claw. Note that Distance-\(0\) Vertex Cover, that is, Vertex Cover, can be solved in polynomial time for claw-free graphs [28, 34]. However, as we show next, this is not the case for Distance-\(k\) Vertex Cover when \(k \ge 1\) (unless \(\P = \textsf {NP}\)). The proof goes in two steps. First, we generalize the notion of edge dominating set to its distance-based variant, and consider the corresponding decision problem called Distance-\(k\) Edge Dominating Set. For \(k = 0\) the problem coincides with the NP-complete Edge Dominating Set problem. We establish NP-completeness also for all \(k \ge 1\). Then we use this result to prove that, for every integer \(k\ge 1\), Distance-\(k\) Vertex Cover is NP-complete on line graphs, which are claw-free.

For an edge e and a set of edges F, we denote by \(\textsf {dist}(e,F)\) the minimum over all distances between an endpoint of e and an endpoint of an edge in F. Given an integer \(k \ge 0\) and a graph G, a set \(F\subseteq E(G)\) is a distance-k edge dominating set if for every edge \(e \in E(G)\), \(\textsf {dist}(e,F) \le k\). The corresponding decision problem is defined as follows.

figure b

The Edge Dominating Set problem, which in our context is equivalent to the Distance-0 Edge Dominating Set problem, is known to be NP-complete.

Theorem 1

(Yannakakis and Gavril [36]). Edge Dominating Set is \(\mathsf {NP}\)-complete, even for cubic bipartite graphs and cubic planar graphs.

Construction 1

Given a graph G and an integer \(k \ge 1\), we define a graph \(G'\) obtained from G as follows: for each edge \(\{u,v\} \in E(G)\), create a path \(P_{u,v}\) made of 2k new vertices and connect the endpoints of \(P_{u,v}\) to u and v, respectively. The path \(P_{u,v}\) together with the edge \(\{u,v\}\) is called the u, v-gadget. Note that the u, v-gadget is an induced cycle in \(G'\) of length \(2k+2\). In particular, there exists a unique edge \(e' \in E(G')\) of the u, v-gadget such that \(\textsf {dist}_{G'}(e',u) = \textsf {dist}_{G'}(e',v) = k\). We call the edge \(e'\) the opposite edge of the edge \(\{u,v\}\). See Fig. 1 for an example.

Fig. 1.
figure 1

An edge \(\{u,v\}\) (left) and its corresponding u, v-gagdet (right).

Full size image

\(\blacklozenge \) Theorem 2. For every integer \(k \ge 1\), Distance-k Edge Dominating Set is \(\mathsf {NP}\)-complete, even for bipartite graphs with maximum degree 6 and for planar graphs with maximum degree 6.

Fig. 2.
figure 2

An example of the graphs used in the proof of Theorem 3: the input graph G, the graph \(G'\) obtained from G, and H the line graph of \(G'\). Dashed edges in \(G'\) correspond to square shaped vertices in H.

Full size image

Proof sketch

Fix an integer \(k\ge 1\). Since distances in graphs can be computed efficiently using breadth-first search, the Distance-k Edge Dominating Set problem is in NP. Let \(G'\) be the graph obtained from Construction 1 given G and k. Note that \(G'\) can be obtained in polynomial time. To complete the proof, it can be shown that G contains an edge dominating set of size at most \(\ell \) if and only if \(G'\) contains a distance-k edge dominating set of size at most \(\ell \).    \(\square \)

\(\blacklozenge \) Theorem 3. For every fixed integer \(k\ge 1\), Distance-\(k\) Vertex Cover is \(\mathsf {NP}\)-complete for line graphs of bipartite graphs and line graphs of planar graphs, even if the maximum degree (of the line graphs) is at most 6 if \(k = 1\) and at most 12 if \(k \ge 2\).

Proof sketch

Fix a positive integer k and let G be a graph. We construct a graph \(G'\) from G by adding for each vertex \(u\in V(G)\) a new vertex \(u'\) and the edge \(\{u,u'\}\) in \(G'\). Let H be the line graph of \(G'\). See Fig. 2 for an example. Note that H can be computed in polynomial time. The rest of the proof consists in showing that G has a distance-k edge dominating set with size at most \(\ell \) if and only if H has a distance-k vertex cover with size at most \(\ell \).    \(\square \)

Since every line graph is claw-free, Theorem 3 implies the following result.

Corollary 1

Let H be a graph containing a claw as induced subgraph. Then for every fixed integer \(k \ge 1\), Distance-\(k\) Vertex Cover is \(\mathsf {NP}\)-complete on H-free graphs.

When H Contains a Cycle. We start by generalizing a well-known fact, observed first in 1974 by Poljak [32], that a double subdivision of an edge increases the minimum size of a vertex cover by exactly one.

\(\blacklozenge \) Lemma 1 Let G be a graph, let \(e \in E(G)\), and let \(G'\) be the graph obtained from G by subdividing edge e exactly \(2k+2\) times, for some integer \(k\ge 0\). Then \(\tau _k(G') = \tau _k(G) + 1\).

An iterative application of Lemma 1 leads to the following result.

\(\blacklozenge \) Corollary 2 Let G be a graph, let \(e\in E(G)\), and let \(G'\) be the graph obtained from G by subdividing edge e exactly \(p(2k+2)\) times, for some two integers \(k\ge 0\) and \(p\ge 0\). Then \(\tau _k(G') = \tau _k(G) + p\).

Theorem 4

Let H be a graph containing a cycle. Then for every fixed integer \(k \ge 0\), Distance-\(k\) Vertex Cover is \(\mathsf {NP}\)-complete on H-free graphs.

Proof

Let G be any graph and k a non-negative integer. Denote by g the girth of H and let \(G'\) be the graph obtained from G by subdividing every edge of G exactly \(g(2k+2)\) times. Note that \(G'\) is obtained in polynomial time and by Corollary 2, \(\tau _k(G')=\tau _k(G)+g|E(G)|\). Moreover, notice that \(G'\) has no cycle of length g, and thus is H-free. By Theorem 3, Distance-k Vertex Cover is NP-complete, and hence the problem remains NP-complete on H-free graphs when H contains a cycle.    \(\square \)

Corollary 1 and Theorem 4 imply the following result.

Corollary 3

Let H be a graph that is not a linear forest. Then for any fixed integer \(k \ge 1\), Distance-\(k\) Vertex Cover is \(\mathsf {NP}\)-complete on H-free graphs.

3.2 When H Is a Linear Forest

We now show that Distance-\(k\) Vertex Cover remains NP-complete in the class of H-free graphs even for certain linear forests. In particular, this is the case when \(H = 2P_{k+1}\) for \(k\ge 2\) and when H is either \(P_{5}\) or \(2P_{3}\) for \(k = 1\), even if the input graph is chordal.

Construction 2

Given a graph G containing at least one edge and an integer \(k \ge 1\), we construct a graph \(G'\) as follows. First, we take a complete graph on a set Q of |V(G)| new vertices such that for every vertex \(u\in V(G)\) there exists a unique vertex \(u'\) in Q. Then, for each edge \(\{u,v\} \in E(G)\), we create a u, v-ladder as follows. We create a path \(P_{u{,}v}\) of order k and connect one of its endpoints to both \(u'\) and \(v'\); then for each such vertex w of \(P_{u{,}v}\) we add a new vertex \(w'\) and make it adjacent exactly to the vertices in N[w] (in particular, this means that \(N[w'] = N[w]\) in the resulting graph). We call the unique edge e of the u, v-ladder such that \(\textsf {dist}_{G'}(e,\{u,v\})=k\) the opposite edge of the edge \(\{u',v'\}\). See Fig. 3 for an example.

Fig. 3.
figure 3

An edge \(\{u,v\}\) (left) and its corresponding u, v-ladder (right).

Full size image

Theorem 5

Distance-\(1\) Vertex Cover is \(\mathsf {NP}\)-complete on \(\{P_{5}, 2P_3\}\)-free chordal graphs and, for all \(k \ge 2\), Distance-\(k\) Vertex Cover is \(\mathsf {NP}\)-complete on \(2P_{k+1}\)-free chordal graphs.

Proof

Let G be a graph containing at least one edge and k a positive integer. Let \(G'\) be the graph obtained from Construction 2 given G and k. Note that \(G'\) can be obtained in polynomial time. Besides, it is easily observed that \(G'\) is chordal. Notice that any induced subgraph of \(G'\) isomorphic to \(P_{\max \{k+1,3\}}\) contains at least one vertex in the clique Q, which implies that \(G'\) cannot contain \(2P_{\max \{k+1,3\}}\) as an induced subgraph, that is, if \(k = 1\), then \(G'\) is \(2P_3\)-free, and if \(k\ge 2\), then \(G'\) is \(2P_{k+1}\)-free. Furthermore, if \(k=1\), then \(G'\) is also \(P_5\)-free. To see this, consider an induced path P in \(G'\) of order 4. Then P has both its endpoints in \(V(G) \setminus Q\) and its two internal vertices in Q, as otherwise P would not be induced. This readily implies that P is a maximal path, and thus that \(G'\) is \(P_5\)-free.

To complete the proof, we show that G has a vertex cover with size at most \(\ell \) if and only if \(G'\) has a distance-k vertex cover with size at most \(\ell \).

Let C be a vertex cover in G with size at most \(\ell \) and \(C'= \{u': u\in C\}\). Note that \(C'\subseteq Q\subseteq V(G')\); we claim that \(C'\) is a distance-k vertex cover in \(G'\). Suppose that this is not the case. Then there exists an edge \(f\in E(G')\) at distance more than k from \(C'\). Observe that \(C'\subseteq Q\), and thus, every edge of \(G'\) having one endpoint in Q is at distance at most 1 from \(C'\). Therefore, as f is at distance more than k from \(C'\), it must have both endpoints in \(V(G')\setminus Q\), and hence belongs to an u, v-ladder for some edge \(\{u,v\}\in E(G)\). Since C is a vertex cover in G, at least one of u or v belongs to C. We assume without loss of generality that u belongs to C. Since f belongs to the u, v-ladder and \(u' \in C'\), we have \(\textsf {dist}_{G'}(f,C') \le \textsf {dist}_{G'}(f,u') \le k\), a contradiction. Thus, \(C'\) is a distance-k vertex cover in \(G'\) with size \(|C'|=|C| \le \ell \).

Let \(C'\) be a distance-k vertex cover in \(G'\) with size at most \(\ell \). Observe that if \(w\in V(G')\setminus Q\), then w is a vertex in a u, v-ladder for some \(\{u,v\}\in E(G)\). Observe that, by construction of \(G'\), every edge f of \(G'\) with \(\textsf {dist}_{G'}(f,w) \le k\) is such that \(\textsf {dist}_{G'}(f,u') \le k\). Hence, if \(w\in C'\), then the set \((C'\setminus \{w\})\cup \{u'\}\) is also a distance-k vertex cover in \(G'\) with size at most \(\ell \). Hence, we may assume that \(C'\subseteq Q\). Let \(C=\{u\in V(G): u'\in C'\}\). Suppose that C is not a vertex cover in G. Then there is an edge \(\{u,v\}\in E(G)\) such that \(u,v\not \in C\). Therefore, \(u',v'\not \in C'\) but then the opposite edge e of the u, v-ladder is such that \(\textsf {dist}_{G'}(e,C') > \textsf {dist}_{G'}(e, \{u',v'\}) = k\), a contradiction. Hence, C is a vertex cover in G with size \(|C|=|C'|\le \ell \).

Since Vertex Cover is NP-complete [20], we obtain that Distance-1 Vertex Cover is NP-complete on \(\{P_{5},2P_3\}\)-free chordal graphs and that, for all \(k\ge 2\), Distance-\(k\) Vertex Cover is NP-complete on \(2P_{k+1}\)-free chordal graphs.    \(\square \)

4 Polynomial Algorithms

In this section we identify, for each integer \(k\ge 1\), an infinite family of graph classes in which Distance-k Vertex Cover can be solved in polynomial time. Our first result will be based on the following structural property of \(P_t\)-free graphs.

Theorem 6

(Camby and Schaudt [9]). Let \(t \ge 4\) be an integer, let G be a connected \(P_t\)-free graph, and let S be any minimum connected dominating set in G. Then the subgraph induced by S in G is either \(P_{t-2}\)-free or isomorphic to \(P_{t-2}\).

Theorem 6 has the following consequence for distance-k vertex covers in \(P_{2k+2}\)-free graphs.

Lemma 2

For every integer \(k\ge 1\), every connected \(P_{2k+2}\)-free graph G has a distance-k vertex cover that induces a path of order at most two.

Proof

Fix a positive integer k. To prove the statement of the lemma, we will in fact establish the following stronger statement: every connected \(P_{2k+2}\)-free graph G has a distance-k dominating set that induces a path of order at most two. It follows immediately from the definitions that every distance-k dominating set is also a distance-k vertex cover, hence this will indeed suffice.

The proof is by induction on k. Suppose first that \(k = 1\). In this case, the statement says that every connected \(P_{4}\)-free graph G has a dominating set that induces a path of order at most two. This follows from the well-known fact that for every connected \(P_4\)-free graph G with at least two vertices, the complement of G is disconnected (see, e.g., [12]). Indeed, denoting by C any component of the complement of G and taking \(u\in V(C)\) and \(v\in V(G)\setminus V(C)\), the set \(\{u,v\}\) is a dominating set in G that induces a path of order two. Suppose now that \(k>1\) and consider a connected \(P_{2k+2}\)-free graph G. Let S be a minimum connected dominating set in G and let \(G'\) be the subgraph of G induced by S. Following Theorem 6, we obtain that \(G'\) is either \(P_{2k}\)-free or isomorphic to \(P_{2k}\). If \(G'\) is \(P_{2k}\)-free, then the induction hypothesis implies that \(G'\) has a distance-\((k-1)\) dominating set that induces a path of order at most two. If \(G'\) is isomorphic to \(P_{2k}\), with vertices \(v_1,\ldots , v_{2k}\) in order, then the edge \(\{v_k,v_{k+1}\}\) is a distance-\((k-1)\) dominating set in \(G'\). In either case, \(G'\) has a distance-\((k-1)\) dominating set \(S'\) that induces a path of order at most two. Since every vertex in G is either in S or has a neighbor in S, we infer that \(S'\) is a distance-k dominating set in G that induces a path of order at most two.    \(\square \)

In the following theorem, the running time of the algorithm is independent of k, that is, the \(\mathcal {O}\) notation does not hide any constants depending on k.

\(\blacklozenge \) Theorem 7. For every integer \(k\ge 1\), there is an algorithm with running time \(\mathcal {O}((|V(G)|+|E(G)|)^2)\) that takes as input a \(P_{2k+2}\)-free graph G and computes a minimum distance-k vertex cover of G.

Proof sketch

Fix a positive integer k and let G be a \(P_{2k+2}\)-free graph. To compute a minimum distance-k vertex cover of G, we first compute the connected components \(G_1,\ldots , G_s\) of G, solve the problem in each connected component \(G_i\), and combine the obtained solutions. By Lemma 2, each connected component \(G_i\) of G has a distance-k vertex cover that induces a path of order at most two. Thus, we immediately obtain a polynomial-time algorithm for computing a minimum distance-k vertex cover of a nontrivial component \(G_i\). We first check if there exists a vertex \(u\in V(G_i)\) such that \(\{u\}\) is a distance-k vertex cover of \(G_i\). If this is the case, then we have an optimal solution; otherwise we check for each edge \(\{u,v\}\in E(G_i)\) if \(\{u,v\}\) is a distance-k vertex cover of \(G_i\). Once we find one, we return it. We can verify, in each \(G_i\), if a vertex or an edge is a distance-k vertex cover using a breadth-first search, and the running time follows.    \(\square \)

Remark 1

For \(k = 1\), an improved running time of \({\mathcal O}(|V(G)|+|E(G)|)\) can be obtained using a different approach: the fact that \(P_4\)-free graphs have clique-width at most two, the fact that the defining property of distance-1 vertex covers can be expressed in \(\mathrm{MSO}_1\) logic, and a metatheorem for \(\mathrm{MSO}_1\) problems on graphs of bounded clique-width of Courcelle et al. [13].

We now consider the more general case of \((P_{2k+2}+sP_{\max \{k,2\}})\)-free graphs for two integers \(k\ge 1\) and \(s\ge 0\). We first consider the case \(k = 1\) and then the case \(k\ge 2\).

\(\blacklozenge \) Lemma 3 For every integer \(s\ge 0\), every connected \((P_{4}+sP_2)\)-free graph G has a distance-1 vertex cover that induces a linear forest of order at most \(2s+2\).

Lemma 4

For every two integers \(k\ge 2\) and \(s\ge 0\), every connected \((P_{2k+2}+sP_k)\)-free graph G has a distance-k vertex cover that induces a linear forest of order at most \(f_k(s)\) where

$$f_k(s) = \left\{ \begin{array}{ll}2 &{}\text { if }s=0\,,\\ (s+1)k+2&{} \text { if }s \ge 1\,. \end{array}\right. $$

Proof

Fix an integer \(k\ge 2\). We use induction on s. For \(s = 0\), the statement follows from Lemma 2.

Suppose now that \(s \ge 1\) and that every connected \((P_{2k+2}+(s-1)P_k)\)-free graph has a distance-k vertex cover that induces a linear forest of order at most \(f_k(s-1)\). Let G be a connected \((P_{2k+2}+sP_k)\)-free graph. If G is \((P_{2k+2}+(s-1)P_k)\)-free, then G has a distance-k vertex cover that induces a linear forest of order at most \(f_k(s-1) \le f_k(s)\). On the other hand, if G is not \((P_{2k+2}+(s-1)P_k)\)-free, then there exists a set \(S\subseteq V(G)\) inducing a \(P_{2k+2}+(s-1)P_k\). Note that S induces a linear forest of order \((s+1)k+2 = f_k(s)\). It thus suffices to show that S is a distance-k vertex cover in G. Let \(X= N(S)\) be the set of vertices not in S and with a neighbor in S and \(Y = V(G) \setminus (S \cup X)\) be the set of vertices not in S and without a neighbor in S. Let e be an edge of G. If e has an endpoint in \(S\cup X\), then \(\textsf {dist}_G(e,S)\le 1\le k\). So let e be entirely contained in Y. Since G is connected, there exists a shortest path P between an endpoint of e and a vertex in S. Since G is \((P_{2k+2}+sP_k)\)-free, the part of P entirely contained in Y has at most \(k-1\) vertices. Other than that, P has exactly one vertex in X and exactly one in S. Thus, the length of P is at most k, which implies \(\textsf {dist}_G(e,S)\le k\). This shows that S is a distance-k vertex cover in G and completes the proof.    \(\square \)

Lemmas 3 and 4 imply that for all integers \(k\ge 0\) and \(s\ge 0\) the minimum size of a distance-k vertex cover in a \((P_{2k+2}+sP_{\max \{k,2\}})\)-free graph is bounded by a function depending only on k and s but independent of G. Thus, we can do a complete enumeration of small subsets of vertices to find a minimum distance-k vertex cover in such a graph, and essentially the same approach as the one used to prove Theorem 7 using Lemma 2 can be used to prove the following theorem using Lemmas 3 and 4.

Theorem 8

For every two integers \(k\ge 1\) and \(s\ge 0\), there is a polynomial-time algorithm that takes as input a \((P_{2k+2}+sP_{\max \{k,2\}})\)-free graph G and computes a minimum distance-k vertex cover of G.

5 Complexity Dichotomies

Our results from Sects. 3 and 4 allow us to obtain a complexity dichotomy of Distance-\(k\) Vertex Cover on H-free graphs, for all \(k \ge 1\).

Theorem 9

For every graph H, the following holds:

  • Distance-\(1\) Vertex Cover is solvable in polynomial time in the class of H-free graphs if H is an induced subgraph of \(P_4+sP_2\), for some \(s\ge 0\), and NP-complete otherwise.

  • For every integer \(k\ge 2\), Distance-\(k\) Vertex Cover is solvable in polynomial time in the class of H-free graphs if H is an induced subgraph of \(P_{2k+2}+sP_k\) for some \(s\ge 0\), and NP-complete otherwise.

Proof Fix a graph H and let \(\mathcal {G}\) be the class of H-free graphs. If H is not a linear forest, then for all \(k\ge 1\), Corollary 3 implies that Distance-\(k\) Vertex Cover is NP-complete on \(\mathcal {G}\). Suppose that H is a linear forest.

Consider first the case when \(k = 1\). If H contains \(P_{5}\) or \(2P_3\) as an induced subgraph, then \(\mathcal {G}\) contains the class of \(\{P_5,2P_3\}\)-free chordal graphs, and hence by Theorem 5 Distance-\(1\) Vertex Cover is NP-complete on \(\mathcal {G}\). Otherwise, we obtain that H is \(\{P_5,2P_3\}\)-free. Recall that H is a linear forest. Let us denote by t be the maximum order of a component of H and let P be a component of H of order t. If \(t\le 2\), then every component of H has order at most two. If \(t\ge 3\), then, since H is \(2P_3\)-free, every component of H other than P has order at most two. In either case, every component of H other than P has order at most two, which implies that H is an induced subgraph of \(P_{t}+sP_2\) for some \(s\ge 0\). Since H is \(P_5\)-free, we have \(t\le 4\), and hence every H-free graph is \((P_{4}+sP_2)\)-free. Thus, by Theorem 8 the problem can be solved in polynomial time for graphs in \(\mathcal {G}\).

Suppose now that \(k\ge 2\). If H contains \(2P_{k+1}\) as an induced subgraph, then \(\mathcal {G}\) contains the class of \(2P_{k+1}\)-free chordal graphs, and hence by Theorem 5 Distance-\(k\) Vertex Cover is NP-complete on \(\mathcal {G}\). Again, let t denote the maximum order of a component of H and let P be a component of H of order t. If \(t\le k\), then every component of H has order at most k. If \(t\ge k+1\), then, since H is \(2P_{k+1}\)-free, every component of H other than P has order at most k. Thus, in either case, every component of H other than P has order at most k, and H is an induced subgraph of \(P_{t}+sP_k\) for some \(s\ge 0\). Since H is \(2P_{k+1}\)-free, it is also \(P_{2k+3}\)-free, which implies that \(t\le 2k+2\), and thus H is an induced subgraph of \(P_{2k+2}+sP_k\) for some \(s\ge 0\). It follows that every H-free graph is \((P_{2k+2}+sP_k)\)-free. Thus, by Theorem 8 the problem can be solved in polynomial time for graphs in \(\mathcal {G}\).    \(\square \)

For the case when the forbidden induced subgraph is connected, Theorems 7 and 9 imply the following dichotomy.

Corollary 4

For every connected graph H and integer \(k\ge 1\), the Distance-\(k\) Vertex Cover problem is solvable in time \(\mathcal {O}((|V(G)|+|E(G)|)^2)\) in the class of H-free graphs if H is an induced subgraph of \(P_{2k+2}\), and \(\mathsf {NP}\)-complete otherwise.

Furthermore, as explained in Remark 1, the running time can be improved to linear for the case \(k = 1\).