betaFeedback

Reading v1View latest version

WorksComputer Science

Metric Dimension Parameterized by Bag-Connected Treewidth and Bag-Connected Pathwidth

Abstract

The metric dimension of a graph is the minimum size of a set of vertices whose distance vectors distinguish all vertices of the graph. We prove that \MetricDimension{} is NP-complete on planar graphs of treewidth and bag-connected treewidth exactly three. The graphs in our construction have no induced cycle longer than four and have (prefix-connected) pathwidth at most four. In particular, the problem admits no XP algorithm parameterized by bag-connected treewidth unless P=NP\mathrm P=\mathrm{NP}. This answers questions of Bonnet and Purohit and of Bousquet, Deschamps, and Parreau. We prove that the problem is fixed-parameter tractable when parameterized by bag-connected pathwidth.

Introduction

Let GG be a finite, simple, connected graph. A set S⊆V(G)S \subseteq V(G) is a resolving set if, for every two distinct vertices u,vu, v, there is a vertex s∈Ss \in S with dist⁡G(s,u)≠dist⁡G(s,v)\operatorname{dist}_G(s,u) \ne\operatorname{dist}_G(s,v). The metric dimension dim⁡(G)\dim(G) is the minimum size of a resolving set. This notion was introduced independently by Slater and by Harary and Melter [20, 24]. In the decision problem Metric Dimension, we are given a graph GG and an integer kk and ask whether dim⁡(G)≤k\dim(G) \le k.

The problem is NP-complete in general [18 Problem GT61] and W[2]-complete when parameterized by solution size, even on subcubic graphs [21]. It is polynomial-time solvable on trees and outerplanar graphs [11, 22]. Belmonte, Fomin, Golovach, and Ramanujan proved fixed-parameter tractability for the combined parameter tree-length plus maximum degree [2]. Their result also gives fixed-parameter tractability for tree-length plus solution size.

For ordinary treewidth, Bonnet and Purohit proved W[1]-hardness, even for the larger parameter pathwidth and on graphs of constant maximum degree [5]. Li and Pilipczuk subsequently proved NP-hardness on graphs of treewidth and pathwidth at most 24 [23]. See [9, 14, 15, 16, 17, 25] for more results on this topic. A recent preprint of Benoit gives NP-hardness on graphs of treewidth two and pathwidth at most five [3].

A tree decomposition is bag-connected if every bag induces a connected subgraph. The bag-connected treewidth ctw⁡(G)\operatorname{ctw}(G) of a graph GG is the minimum width of such a decomposition [12, 19]. A connected bag of size at most q+1q+1 has diameter at most qq, so bag-connected treewidth bounds both the size and the diameter of the bags. Bonnet and Purohit asked whether Metric Dimension is fixed-parameter tractable when parameterized by bag-connected treewidth alone [5]. The algorithm for tree-length plus maximum degree already gives fixed-parameter tractability for bag-connected treewidth plus maximum degree, so the remaining question was whether the degree bound can be dropped. Bousquet, Deschamps, and Parreau [6] proved that Metric Dimension is fixed-parameter tractable by treewidth on chordal graphs. They asked whether this extends to decompositions in which both the bag size and the bag diameter are bounded. A positive answer would in particular imply fixed-parameter tractability by bag-connected treewidth. We answer both questions negatively, even for planar graphs and even if one asks only for an XP algorithm, by showing that the problem is para-NP hard when parameterized by bag-connected treewidth.

Theorem 1.1. Metric Dimension is NPNP-complete on graphs GG satisfying all of the following properties:

  • GG is planar.

  • tw⁡(G)=ctw⁡(G)=3\operatorname{tw}(G) = \operatorname{ctw}(G) = 3.

  • GG has no induced cycle of length greater than four.

  • GG admits a bag-connected tree decomposition of width three in which every bag has induced diameter at most two.

  • GG admits a path decomposition of width at most four in which the union of every initial sequence of bags is connected.

The hardness holds even when both decompositions are given as part of the input.

Recall that an XP algorithm parameterized by bag-connected treewidth qq has running time f(q)ng(q)f(q)n^{g(q)} for computable functions f,gf,g. Such an algorithm runs in polynomial time when q=3q = 3. Hence Theorem 1.1 rules out an XP algorithm unless P=NPP = NP.

Our construction shows that the chordal result does not extend to 4-chordal graphs, that is, graphs with no induced cycle longer than four. The output graphs have tree-length two, whereas chordal graphs have tree-length at most one. Furthermore, every isometric cycle in an output graph has length at most four. Consequently, Metric Dimension is NP-hard even when both the treewidth and the maximum length of an isometric cycle are fixed constants.

We next ask what happens if the decomposition tree is required to be a path. The bag-connected pathwidth cpw⁡(G)\operatorname{cpw}(G) of a graph GG is the minimum width of a path decomposition in which every bag induces a connected subgraph. There is a version of connected pathwidth studied in graph searching, where the unions of initial sequences of bags must be connected [10]. We denote this parameter by gs-cpw⁡(G)\operatorname{gs\text{-}cpw}(G).

Theorem 1.2. There is an algorithm that finds a minimum resolving set of a connected graph GG in time f(cpw⁡(G))∣V(G)∣O(1)f(\operatorname{cpw}(G))|V(G)|^{O(1)}, where ff is a computable function.

Preliminaries

We write dist⁡G(u,v)\operatorname{dist}_G(u,v) for the distance between vertices u,vu,v of a connected graph GG, and omit the subscript when the graph is clear from the context. For A⊆V(G)A \subseteq V(G), we write G[A]G[A] for the subgraph induced by AA and G−AG-A for G[V(G)∖A]G[V(G) \setminus A]. The external vertex boundary of AA is

∂GA={v∈V(G)∖A:v has a neighbor in A}.\partial_G A = \{v \in V(G) \setminus A : v\text{ has a neighbor in }A\}.

We omit the subscript GG when the ambient graph is clear, and use the same notation for a subgraph and its vertex set.

A set S⊆V(G)S \subseteq V(G) is a resolving set if, for every two distinct vertices u,vu,v, there is a vertex s∈Ss \in S with dist⁡(s,u)≠dist⁡(s,v)\operatorname{dist}(s,u) \ne\operatorname{dist}(s,v). A vertex that belongs to a resolving set will also be called a landmark. The metric dimension dim⁡(G)\dim(G) is the minimum size of a resolving set. A leaf is a vertex of degree one, and its incident edge is a pendant edge. We call a pair of leaves with a common neighbor a forcing pair, its members forcing leaves, and their common neighbor a forcing vertex. The two leaves have the same distance from every other vertex. Hence every resolving set contains at least one of them. We will use such pairs to force a choice of a landmark without prescribing which leaf is chosen.

A vertex cover of a graph FF is a set C⊆V(F)C \subseteq V(F) containing at least one endpoint of every edge. We write τ(F)\tau(F) for the minimum size of a vertex cover of FF. In Vertex Cover, the input is a graph FF and an integer tt, and the question is whether τ(F)≤t\tau(F) \le t.

A tree decomposition of GG consists of a tree TT and bags β(t)⊆V(G)\beta(t) \subseteq V(G), for t∈V(T)t \in V(T), such that every edge has both endpoints in some bag and, for every vertex vv, the nodes whose bags contain vv form a nonempty connected subtree of TT. Its width is max⁡t∣β(t)∣−1\max_t |\beta(t)| - 1, and the treewidth tw⁡(G)\operatorname{tw}(G) is the minimum possible width. We call the decomposition bag-connected if G[β(t)]G[\beta(t)] is connected for every tt. The bag-connected treewidth ctw⁡(G)\operatorname{ctw}(G) is the minimum width of a bag-connected tree decomposition of GG. In particular, tw⁡(G)≤ctw⁡(G)\operatorname{tw}(G) \le\operatorname{ctw}(G).

We call a rooted tree decomposition nice if all bags are nonempty, every leaf has a singleton bag, and every non-leaf node is of one of the following three types. An introduce node tt has one child t′t' and satisfies β(t)=β(t′)∪{v}\beta(t) = \beta(t') \cup\{v\} for some v∉β(t′)v \notin\beta(t'). A forget node tt has one child t′t' and satisfies β(t)=β(t′)∖{v}\beta(t) = \beta(t') \setminus\{v\} for some v∈β(t′)v \in\beta(t'). A join node tt has two children t1,t2t_1,t_2 with β(t)=β(t1)=β(t2)\beta(t) = \beta(t_1) = \beta(t_2).

A path decomposition is a tree decomposition whose underlying tree is a path. The bag-connected pathwidth cpw⁡(G)\operatorname{cpw}(G) of GG is the minimum width over all path decompositions where every bag is required to induce a connected graph. Thus ctw⁡(G)≤cpw⁡(G)\operatorname{ctw}(G) \le\operatorname{cpw}(G). The graph-search version of connected pathwidth, denoted by gs-cpw⁡(G)\operatorname{gs\text{-}cpw}(G), instead minimizes the width over path decompositions B1,…,BtB_1,\ldots,B_t for which G[⋃j=1iBj]G[\bigcup_{j=1}^{i} B_j] is connected for every ii. We write Nr(v)={w∈V(G):dist⁡(v,w)≤r}N_r(v) = \{w \in V(G) : \operatorname{dist}(v,w) \le r\} for the radius-rr neighborhood, or ball, around vv.

The length of a tree decomposition is the maximum of diam⁡G(β(t))\operatorname{diam}_G(\beta(t)) over its bags, where the diameter is measured in the whole graph. The tree-length tl⁡(G)\operatorname{tl}(G) is the minimum length of a tree decomposition [13]. The induced diameter of a connected bag is its diameter in the subgraph it induces. In our hardness construction, every bag has induced diameter at most two. A cycle is isometric if the distance between any two of its vertices is the same in the cycle and in the whole graph. Every isometric cycle is induced. We denote the maximum length of an isometric cycle by γiso(G)\gamma_{\mathrm{iso}}(G), with value zero for forests.

The tail construction

In this section, we introduce the graph gadgets used in our reduction, which we call tails, and analyze which vertex pairs remain unresolved by the forced landmarks.

A ladder with LL levels, where L≥2L \ge2, consists of two vertex-disjoint paths u1,…,uLu_1,\ldots,u_L and v1,…,vLv_1,\ldots,v_L, together with the edges uhvhu_hv_h for 1≤h≤L1 \le h \le L. The two paths are its rails, their vertices are rail vertices, and the edges uhvhu_hv_h are its rungs. The vertices uh,vhu_h,v_h and their rung are at level hh. The four-cycles uh−1uhvhvh−1uh−1u_{h-1}u_hv_hv_{h-1}u_{h-1}, for 2≤h≤L2 \le h \le L, are the ladder cells. We attach the ladder to an edge pqpq disjoint from its rails by adding pu1pu_1 and qv1qv_1. A marker at level hh, for 2≤h≤L2 \le h \le L, is an additional vertex chc_h whose neighbors are uh−1u_{h-1} and vh−1v_{h-1}. Thus a marker is attached to the rung one level before its own; together with that rung, it forms a marker triangle. Figure 1 illustrates these definitions.

Figure 1. A ladder with five levels, attached to the edge pqpq, and a marker c4c_4 at level four. The horizontal paths are the rails and the vertical edges uhvhu_hv_h are the rungs. The vertices p,q,c4p,q,c_4 are outside the ladder.

For a nonempty set X={x1,…,xk}⊆V(G)X = \{x_1,\ldots,x_k\} \subseteq V(G) with a fixed ordering, the distance vector to $X of a vertex v∈V(G)v \in V(G) is

dX(v)=(dist⁡(x1,v),…,dist⁡(xk,v)).\mathbf{d}_X(v) = \bigl(\operatorname{dist}(x_1,v),\ldots,\operatorname{dist}(x_k,v)\bigr).

The following standard lemma expresses distances through a separating set.

Lemma 3.1. Let GG be a connected graph and let ∅≠X⊆V(G)\varnothing\ne X \subseteq V(G). If CC is a component of G−XG-X, v∈Cv \in C, and s∈V(G)∖Cs \in V(G) \setminus C, then

dist⁡(s,v)=min⁡x∈X(dist⁡(s,x)+dist⁡(x,v)).\operatorname{dist}(s,v)=\min_{x\in X}\bigl(\operatorname{dist}(s,x)+\operatorname{dist}(x,v)\bigr).

In particular, if v,wv,w lie in different components of G−XG-X and satisfy dX(v)=dX(w)\mathbf{d}_X(v)=\mathbf{d}_X(w), then no vertex outside these two components distinguishes them.

Our construction attaches several ladders to the same edge pqpq and adds markers and further local vertices. A tail consists of one ladder and all vertices added locally to it, including its markers and forcing leaves; it excludes pp, qq and the leaves attached directly to them. The tails are pairwise disjoint connected subgraphs. All tails in our construction attach to the same boundary X={p,q}X=\{p,q\}. Thus, writing HH for the constructed graph and TaT_a for its aath tail, we have ∂HTa=X\partial_H T_a=X for every aa. We call the forcing leaves within a tail local forcing leaves, and the leaves attached directly to p,qp,q boundary leaves. The entrance graph of a tail consists of p,q,u1,v1p,q,u_1,v_1, the edges pqpq, pu1pu_1, u1v1u_1v_1, qv1qv_1, and the paths pwpv1pw_pv_1 and qwqu1qw_qu_1, where wp,wqw_p,w_q are two additional vertices of the tail. We specify the remaining local vertices and their edges below. For the common boundary of our tails, we always use the order (p,q)(p,q), so

dX(v)=(dist⁡(p,v),dist⁡(q,v)).\mathbf{d}_X(v)=\bigl(\operatorname{dist}(p,v),\operatorname{dist}(q,v)\bigr).

We will repeatedly use Lemma 3.1 to compute distances from vertices outside a tail.

The markers in our construction will represent the edges of a Vertex Cover instance. For now, we allow an arbitrary choice of the levels at which they occur. Let L≥2L\ge2, and let D1,…,DnD_1,\ldots,D_n be subsets of {2,…,L}\{2,\ldots,L\}. We start with an edge pqpq and put X={p,q}X=\{p,q\}. For each index a∈{1,…,n}a\in\{1,\ldots,n\}, we attach a ladder with LL levels to pqpq, using the superscript aa to distinguish its vertices from those of the other ladders. Its rails are u1a,…,uLau_1^a,\ldots,u_L^a and v1a,…,vLav_1^a,\ldots,v_L^a, its rungs are uhavhau_h^av_h^a, and its attachment edges are pu1apu_1^a and qv1aqv_1^a. For every h∈Dah\in D_a, we add a marker chac_h^a adjacent to uh−1au_{h-1}^a and vh−1av_{h-1}^a. The marker is thus attached to the rung immediately before its level, as illustrated in Figure 1.

We next arrange that certain landmarks distinguish the rails while leaving markers at the same level unresolved. For each index aa and each x∈{p,q}x\in\{p,q\}, we add vertices wxa,sxaw_x^a,s_x^a. We make wpaw_p^a adjacent to p,v1ap,v_1^a, and wqaw_q^a adjacent to q,u1aq,u_1^a. The vertices wpa,wqaw_p^a,w_q^a, together with p,q,u1a,v1ap,q,u_1^a,v_1^a, form the entrance graph of the tail. We then make sxas_x^a adjacent to x,wxax,w_x^a and attach two leaves fx,0a,fx,1af_{x,0}^a,f_{x,1}^a to it. Thus sxas_x^a is a local forcing vertex with forcing pair {fx,0a,fx,1a}\{f_{x,0}^a,f_{x,1}^a\}. Finally, we attach five leaves p0,p1p^0,p^1 to pp and two leaves q0,q1q^0,q^1 to qq. There are no further edges, and we denote the resulting graph by HH. The tail TaT_a consists of all vertices introduced for index aa, including its local forcing leaves but excluding p,qp,q and their leaves. Each tail is a component of H−XH-X and has external boundary $\partial_H T_a=X. Figure 2 shows the entrance graph and a complete example of a tail.

The entrance graph and a complete tail

Figure 2. The entrance graph and a complete tail. In (a), deleting sps_p, sqs_q and their leaves gives K4K_4 with two opposite edges subdivided once. In (b), pp, qq and their leaves are shared with all other tails. Blue leaves indicate one choice from each depicted forcing pair; the blue vertex u11u^1_1 is an additional landmark used in the reduction. Red diamonds are markers.

To see the role of these vertices, observe that spas_p^a has distance two from both u1au_1^a and v1av_1^a, although it is closer to pp than to qq. It therefore distinguishes the vv-rail of its own tail from the vv-rail of another tail. The vertex sqas_q^a does the same for the uu-rails. Neither vertex distinguishes markers at the same level. Their leaves inherit these properties, and every resolving set must contain at least one leaf from each pair.

Lemma 3.2. The distance vectors dX(v)\mathbf{d}_X(v) of the vertices in HH are as follows, with coordinates ordered as (p,q)(p,q).

Vertex vvDistance vector dX(v)\mathbf{d}_X(v)
pp, qq(0,1)(0,1), (1,0)(1,0)
pjp^j, qjq^j(1,2)(1,2), (2,1)(2,1)
uhau^a_h, vhav^a_h(h,h+1)(h,h+1), (h+1,h)(h+1,h)
chac^a_h(h,h)(h,h)
spas^a_p, wpaw^a_p(1,2)(1,2)
sqas^a_q, wqaw^a_q(2,1)(2,1)
fp,jaf_{p,j}^a, fq,jaf_{q,j}^a(2,3)(2,3), (3,2)(3,2)

For every local forcing vertex sxas^a_x and every marker chbc^b_h, regardless of whether a=ba=b, we have

dist⁡(sxa,chb)=h+1,dist⁡(fx,ja,chb)=h+2.(1)\operatorname{dist}(s^a_x,c^b_h)=h+1,\qquad\operatorname{dist}(f^a_{x,j},c^b_h)=h+2. \tag*{(1)}

Proof. We first compute the distances to the boundary. A shortest path cannot pass through a marker as an internal vertex, since the two neighbors of the marker are joined by a rung. We may therefore ignore the markers when computing distances between the other vertices. Along the ladder, uhau^a_h has distance hh from pp and needs one extra step to reach qq; the distances for vhav^a_h are symmetric. The paths through sxa,wxas^a_x,w^a_x give no shorter route to either end of the first rung, and hence do not change these distances. As chac^a_h is adjacent to both rail vertices at level h−1h-1, its distance from each boundary vertex is hh. We read off the remaining entries from the beginning of the tail, adding one step when we pass to a forcing leaf. We next verify Equation (1). In its own tail, sxas_x^a has distance two from both first rail vertices, and hence distance hh from both rail vertices at level h−1h-1. Its distance to cac^a is therefore h+1h+1. For a marker in another tail, we obtain the same value from Lemma 3.1: sxas_x^a has distance one from the boundary, and dX(chb)=(h,h)\mathrm{d}_X(c_h^b)=(h,h). Again, passing to a forcing leaf adds one step.

We now show that the forced landmarks leave precisely the marker pairs that we want to use in the reduction.

Lemma 3.3. Choose one leaf from each of the 2n+22n+2 forcing pairs, and let S0S_0 be the resulting set. The pairs not resolved by S0S_0 are precisely the pairs of markers at the same level in different tails.

Proof. A selected vertex distinguishes itself from every other vertex, so we consider only pairs outside S0S_0. For each x∈{p,q}x \in\{p,q\}, let x^\widehat{x} be the selected leaf adjacent to xx. For every y≠x^y \ne\widehat{x}, we have dist⁡(x,y)=1+dist⁡(x,y)\operatorname{dist}(x,y)=1+\operatorname{dist}(x,y). The two selected boundary leaves therefore distinguish any two vertices outside S0S_0 with different distance vectors to XX. We are left with pairs having the same distance vector to XX, which we examine using Lemma 3.2.

Let f^xa\widehat{f}_x^a be the selected leaf at sxas_x^a. Its distances to sxas_x^a and wxaw_x^a are one and two, respectively. Every other vertex outside S0S_0 with their common distance vector to XX is at distance at least three from f^xa\widehat{f}_x^a. Thus all pairs involving an ss-vertex or a ww-vertex are resolved. Similarly, the unselected leaf at sxas_x^a has distance two from the selected leaf of its forcing pair, while every other vertex outside S0S_0 with the same distance vector to XX has distance at least four. This also resolves all pairs involving a local forcing leaf.

A rail vertex uhau_h^a can share its distance vector to XX with a remaining vertex only if that vertex is uhbu_h^b in another tail or, when h=1h=1, the unselected leaf at pp. The selected leaf f^qb\widehat{f}_q^b has distance h+2h+2 from uhau_h^a and distance h+3h+3 from each of these other vertices, so it distinguishes them. We argue symmetrically with f^pa\widehat{f}_p^a for the vertices vhav_h^a. The boundary vertices and the two remaining boundary leaves have distinct distance vectors to XX from one another. The only pairs left are therefore markers at the same level in different tails.

These marker pairs are indeed unresolved: the selected boundary leaves have distance h+1h+1 from every marker at level hh, and all selected local leaves have distance h+2h+2 by Equation (1).

The reduction

We reduce from Vertex Cover, which is NP-complete [18 Problem GT1]. Let FF be an input graph with nn vertices and mm edges, and let tt be the requested cover size. We assign every edge ee a distinct level λ(e)∈{2,…,m+1}\lambda(e) \in\{2,\ldots,m+1\}. For each vertex a∈V(F)a \in V(F), let DaD_a be the set of levels assigned to edges incident with aa. We apply the construction of § 3 with these sets and with L=m+2L=m+2, denote the resulting graph by HFH_F, and set K=2n+2+tK=2n+2+t. Each edge abab thus gives two markers at its level, one in each endpoint tail.

Figure 3 illustrates the reduction for the cycle F=C4F=C_4 on vertices 1,2,3,41,2,3,4, with edge levels λ(12)=2\lambda(12)=2, λ(23)=3\lambda(23)=3, λ(34)=4\lambda(34)=4, and λ(41)=5\lambda(41)=5. Here L=6L=6, and the first tail is the one shown in Figure 2b. The vertex cover C={1,3}C=\{1,3\} gives the displayed resolving set: one leaf from each of the ten forcing pairs, together with u11u_1^1 and u13u_1^3.

The graph $H_{C_4}$ and the resolving set arising from $C=\{1,3\}$

Figure 3. The graph HC4H_{C_4} and the resolving set arising from C={1,3}C=\{1,3\}, shown in blue. Red diamonds are markers labeled by their levels; the two markers at each level represent one input edge. Superscripts identifying the tails are omitted within the drawing. Blue and purple attachment edges lead to pp and qq, respectively.

The boundary and its four leaves contribute six vertices. Each tail has 2L2L rail vertices, eight additional vertices at its beginning, and one marker for every incident input edge. Since every input edge contributes two markers, the total number of vertices is

∣V(HF)∣=6+n(2L+8)+2m=6+2n(m+6)+2m.|V(H_F)| = 6+n(2L+8)+2m = 6+2n(m+6)+2m.

We can construct the graph and the decomposition described below in O(n(m+1))O(n(m+1)) time.

The following identity proves the correctness of the reduction. Recall that dim⁡(HF)\dim(H_F) is the minimum size of a resolving set of HFH_F, and τ(F)\tau(F) is the minimum size of a vertex cover of FF.

Theorem 4.1. For every input graph FF on nn vertices,

dim⁡(HF)=2n+2+τ(F).\dim(H_F)=2n+2+\tau(F).

In particular, FF has a vertex cover of size at most tt if and only if dim⁡(HF)≤K\dim(H_F)\le K.

Proof. We first extract a vertex cover from a resolving set SS of HFH_F. It contains at least one leaf from each forcing pair, and hence at least 2n+22n+2 forcing leaves. For an edge abab of FF, consider its two markers cah,cbhc_a^h,c_b^h, where h=λ(ab)h=\lambda(ab). Their distance vectors to XX agree, so no vertex outside Ta∪TbT_a\cup T_b distinguishes them by Lemma 3.1. Nor does any forcing leaf distinguish them, by Equation (1) and the distances from the boundary leaves. Consequently, SS must contain a vertex of Ta∪TbT_a\cup T_b that is not a forcing leaf. We take all vertices a∈V(F)a\in V(F) whose tails contain such a landmark. They form a vertex cover of size at most ∣S∣−(2n+2)|S|-(2n+2), since the tails are disjoint. It follows that ∣S∣≥2n+2+τ(F)|S|\ge2n+2+\tau(F).

Conversely, let CC be a minimum vertex cover of FF. We choose one leaf from each forcing pair and add u1au_1^a for every a∈Ca\in C. By Lemma 3.3, we only need to resolve pairs of markers at the same level. Each such pair represents an edge abab of FF, and at least one endpoint, say aa, belongs to CC. Following the uu-rail inside TaT_a, we obtain

dist⁡(u1a,cah)≤h−1<h+1=dist⁡(u1a,cbh),\operatorname{dist}(u_1^a,c_a^h)\le h-1<h+1=\operatorname{dist}(u_1^a,c_b^h),

where the last equality follows from Lemma 3.1. Thus the additional landmarks resolve every remaining pair. We have chosen 2n+2+τ(F)2n+2+\tau(F) landmarks in total, which proves the reverse inequality.

Structural properties of the construction

We now verify the structural properties required in Theorem 1.1. The main point is to understand the graph at the beginning of a tail, the ladders and forcing leaves can then be attached along edges or single vertices.

Lemma 5.1. For every input graph FF, HFH_F is planar and satisfies

tw⁡(HF)=ctw⁡(HF)=3,tl⁡(HF)=2,γiso(HF)=4.\operatorname{tw}(H_F)=\operatorname{ctw}(H_F)=3,\qquad\operatorname{tl}(H_F)=2,\qquad\gamma_{\mathrm{iso}}(H_F)=4.

Every induced cycle has length at most four. A bag-connected tree decomposition of width three whose bags have induced diameter at most two can be constructed in O(∣V(HF)∣)O(|V(H_F)|) time.

Proof. We construct a bag-connected tree decomposition as follows. We take X={p,q}X=\{p,q\} as the root bag and attach the bags {p,p0,p1}\{p,p^0,p^1\} and {q,q0,q1}\{q,q^0,q^1\} to it. For each tail TaT_a, we attach the bag Ia={p,q,u1a,v1a}I_a=\{p,q,u_1^a,v_1^a\} to the root. From IaI_a, we cover the local forcing vertices and their leaves by the two paths of bags

Ia−{x,u1a,v1a,wxa}−{x,wxa,sxa}−{sxa,f0a,fx,1a},x∈{p,q}.I_a-\{x,u_1^a,v_1^a,w_x^a\}-\{x,w_x^a,s_x^a\}-\{s_x^a,f_0^a,f_{x,1}^a\},\qquad x\in\{p,q\}.

We cover the ladder by a further path from IaI_a, namely

Ia−P2a−Q2a−⋯−PLa−QLa,I_a-P_2^a-Q_2^a-\cdots-P_L^a-Q_L^a,

where

Pha={uh−1a,vh−1a,uha},Qha={vh−1a,uha,vha}.P_h^a=\{u_{h-1}^a,v_{h-1}^a,u_h^a\},\qquad Q_h^a=\{v_{h-1}^a,u_h^a,v_h^a\}.

Whenever h∈Dah\in D_a, we attach the marker bag {uh−1a,vh−1a,cha}\{u_{h-1}^a,v_{h-1}^a,c_h^a\} at PhaP_h^a. Every edge is covered, and the bags containing any fixed vertex form a subtree: boundary vertices occur through the root, rail vertices in consecutive ladder bags and their incident attachments, and the remaining vertices along their local paths of bags. Every bag has at most four vertices and induces a connected graph of diameter at most two, proving ctw⁡(HF)≤3\operatorname{ctw}(H_F)\le3 and tl⁡(HF)≤2\operatorname{tl}(H_F)\le2. To obtain the reverse bound on treewidth, we contract pwpap w_p^a and qwqaq w_q^a at the beginning of any tail. The two contracted vertices together with u1a,v1au_1^a,v_1^a form a K4K_4. Hence

3≤tw⁡(HF)≤ctw⁡(HF)≤3.3\le\operatorname{tw}(H_F)\le\operatorname{ctw}(H_F)\le3.

For planarity and the bound on induced cycles, we consider the entrance graph on p,q,u1,v1,wp,wqp,q,u_1,v_1,w_p,w_q, omitting the superscript aa. As shown in Figure 2a, it is obtained from K4K_4 on p,q,u1,v1p,q,u_1,v_1 by subdividing the two opposite edges pv1pv_1 and qu1qu_1 once. In particular, it is planar. We obtain the whole graph by gluing entrance graphs along pqpq, ladder cells and marker triangles along rung edges, and the triangles xwxsxxw_xs_x along xwxxw_x, before adding the pendant edges. Each piece is planar, and gluing along an edge or a vertex preserves planarity. Thus HFH_F is planar.

The entrance graph is bipartite, with parts {p,v1,wq}\{p,v_1,w_q\} and {q,u1,wp}\{q,u_1,w_p\}, and has six vertices and eight edges. An induced cycle longer than four would therefore have to use all six vertices, but the remaining two edges would then be chords. Hence every induced cycle in the entrance graph has length at most four. An induced cycle of length at least four cannot cross a clique along which two graphs are glued: two vertices of that clique would give a chord, or a single vertex would disconnect the cycle. Every induced cycle of HFH_F therefore lies in an entrance graph, a ladder cell, or one of the attached triangles. This proves the bound of four and hence γiso(HF)≤4\gamma_{\mathrm{iso}}(H_F)\le4. A ladder cell is an induced, and therefore isometric, four-cycle, so equality holds. Finally, a graph has tree-length at most one exactly when it is chordal, whereas HFH_F contains an induced four-cycle. Together with the decomposition above, this gives tl⁡(HF)=2\operatorname{tl}(H_F)=2.

Lemma 5.2. Every graph in the tail construction has a path decomposition of width at most four. The decomposition can be constructed in linear time and the union of every initial sequence of bags induces a connected graph.

Proof. We keep pp and qq in every bag and process the tails one after another. We start with {p,q}\{p,q\}, followed by one bag for each of the four boundary leaves, containing that leaf together with p,qp,q.

For a tail aa, we use the following sequence of sets, adding p,qp,q to each of them. We omit the superscript aa to keep the notation short.

{sp,fp,0},{sp,fp,1},{sp,wp},{wp,v1},\{s_p,f_{p,0}\},\quad\{s_p,f_{p,1}\},\quad\{s_p,w_p\},\quad\{w_p,v_1\},
{v1,sq,fq,0},{v1,sq,fq,1},{v1,sq,wq},{v1,wq,u1}.\{v_1,s_q,f_{q,0}\},\quad\{v_1,s_q,f_{q,1}\},\quad\{v_1,s_q,w_q\},\quad\{v_1,w_q,u_1\}.

These bags cover the edges at the beginning of the tail, and the last one contains both ends of the first rung. For h=2,…,Lh=2,\ldots,L, we continue with the sets

{uh−1,vh−1,uh},{vh−1,uh,vh}.\{u_{h-1},v_{h-1},u_h\},\quad\{v_{h-1},u_h,v_h\}.

again adding p,qp,q. If h∈Dah\in D_a, we insert the marker bag immediately before these two bags:

{p,q,uh−1,vh−1,ch}.\{p,q,u_{h-1},v_{h-1},c_h\}.

Every edge is covered, every vertex appears in consecutive bags, and every bag has at most five vertices. After the first bag, each new vertex has a path to an earlier vertex using only vertices of the current bag. Thus every initial union of bags induces a connected graph. The construction uses linearly many bags and takes linear time.

Remark: For tree decompositions, bounded treewidth together with a bound on the length of isometric cycles implies bounded bag-connected treewidth [12, 19]. The analogous statement for path decompositions is false. In Lemma 5.2, the union of each initial sequence of bags is connected, but an individual bag need not be: a bag containing p,qp,q and rail vertices far along a tail omits the intervening rail vertices. In fact, our graphs have prefix-connected pathwidth at most four and no induced cycle longer than four, but their bag-connected pathwidth is unbounded. We prove that cpw⁡(HF)≥L\operatorname{cpw}(H_F)\ge L whenever FF has at least three vertices.

Consider any path decomposition B1,…,BtB_1,\ldots,B_t with connected bags. Choose three tails and a bag containing the last rail vertex of each tail; relabel these tails so that uLa∈Biau_L^a\in B_{i_a} for a∈{1,2,3}a\in\{1,2,3\} and i1≤i2≤i3i_1\le i_2\le i_3. Let PP be the path from uL1u_L^1 along its rail to pp and then along the third rail to uL3u_L^3. The bags meeting a connected subgraph form an interval, since the occurrence intervals of adjacent vertices overlap. The bags meeting PP therefore form an interval containing i1i_1 and i3i_3, so Bi2B_{i_2} contains some vertex x∈V(P)x\in V(P) as well as uL2u_L^2. Since PP lies outside T2T_2, every uL2u_L^2–xx path meets {p,q}\{p,q\}. By dHF(uL2)=(L,L+1)d_{H_F}(u_L^2)= (L,L+1), these two vertices have distance at least LL. The connected graph HF[Bi2]H_F[B_{i_2}] must contain a path between them of length at least LL, and hence ∣Bi2∣≥L+1|B_{i_2}|\ge L+1. This proves the lower bound. Since L=∣E(F)∣+2L=|E(F)|+2 can be arbitrarily large, the width-four decomposition with connected initial unions cannot in general be replaced by one of bounded width with connected bags.

Proof of Theorem 1.1. The construction is polynomial, and Theorem 4.1 proves that it is a correct reduction from Vertex Cover. The required structural properties and the two decompositions follow from Lemmas 5.1 and 5.2. Finally, we can verify a proposed resolving set in polynomial time by computing its distance vectors, which proves membership in NP.

Path decompositions with connected bags

We now prove Theorem 1.2, which states that a minimum resolving set of a connected graph GG can be found in time f(cpw⁡(G))∣V(G)∣O(1)f(\operatorname{cpw}(G))|V(G)|^{O(1)} for some computable function ff. Our proof uses the fact that a graph with a path decomposition of small bag diameter lies close to a shortest path. We distinguish two cases according to whether a minimum resolving set contains two distant vertices or is contained in a small ball. The algorithm will use a dominating shortest path and small separators, which can be found without computing a path decomposition with connected bags. Throughout this section, distances and bag diameters are measured in the whole graph.

Distant landmarks

A path is qq-dominating in a graph GG if every vertex of GG is at distance at most qq from it.

Lemma 6.1. If a connected graph has a path decomposition whose bags have diameter at most qq, then it has a qq-dominating shortest path, which can be found in polynomial time.

Proof. We compute an arbitrary shortest path between every pair of vertices and also consider one-vertex paths. Among these paths, we choose one minimizing the maximum distance of a vertex from the path.

To see that one of these paths is qq-dominating, consider a path decomposition B1,…,BtB_1,\ldots,B_t with bags of diameter at most qq. After discarding empty bags, choose a∈B1a \in B_1 and b∈Btb \in B_t. The bags meeting a connected subgraph form an interval. Every aa-bb path therefore meets every bag, since this interval contains both 11 and tt. In particular, the computed shortest path for a,ba,b meets every bag. Every vertex shares a bag with a vertex of this path, so the path is qq-dominating.

Lemma 6.2. Suppose GG has a qq-dominating shortest path. If dist⁡(s,t)>6q\operatorname{dist}(s,t)>6q, then {s,t}\{s,t\} distinguishes every pair u,vu,v with dist⁡(u,v)>6q\operatorname{dist}(u,v)>6q.

Proof. Index the vertices of the shortest path by their distance from one endpoint. For every vertex xx, choose a path vertex within distance qq and denote its index by zxz_x. Because the path is shortest, the triangle inequality gives

∣dist⁡(x,y)−∣zx−zy∣∣≤2q.\left|\operatorname{dist}(x,y)-|z_x-z_y|\right|\le2q.

Suppose u,vu,v are not distinguished by ss, and order their projections so that zu<zvz_u<z_v. Their distance is greater than 6q6q, so zv−zu>4qz_v-z_u>4q. Equality of the two distances from ss implies

∣∣zs−zu∣−∣zs−zv∣∣≤4q.\left||z_s-z_u|-|z_s-z_v|\right|\le4q.

Thus zsz_s lies in the interval of length 4q4q centered at (zu+zv)/2(z_u+z_v)/2. If tt also fails to distinguish u,vu,v, its index lies in the same interval. It follows that dist⁡(s,t)≤∣zs−zt∣+2q≤6q\operatorname{dist}(s,t)\le|z_s-z_t|+2q\le6q, a contradiction.

It follows that, once we have guessed two landmarks at distance greater than 6q6q, only pairs at distance at most 6q6q need further attention. If a minimum resolving set contains no such two landmarks, then it is contained in the ball of radius 6q6q around any of its vertices. We next show how to find a smallest resolving set in each of these two cases.

Resolving nearby pairs

For pairs at bounded distance, we can work with a tree decomposition. We need both its width and its bag diameter to be bounded. The following approximation result shows that such a decomposition can be found efficiently.

Lemma 6.3 ([7]). Given a graph GG with nn vertices and mm edges, we can compute a bag-connected tree decomposition of width O(c2)O(c^2) in time 2O(c2)nO(1)2^{O(c^2)}n^{O(1)}, where c:=ctw⁡(G)c := \operatorname{ctw}(G).

A connected bag of size at most w+1w+1 has diameter at most ww, so this also bounds the bag diameter by O(c2)O(c^2).

Lemma 6.4. Let r,w,ℓr,w,\ell be nonnegative integers. Given a connected graph GG and a tree-decomposition (T,β)(T,\beta) of width at most ww whose bags have diameter at most ℓ\ell in GG, one can find a smallest set distinguishing all pairs of distinct vertices at distance at most rr in time f(w,ℓ,r)(∣V(G)∣+∣V(T)∣)O(1)f(w,\ell,r)(|V(G)|+|V(T)|)^{O(1)}. The same holds if specified vertices are required to belong to the set or forbidden from belonging to it.

Proof. We first compute all distances in GG. These are the distances used in the dynamic program, even when both vertices lie in a part of the graph that has already been processed. We refine the given decomposition into a nice rooted decomposition. Every intermediate bag is a subset of an original bag, so the bounds on width and diameter are preserved. Since GG is connected, adjacent nonredundant bags have nonempty intersection. Refining through these intersections, we may therefore assume that all bags are nonempty and that the leaves have singleton bags.

Consider a node with bag XX, and let VXV_X be the union of the bags in its subtree. We need to remember which pairs at distance at most rr inside VXV_X still require a landmark outside, and which vertices inside VXV_X may form such a pair with a vertex outside. The latter vertices must lie within distance rr of XX, because XX separates the two parts of the graph. For a vertex zz, write

aX(z)=min⁡x∈Xdist⁡(z,x),pX(z)=(dist⁡(z,x)−aX(z):x∈X).a_X(z)=\min_{x\in X}\operatorname{dist}(z,x),\qquad p_X(z)=\bigl(\operatorname{dist}(z,x)-a_X(z):x\in X\bigr).

We call pX(z)p_X(z) the profile of zz at XX. Its coordinates belong to {0,…,ℓ}\{0,\ldots,\ell\}. For a partial solution S⊆VXS\subseteq V_X, we remember S∩XS\cap X and the following three sets.

The set PP consists of the profiles of vertices in SS. It describes how these landmarks distinguish vertices on the other side of XX. For each pair u,v∈VXu,v\in V_X with 0<dist⁡(u,v)≤r0<\operatorname{dist}(u,v)\le r that is not yet distinguished by SS, we keep its two distance vectors to XX, after subtracting the smallest coordinate occurring in either vector. Let DD be the set of these records. Since ∣aX(u)−aX(v)∣≤r|a_X(u)-a_X(v)|\le r, every coordinate of a record belongs to {0,…,r+ℓ}\{0,\ldots,r+\ell\}.

To deal with pairs having one vertex on either side of the bag, for each u∈VXu\in V_X with aX(u)≤ra_X(u)\le r we keep

αu=dX(u),σu={(pX(s),dist⁡(s,u)−aX(s)):s∈S}.\alpha_u=\mathbf{d}_X(u),\qquad\sigma_u=\{(p_X(s),\operatorname{dist}(s,u)-a_X(s)):s\in S\}.

Let CC be the set of these pairs (αu,σu)(\alpha_u,\sigma_u). The vector αu\alpha_u gives the distances of uu to the bag, while σu\sigma_u describes its distances to the chosen landmarks relative to their distances from the bag. Every coordinate of αu\alpha_u is at most r+ℓr+\ell, and the triangle inequality gives

−r≤dist⁡(s,u)−aX(s)≤r+ℓ.-r\le\operatorname{dist}(s,u)-a_X(s)\le r+\ell.

The number of possible records therefore depends only on w,ℓ,rw,\ell,r. We keep them as sets, without multiplicities. For each choice of S∩X,P,D,CS\cap X,P,D,C, the table stores the smallest cardinality of a partial solution with this information.

We verify that this information is sufficient. Suppose first that a vertex vv is introduced. For every previously processed vertex zz, separation by the old bag XX gives

dist⁡(z,v)=min⁡x∈X(dist⁡(z,x)+dist⁡(x,v)).\operatorname{dist}(z,v)=\min_{x\in X}(\operatorname{dist}(z,x)+\operatorname{dist}(x,v)).

Thus the old coordinates determine the new coordinate at vv in every recorded vector. They also show that the distance of an old vertex to the bag does not decrease, so no vertex omitted from CC needs to be added. If a new pair u,vu,v has distance at most rr, then αX(u)≤r\alpha_X(u)\le r and uu is represented in CC. Its distance to vv is determined by αu\alpha_u. An already chosen landmark distinguishes the pair precisely when some (p,δ)∈σu(p,\delta)\in\sigma_u satisfies

δ≠min⁡x∈X(p(x)+dist⁡(x,v)).\delta\ne\min_{x\in X}(p(x)+\operatorname{dist}(x,v)).

This tells us which pairs to add to DD. The information for vv itself is determined by PP, because for a selected vertex ss with old profile pp, the displayed minimum is exactly dist⁡(s,v)−αX(s)\operatorname{dist}(s,v)-\alpha_X(s). We consider both choices for vv. If we select it, the size of the partial solution increases by one. We add its profile to PP and add (pX∪{v}(v),dist⁡(v,u))(p_{X\cup\{v\}}(v),\operatorname{dist}(v,u)) to each σu\sigma_u. These distances are coordinates of the vectors αu\alpha_u. A pair is distinguished by vv if its two coordinates at vv differ, so we delete precisely these records from DD. In particular, all new pairs involving vv are deleted. If the membership of vv is prescribed, we consider only the permitted choice.

Forgetting a vertex only changes the bag; the processed vertices and the chosen landmarks remain the same. We restrict the recorded vectors to the new bag and normalize them again. We discard a pair (α,σ)(\alpha,\sigma) from CC if the minimum coordinate of its restricted α\alpha exceeds rr. If a landmark profile pp loses a coordinate and the minimum of the remaining coordinates is cc, we replace each (p,δ)(p,\delta) by (p−c,δ−c)(p-c,\delta-c), with the deleted coordinate omitted. This accounts for the change in the distance of the landmark from the bag.

At a join node, the two processed parts intersect in their common bag XX. We combine two partial solutions only when they agree on which vertices of XX are selected. Their union has size equal to the sum of their sizes minus the number of selected bag vertices, and its landmark profiles form the union of the two sets PP. A pair recorded by (α,α′)(\alpha,\alpha') in one child is distinguished by a landmark from the other child precisely when one of that child’s profiles pp satisfies

min⁡x∈X(p(x)+α(x))≠min⁡x∈X(p(x)+α′(x)).\min_{x\in X}(p(x)+\alpha(x))\ne\min_{x\in X}(p(x)+\alpha'(x)).

We discard these pairs from the two sets DD.

We must also consider pairs with one vertex in each child. If such a pair has distance at most rr, both vertices lie within distance rr of XX, so their information occurs in the two sets CC. For records (αu,σu)(\alpha_u,\sigma_u) and (αv,σv)(\alpha_v,\sigma_v) from the two children, separation by XX gives distance

h=min⁡x∈X(αu(x)+αv(x)).h=\min_{x\in X}(\alpha_u(x)+\alpha_v(x)).

If 0<h≤r0<h\le r, the pair is distinguished by a selected vertex in the first child precisely when some (p,δ)∈σu(p,\delta)\in\sigma_u has δ≠min⁡x∈X(p(x)+αv(x))\delta\ne\min_{x\in X}(p(x)+\alpha_v(x)), and symmetrically for the second child. If neither test succeeds, we add the jointly normalized pair of vectors to DD. Pairs involving bag vertices may be considered more than once, which does not affect a set of records; the condition h>0h>0 excludes a vertex paired with itself.

For a vertex uu from one child, its distances to landmarks from the other child are again determined by their profiles at XX. We therefore add

(p,min⁡x∈X(p(x)+αu(x)))\left(p,\min_{x\in X}(p(x)+\alpha_u(x))\right)

to σu\sigma_u for each landmark profile pp in the other child. After making these additions to the records from both children, we take their union to obtain CC. The same distance calculations apply when one of the vertices belongs to XX.

At a singleton leaf, the two possible choices can be checked directly, respecting any prescribed membership. The calculations above show inductively that all table entries have the stated meaning. As they depend only on the information stored in the tables, we may always keep a partial solution of smallest size for each entry. At the root, all vertices have been processed, and a partial solution has the required property exactly when DD is empty. The number of entries and the work needed to compute them at each node are bounded by a computable function of w,ℓ,rw,\ell,r. Remembering which entries were combined allows us to recover a smallest set.

Landmarks in a ball

Lemma 6.5. Suppose GG has a path decomposition of width at most qq whose bags have diameter at most qq. Given GG, a vertex cc, and a nonnegative integer RR, one can find a smallest resolving set SS of the whole graph GG satisfying

c∈S⊆NR(c)c \in S \subseteq N_R(c)

in time f(q,R)∣V(G)∣O(1)f(q,R)|V(G)|^{O(1)}, or determine that no such set exists.

Proof. Put A=NR(c)A=N_R(c) and U=NR+q(c)U=N_{R+q}(c). We first show that a small set of vertices in UU separates the possible landmarks from the vertices outside UU. Consider a path decomposition as in the statement. Since AA induces a connected graph, the bags meeting AA form an interval. Each of these bags meets AA and has diameter at most qq, so their union is contained in UU. Taking the first and last bags of the interval gives a set Z⊆UZ \subseteq U of size at most 2q+22q+2 meeting every path from AA to V(G)∖UV(G) \setminus U. Notice that ZZ may contain vertices of AA.

We find a smallest such set ZZ by a vertex-capacitated minimum cut, giving capacity one to vertices of UU and infinite capacity to other vertices. In the usual vertex-splitting construction, the source is joined to the incoming copy of each vertex of AA, and the outgoing copies of vertices outside UU are joined to the sink. Thus vertices of AA are themselves allowed in the cut. Let CC consist of ZZ and all components of G−ZG-Z meeting A∖ZA \setminus Z. Then

A⊆C⊆U,∣Z∣≤2q+2,A \subseteq C \subseteq U,\qquad|Z| \leq2q+2,

and every path from a vertex of AA to a vertex outside CC meets ZZ. If ZZ is empty, connectedness of GG implies C=V(G)C=V(G).

We will express the conditions c∈S⊆Ac \in S \subseteq A and that SS resolves GG by a monadic second-order formula whose length, and whose number of additional unary colors, depend only on q,Rq,R. Since GG has treewidth at most qq, monadic second-order optimization will then find a smallest such set. We mark AA, CC, and cc by unary colors. Every vertex of AA has distance at most M=2R+qM=2R+q from every vertex of CC. We can therefore express that SS distinguishes all pairs in CC using the formulas for distances 0,…,M0,\ldots,M.

It remains to describe the effect of the vertices outside CC, whose distances from the landmarks may be arbitrarily large. If there are such vertices, then ZZ is nonempty. For each of them write

δv=min⁡z∈Zdist⁡G(v,z),αv(z)=dist⁡G(v,z)−δv.\delta_v=\min_{z\in Z}\operatorname{dist}_G(v,z),\qquad\alpha_v(z)=\operatorname{dist}_G(v,z)-\delta_v.

The diameter of ZZ is at most 2R+2q2R+2q, so the coordinates of αv\alpha_v belong to {0,…,2R+2q}\{0,\ldots,2R+2q\}. As ∣Z∣≤2q+2|Z|\leq2q+2, the number of possible profiles depends only on q,Rq,R. For s∈As\in A and a profile α\alpha, put

fα(s)=min⁡z∈Z(dist⁡G(s,z)+α(z)).(2)f_\alpha(s)=\min_{z\in Z}\bigl(\operatorname{dist}_G(s,z)+\alpha(z)\bigr). \tag*{(2)}

Every path from ss to an outside vertex vv meets ZZ, and hence

dist⁡G(s,v)=δv+fαv(s).\operatorname{dist}_{G}(s,v)=\delta_v+f_{\alpha_v}(s).

Observe that 0≤fα(s)≤M0 \le f_{\alpha}(s) \le M. Indeed, α\alpha has a zero coordinate, and the distance from ss to the corresponding vertex of ZZ is at most MM. We use unary colors to record the value of fα(s)f_{\alpha}(s) for each s∈As \in A and each profile α\alpha that occurs. These colors can be computed from the distance matrix of GG, and their number depends only on q,Rq,R.

Consider first x∈Cx \in C and v∉Cv \notin C. If δv>M\delta_v > M, every vertex of AA distinguishes the pair, because its distance to xx is at most MM. Otherwise, the condition that a landmark distinguish xx and vv depends on vv only through αv\alpha_v and δv∈{0,…,M}\delta_v \in\{0,\ldots,M\}. For each combination that occurs, we require that for every x∈Cx \in C there be an s∈Ss \in S with

dist⁡G(s,x)≠δv+fαv(s).\operatorname{dist}_{G}(s,x) \ne\delta_v+f_{\alpha_v}(s).

The number of these requirements depends only on q,Rq,R, and each is expressible using the colors above and bounded-distance formulas.

Now consider two distinct vertices v,wv,w outside CC. If ∣δv−δw∣>M|\delta_v-\delta_w|>M, every vertex of AA distinguishes them. Otherwise, their two profiles and the difference Δ=δw−δv∈{−M,…,M}\Delta=\delta_w-\delta_v \in\{-M,\ldots,M\} determine which vertices of AA distinguish them: we need an s∈Ss \in S for which

fαv(s)−fαw(s)≠Δ.f_{\alpha_v}(s)-f_{\alpha_w}(s) \ne\Delta.

For each combination realized by a pair of distinct outside vertices, we mark the vertices of AA satisfying this inequality and require SS to contain one of them. If no vertex of AA satisfies the inequality, no resolving set contained in AA exists. Again, the number of color classes is bounded in terms of q,Rq,R.

We have now expressed that every pair of vertices of GG is distinguished by SS. The formula has length bounded in terms of q,Rq,R, as does the number of colors, and all colors and realized combinations can be computed in polynomial time. Unary colors do not affect treewidth. We can therefore use Bodlaender’s algorithm [4] to find a tree decomposition and apply monadic second-order optimization [1] to find a smallest satisfying set in the claimed running time. □

Putting the algorithm together

Proof of Theorem 1.2. A one-vertex graph has the empty resolving set, so suppose ∣V(G)∣≥2|V(G)| \ge2 and let q=cpw⁡(G)≥1q=\operatorname{cpw}(G) \ge1. Since ctw⁡(G)≤q\operatorname{ctw}(G) \le q, Lemma 6.3 gives a tree decomposition whose width and bag diameter are both O(q2)O(q^2). By Lemma 6.1, we can also find a qq-dominating shortest path.

For each pair s,ts,t with dist⁡(s,t)>6q\operatorname{dist}(s,t)>6q, we apply Lemma 6.4 with r=6qr=6q, requiring both ss and tt to be selected. The resulting set resolves all nearby pairs by construction, and all other pairs by Lemma 6.2. For every vertex cc, we also apply Lemma 6.5 with R=6qR=6q. Among all sets found in this way, we return one of smallest size.

Every set considered for the output is a resolving set. Conversely, let SS be a minimum resolving set. If it contains two vertices farther than 6q6q apart, the computation for this pair returns a set of size at most ∣S∣|S|. If it does not, choose any c∈Sc \in S; the set is nonempty because the graph has at least two vertices. Then S⊆N6q(c)S \subseteq N_{6q}(c), and the computation for cc returns a set of size at most ∣S∣|S|. Hence the algorithm finds a minimum resolving set. There are at most ∣V(G)∣2|V(G)|^2 computations, each taking f(q)∣V(G)∣O(1)f(q)|V(G)|^{O(1)} time.

Finally, the algorithm need not know qq in advance. The bag-connected tree decomposition is computed once, independently of qq, and reused throughout, including for the monadic second-order optimization. We try q=1,2,…q=1,2,\ldots until we have found the structures used in the proof. We check that the shortest path found is qq-dominating and that the minimum cut for every ball of radius 6q6q has size at most 2q+22q + 2. If one of these conditions fails, we again increase qq. Once they all hold, the correctness proof applies: it only uses these structures, not a path decomposition witnessing cpw⁡(G)≤q\operatorname{cpw}(G) \le q. All conditions hold by q=cpw⁡(G)q = \operatorname{cpw}(G), and the computed decomposition has width and bag diameter O(cpw⁡(G)2)O(\operatorname{cpw}(G)^2), so the total running time has the required form.

In particular, bounded width with connected bags gives polynomial-time solvability for path decompositions, whereas Theorem 1.1 rules it out for tree decompositions unless P = NP. The connected-prefix requirement is different: Lemma 5.2 already gives hardness at width four under that convention.

Acknowledgements

We thank Florent Foucaud, Oscar Defrain, Prafullakumar Tale, Mathieu Mari for many interesting discussions on the topic. We acknowledge the organizers and participants of the June 2026 GRALMECO-GRAPHMETRIX Workshop in Aydat near Clermont-Ferrand, France, where many interesting discussions were carried out.

References

  1. [1]Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308–340, 1991. doi: 10.1016/0196-6774(91)90006-K.DOI
  2. [2]Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, and M. S. Ramanujan. Metric dimension of bounded tree-length graphs. SIAM Journal on Discrete Mathematics, 31(2):1217–1243, 2017. doi: 10.1137/16M1057383.DOI
  3. [3]Tristan Benoit. Metric dimension is NP-complete on graphs of treewidth two. arXiv:2610.21133v3, 2026. Preprint, version 3.arxiv.org/abs/2610.21133
  4. [4]Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996. doi: 10.1137/S0097539793251219.DOI
  5. [5]Édouard Bonnet and Nidhi Purohit. Metric dimension parameterized by treewidth. Algorithmica, 83(8):2606–2633, 2021. doi: 10.1007/s00453-021-00808-9.DOI
  6. [6]Nicolas Bousquet, Quentin Deschamps, and Aline Parreau. Metric dimension parameterized by treewidth in chordal graphs. In Daniël Paulusma and Bernard Ries, editors, Graph-Theoretic Concepts in Computer Science – WG 2023, volume 14093 of Lecture Notes in Computer Science, pages 130–142. Springer, 2023. doi: 10.1007/978-3-031-43380-1_10.DOI
  7. [7]Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Sebastian Ordyniak, and Prafullkumar Tale. Connected tree decomposition(s): Parameterized complexity and algorithmic applications. Manuscript.
  8. [8]Dibyayan Chakraborty, Sebastian Ordyniak, and Sebastian Siebertz. Model checking for metric extensions of monadic second-order logic. arXiv:2610.41974, 2026.arxiv.org/abs/2610.41974
  9. [9]Antoine Dailly, Florent Foucaud, and Anni Hakanen. Algorithms and hardness for Metric Dimension on digraphs. Journal of Computer and System Sciences, 158:103776, 2026. doi: 10.1016/j.jcss.2026.103776.DOI
  10. [10]Dariusz Dereniowski. From pathwidth to connected pathwidth. SIAM Journal on Discrete Mathematics, 26(4):1709–1732, 2012. doi: 10.1137/110826424.DOI
  11. [11]Josep Díaz, Olli Pottonen, Maria J. Serna, and Erik Jan van Leeuwen. Complexity of metric dimension on planar graphs. Journal of Computer and System Sciences, 83(1):132–158, 2017. doi: 10.1016/j.jcss.2016.06.006.DOI
  12. [12]Reinhard Diestel and Malte Müller. Connected tree-width. Combinatorica, 38(2):381–398, 2018. doi: 10.1007/s00493-016-3516-5.DOI
  13. [13]Yon Dourisboure and Cyril Gavoille. Tree-decompositions with bags of small diameter. Discrete Mathematics, 307(16):2008–2029, 2007. doi: 10.1016/j.disc.2005.12.060.DOI
  14. [14]Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov. Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity. Algorithmica, 78(3):914–944, 2017. doi: 10.1007/s00453-016-0184-1.DOI
  15. [15]Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP Can Admit Double-Exponential Lower Bounds When Parameterized by Treewidth or Vertex Cover. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 66:1–66:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi: 10.4230/LIPIcs.ICALP.2024.66.DOI
  16. [16]Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension and Geodetic Set Parameterized by Vertex Cover. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), volume 327 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi: 10.4230/LIPIcs.STACS.2025.33.DOI
  17. [17]Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters. SIAM Journal on Discrete Mathematics, 37(4):2241–2264, 2023. doi: 10.1137/22M1510911.DOI
  18. [18]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.
  19. [19]Matthias Hamann and Daniel Weißauer. Bounding connected tree-width. SIAM Journal on Discrete Mathematics, 30(3):1391–1400, 2016. doi: 10.1137/15M1044618.DOI
  20. [20]Frank Harary and Robert A. Melter. On the metric dimension of a graph. Ars Combinatoria, 2:191–195, 1976.
  21. [21]Sepp Hartung and André Nichterlein. On the parameterized and approximation hardness of metric dimension. In Proceedings of the 28th Conference on Computational Complexity, pages 266–276. IEEE Computer Society, 2013. doi: 10.1109/CCC.2013.36.DOI
  22. [22]Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Landmarks in graphs. Discrete Applied Mathematics, 70(3):217–229, 1996. doi: 10.1016/0166-218X(95)00106-2.DOI
  23. [23]Shaohua Li and Marcin Pilipczuk. Hardness of metric dimension in graphs of constant treewidth. Algorithmica, 84(11):3110–3155, 2022. doi: 10.1007/s00453-022-01005-y.DOI
  24. [24]Peter J. Slater. Leaves of trees. Congressus Numerantium, 14:549–559, 1975. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing.
  25. [25]Prafullkumar Tale. On the Hardness of Strong Metric Dimension. In 21st International Symposium on Parameterized and Exact Computation (IPEC 2026), Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. URL https://arxiv.org/abs/2608.06747. Full version available as arXiv:2608.06747.

Paper details

vlnc:W_wm6u4fna
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents