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 . 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 be a finite, simple, connected graph. A set is a resolving set if, for every two distinct vertices , there is a vertex with . The metric dimension is the minimum size of a resolving set. This notion was introduced independently by Slater and by Harary and Melter [20, 26]. In the decision problem Metric Dimension, we are given a graph and an integer and ask whether .
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, 24]. 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 [25]. See [9, 14, 15, 16, 17, 27] 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 of a graph is the minimum width of such a decomposition [12, 19, 22, 23]. A connected bag of size at most has diameter at most , 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 NP-complete on graphs satisfying all of the following properties:
is planar.
.
has no induced cycle of length greater than four.
admits a bag-connected tree decomposition of width three in which every bag has induced diameter at most two.
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 has running time for computable functions . Such an algorithm runs in polynomial time when . Hence Theorem 1.1 rules out an XP algorithm unless P = 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 of a graph 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 .
Theorem 1.2. There is an algorithm that finds a minimum resolving set of a connected graph in time , where is a computable function.
Preliminaries
We write for the distance between vertices of a connected graph , and omit the subscript when the graph is clear from the context. For , we write for the subgraph induced by and for . The external vertex boundary of is
We omit the subscript when the ambient graph is clear, and use the same notation for a subgraph and its vertex set.
A set is a resolving set if, for every two distinct vertices , there is a vertex with . A vertex that belongs to a resolving set will also be called a landmark. The metric dimension 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 is a set containing at least one endpoint of every edge. We write for the minimum size of a vertex cover of . In Vertex Cover, the input is a graph and an integer , and the question is whether .
A tree decomposition of consists of a tree and bags , for , such that every edge has both endpoints in some bag and, for every vertex , the nodes whose bags contain form a nonempty connected subtree of . Its width is , and the treewidth is the minimum possible width. We call the decomposition bag-connected if is connected for every . The bag-connected treewidth is the minimum width of a bag-connected tree decomposition of . In particular, .
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 has one child and satisfies for some . A forget node has one child and satisfies for some . A join node has two children with .
A path decomposition is a tree decomposition whose underlying tree is a path. The bag-connected pathwidth of is the minimum width over all path decompositions where every bag is required to induce a connected graph. Thus . The graph-search version of connected pathwidth, denoted by , instead minimizes the width over path decompositions for which is connected for every . We write for the radius- neighborhood, or ball, around .
The length of a tree decomposition is the maximum of over its bags, where the diameter is measured in the whole graph. The tree-length 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 , 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 levels, where , consists of two vertex-disjoint paths and , together with the edges for . The two paths are its rails, their vertices are rail vertices, and the edges are its rungs. The vertices and their rung are at level . The four-cycles , for , are the ladder cells. We attach the ladder to an edge disjoint from its rails by adding and . A marker at level , for , is an additional vertex whose neighbors are and . 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 , and a marker at level four. The horizontal paths are the rails and the vertical edges are the rungs. The vertices are outside the ladder.
For a nonempty set with a fixed ordering, the distance vector to $X of a vertex is
The following standard lemma expresses distances through a separating set.
Lemma 3.1. Let be a connected graph and let . If is a component of , , and , then
In particular, if lie in different components of and satisfy , then no vertex outside these two components distinguishes them.
Our construction attaches several ladders to the same edge 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 and the leaves attached directly to them. The tails are pairwise disjoint connected subgraphs. All tails in our construction attach to the same boundary . Thus, writing for the constructed graph and for its th tail, we have for every . We call the forcing leaves within a tail local forcing leaves, and the leaves attached directly to boundary leaves. The entrance graph of a tail consists of , the edges , , , , and the paths and , where 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 , so
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 , and let be subsets of . We start with an edge and put . For each index , we attach a ladder with levels to , using the superscript to distinguish its vertices from those of the other ladders. Its rails are and , its rungs are , and its attachment edges are and . For every , we add a marker adjacent to and . 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 and each , we add vertices . We make adjacent to , and adjacent to . The vertices , together with , form the entrance graph of the tail. We then make adjacent to and attach two leaves to it. Thus is a local forcing vertex with forcing pair . Finally, we attach four leaves to and two leaves to . There are no further edges, and we denote the resulting graph by . The tail consists of all vertices introduced for index , including its local forcing leaves but excluding and their leaves. Each tail is a component of and has external boundary $\partial_H T_a=X. Figure 2 shows the entrance graph and a complete example of a tail.

Figure 2. The entrance graph and a complete tail. In (a), deleting , and their leaves gives with two opposite edges subdivided once. In (b), , and their leaves are shared with all other tails. Blue leaves indicate one choice from each depicted forcing pair; the blue vertex is an additional landmark used in the reduction. Red diamonds are markers.
To see the role of these vertices, observe that has distance two from both and , although it is closer to than to . It therefore distinguishes the -rail of its own tail from the -rail of another tail. The vertex does the same for the -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 of the vertices in are as follows, with coordinates ordered as .
| Vertex | Distance vector $\mathbf{d}_X(v) |
| , | , |
| , | , |
| , | , |
| , | |
| , | |
| , | , |
Table 1.
For every local forcing vertex and every marker , regardless of whether , we have
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, has distance from and needs one extra step to reach ; the distances for are symmetric. The paths through give no shorter route to either end of the first rung, and hence do not change these distances. As is adjacent to both rail vertices at level , its distance from each boundary vertex is . 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, has distance two from both first rail vertices, and hence distance from both rail vertices at level . Its distance to is therefore . For a marker in another tail, we obtain the same value from Lemma 3.1: has distance one from the boundary, and . 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 forcing pairs, and let be the resulting set. The pairs not resolved by 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 . For each , let be the selected leaf adjacent to . For every , we have . The two selected boundary leaves therefore distinguish any two vertices outside with different distance vectors to . We are left with pairs having the same distance vector to , which we examine using Lemma 3.2.
Let be the selected leaf at . Its distances to and are one and two, respectively. Every other vertex outside with their common distance vector to is at distance at least three from . Thus all pairs involving an -vertex or a -vertex are resolved. Similarly, the unselected leaf at has distance two from the selected leaf of its forcing pair, while every other vertex outside with the same distance vector to has distance at least four. This also resolves all pairs involving a local forcing leaf.
A rail vertex can share its distance vector to with a remaining vertex only if that vertex is in another tail or, when , the unselected leaf at . The selected leaf has distance from and distance from each of these other vertices, so it distinguishes them. We argue symmetrically with for the vertices . The boundary vertices and the two remaining boundary leaves have distinct distance vectors to 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 from every marker at level , and all selected local leaves have distance by Equation (1).
The reduction
We reduce from Vertex Cover, which is NP-complete [18 Problem GT1]. Let be an input graph with vertices and edges, and let be the requested cover size. We assign every edge a distinct level . For each vertex , let be the set of levels assigned to edges incident with . We apply the construction of § 3 with these sets and with , denote the resulting graph by , and set . Each edge thus gives two markers at its level, one in each endpoint tail.
Figure 3 illustrates the reduction for the cycle on vertices , with edge levels , , , and . Here , and the first tail is the one shown in Figure 2b. The vertex cover gives the displayed resolving set: one leaf from each of the ten forcing pairs, together with and .

Figure 3. The graph and the resolving set arising from , 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 and , respectively.
The boundary and its four leaves contribute six vertices. Each tail has 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
We can construct the graph and the decomposition described below in time.
The following identity proves the correctness of the reduction. Recall that is the minimum size of a resolving set of , and is the minimum size of a vertex cover of .
Theorem 4.1. For every input graph on vertices,
In particular, has a vertex cover of size at most if and only if .
Proof. We first extract a vertex cover from a resolving set of . It contains at least one leaf from each forcing pair, and hence at least forcing leaves. For an edge of , consider its two markers , where . Their distance vectors to agree, so no vertex outside distinguishes them by Lemma 3.1. Nor does any forcing leaf distinguish them, by Equation (1) and the distances from the boundary leaves. Consequently, must contain a vertex of that is not a forcing leaf. We take all vertices whose tails contain such a landmark. They form a vertex cover of size at most , since the tails are disjoint. It follows that .
Conversely, let be a minimum vertex cover of . We choose one leaf from each forcing pair and add for every . By Lemma 3.3, we only need to resolve pairs of markers at the same level. Each such pair represents an edge of , and at least one endpoint, say , belongs to . Following the -rail inside , we obtain
where the last equality follows from Lemma 3.1. Thus the additional landmarks resolve every remaining pair. We have chosen 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 , is planar and satisfies
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 time.
Proof. We construct a bag-connected tree decomposition as follows. We take as the root bag and attach the bags and to it. For each tail , we attach the bag to the root. From , we cover the local forcing vertices and their leaves by the two paths of bags
We cover the ladder by a further path from , namely
where
Whenever , we attach the marker bag at .
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 and . To obtain the reverse bound on treewidth, we contract and at the beginning of any tail. The two contracted vertices together with form a . Hence
For planarity and the bound on induced cycles, we consider the entrance graph on , omitting the superscript . As shown in Figure 2a, it is obtained from on by subdividing the two opposite edges and once. In particular, it is planar. We obtain the whole graph by gluing entrance graphs along , ladder cells and marker triangles along rung edges, and the triangles along , before adding the pendant edges. Each piece is planar, and gluing along an edge or a vertex preserves planarity. Thus is planar.
The entrance graph is bipartite, with parts and , 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 therefore lies in an entrance graph, a ladder cell, or one of the attached triangles. This proves the bound of four and hence . 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 contains an induced four-cycle. Together with the decomposition above, this gives .
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 and in every bag and process the tails one after another. We start with , followed by one bag for each of the four boundary leaves, containing that leaf together with .
For a tail , we use the following sequence of sets, adding to each of them. We omit the superscript to keep the notation short.
These bags cover the edges at the beginning of the tail, and the last one contains both ends of the first rung. For , we continue with the sets
again adding . If , we insert the marker bag immediately before these two bags:
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 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 whenever has at least three vertices.
Consider any path decomposition with connected bags. Choose three tails and a bag containing the last rail vertex of each tail; relabel these tails so that for and . Let be the path from along its rail to and then along the third rail to . The bags meeting a connected subgraph form an interval, since the occurrence intervals of adjacent vertices overlap. The bags meeting therefore form an interval containing and , so contains some vertex as well as . Since lies outside , every – path meets . By , these two vertices have distance at least . The connected graph must contain a path between them of length at least , and hence . This proves the lower bound. Since 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 can be found in time for some computable function . 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 -dominating in a graph if every vertex of is at distance at most from it.
Lemma 6.1. If a connected graph has a path decomposition whose bags have diameter at most , then it has a -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 -dominating, consider a path decomposition with bags of diameter at most . After discarding empty bags, choose and . The bags meeting a connected subgraph form an interval. Every - path therefore meets every bag, since this interval contains both 1 and . In particular, the computed shortest path for meets every bag. Every vertex shares a bag with a vertex of this path, so the path is -dominating.
Lemma 6.2. Suppose has a -dominating shortest path. If , then distinguishes every pair with .
Proof. Index the vertices of the shortest path by their distance from one endpoint. For every vertex , choose a path vertex within distance and denote its index by . Because the path is shortest, the triangle inequality gives
Suppose are not distinguished by , and order their projections so that . Their distance is greater than , so . Equality of the two distances from implies
Thus lies in the interval of length centered at . If also fails to distinguish , its index lies in the same interval. It follows that , a contradiction.
It follows that, once we have guessed two landmarks at distance greater than , only pairs at distance at most need further attention. If a minimum resolving set contains no such two landmarks, then it is contained in the ball of radius 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 with vertices and edges, we can compute a bag-connected tree decomposition of width in time , where .
A connected bag of size at most has diameter at most , so this also bounds the bag diameter by .
Lemma 6.4. Let be nonnegative integers. Given a connected graph and a tree-decomposition of width at most whose bags have diameter at most in , one can find a smallest set distinguishing all pairs of distinct vertices at distance at most in time . 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 . 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 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 , and let be the union of the bags in its subtree. We need to remember which pairs at distance at most inside still require a landmark outside, and which vertices inside may form such a pair with a vertex outside. The latter vertices must lie within distance of , because separates the two parts of the graph. For a vertex , write
We call the profile of at . Its coordinates belong to . For a partial solution , we remember and the following three sets.
The set consists of the profiles of vertices in . It describes how these landmarks distinguish vertices on the other side of . For each pair with that is not yet distinguished by , we keep its two distance vectors to , after subtracting the smallest coordinate occurring in either vector. Let be the set of these records. Since , every coordinate of a record belongs to .
To deal with pairs having one vertex on either side of the bag, for each with we keep
Let be the set of these pairs . The vector gives the distances of to the bag, while describes its distances to the chosen landmarks relative to their distances from the bag. Every coordinate of is at most , and the triangle inequality gives
The number of possible records therefore depends only on . We keep them as sets, without multiplicities. For each choice of , 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 is introduced. For every previously processed vertex , separation by the old bag gives
Thus the old coordinates determine the new coordinate at 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 needs to be added. If a new pair has distance at most , then and is represented in . Its distance to is determined by . An already chosen landmark distinguishes the pair precisely when some satisfies
This tells us which pairs to add to . The information for itself is determined by , because for a selected vertex with old profile , the displayed minimum is exactly . We consider both choices for . If we select it, the size of the partial solution increases by one. We add its profile to and add to each . These distances are coordinates of the vectors . A pair is distinguished by if its two coordinates at differ, so we delete precisely these records from . In particular, all new pairs involving are deleted. If the membership of 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 from if the minimum coordinate of its restricted exceeds . If a landmark profile loses a coordinate and the minimum of the remaining coordinates is , we replace each by , 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 . We combine two partial solutions only when they agree on which vertices of 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 . A pair recorded by in one child is distinguished by a landmark from the other child precisely when one of that child’s profiles satisfies
We discard these pairs from the two sets .
We must also consider pairs with one vertex in each child. If such a pair has distance at most , both vertices lie within distance of , so their information occurs in the two sets . For records and from the two children, separation by gives distance
If , the pair is distinguished by a selected vertex in the first child precisely when some has , and symmetrically for the second child. If neither test succeeds, we add the jointly normalized pair of vectors to . Pairs involving bag vertices may be considered more than once, which does not affect a set of records; the condition excludes a vertex paired with itself.
For a vertex from one child, its distances to landmarks from the other child are again determined by their profiles at . We therefore add
to for each landmark profile in the other child. After making these additions to the records from both children, we take their union to obtain . The same distance calculations apply when one of the vertices belongs to .
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 is empty. The number of entries and the work needed to compute them at each node are bounded by a computable function of . Remembering which entries were combined allows us to recover a smallest set.
Landmarks in a ball
Lemma 6.5. Suppose has a path decomposition of width at most whose bags have diameter at most . Given , a vertex , and a nonnegative integer , one can find a smallest resolving set of the whole graph satisfying
in time , or determine that no such set exists.
Proof. Put and . We first show that a small set of vertices in separates the possible landmarks from the vertices outside . Consider a path decomposition as in the statement. Since induces a connected graph, the bags meeting form an interval. Each of these bags meets and has diameter at most , so their union is contained in . Taking the first and last bags of the interval gives a set of size at most meeting every path from to . Notice that may contain vertices of .
We find a smallest such set by a vertex-capacitated minimum cut, giving capacity one to vertices of and infinite capacity to other vertices. In the usual vertex-splitting construction, the source is joined to the incoming copy of each vertex of , and the outgoing copies of vertices outside are joined to the sink. Thus vertices of are themselves allowed in the cut. Let consist of and all components of meeting . Then
and every path from a vertex of to a vertex outside meets . If is empty, connectedness of implies .
We will express the conditions and that resolves by a monadic second-order formula whose length, and whose number of additional unary colors, depend only on . Since has treewidth at most , monadic second-order optimization will then find a smallest such set. We mark , , and by unary colors. Every vertex of has distance at most from every vertex of . We can therefore express that distinguishes all pairs in using the formulas for distances .
It remains to describe the effect of the vertices outside , whose distances from the landmarks may be arbitrarily large. If there are such vertices, then is nonempty. For each of them write
The diameter of is at most , so the coordinates of belong to . As , the number of possible profiles depends only on . For and a profile , put
Every path from to an outside vertex meets , and hence
Observe that . Indeed, has a zero coordinate, and the distance from to the corresponding vertex of is at most . We use unary colors to record the value of for each and each profile that occurs. These colors can be computed from the distance matrix of , and their number depends only on .
Consider first and . If , every vertex of distinguishes the pair, because its distance to is at most . Otherwise, the condition that a landmark distinguish and depends on only through and . For each combination that occurs, we require that for every there be an with
The number of these requirements depends only on , and each is expressible using the colors above and bounded-distance formulas.
Now consider two distinct vertices outside . If , every vertex of distinguishes them. Otherwise, their two profiles and the difference determine which vertices of distinguish them: we need an for which
For each combination realized by a pair of distinct outside vertices, we mark the vertices of satisfying this inequality and require to contain one of them. If no vertex of satisfies the inequality, no resolving set contained in exists. Again, the number of color classes is bounded in terms of .
We have now expressed that every pair of vertices of is distinguished by . The formula has length bounded in terms of , 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 and let . Since , Lemma 6.3 gives a tree decomposition whose width and bag diameter are both . By Lemma 6.1, we can also find a -dominating shortest path.
For each pair with , we apply Lemma 6.4 with , requiring both and to be selected. The resulting set resolves all nearby pairs by construction, and all other pairs by Lemma 6.2. For every vertex , we also apply Lemma 6.5 with . 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 be a minimum resolving set. If it contains two vertices farther than apart, the computation for this pair returns a set of size at most . If it does not, choose any ; the set is nonempty because the graph has at least two vertices. Then , and the computation for returns a set of size at most . Hence the algorithm finds a minimum resolving set. There are at most computations, each taking time.
Finally, the algorithm need not know in advance. The bag-connected tree decomposition is computed once, independently of , and reused throughout, including for the monadic second-order optimization. We try until we have found the structures used in the proof. We check that the shortest path found is -dominating and that the minimum cut for every ball of radius has size at most . If one of these conditions fails, we again increase . Once they all hold, the correctness proof applies: it only uses these structures, not a path decomposition witnessing . All conditions hold by , and the computed decomposition has width and bag diameter , 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]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]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]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]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]É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]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]Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Sebastian Ordyniak, and Prafullakumar Tale. Connected tree decomposition(s): Parameterized complexity and algorithmic applications. Manuscript.
- [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]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]Dariusz Dereniowski. From pathwidth to connected pathwidth. SIAM Journal on Discrete Mathematics, 26(4):1709–1732, 2012. doi: 10.1137/110826424.DOI
- [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]Reinhard Diestel and Malte Müller. Connected tree-width. Combinatorica, 38(2):381–398, 2018. doi: 10.1007/s00493-016-3516-5.DOI
- [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]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.
- [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]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]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]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]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]Frank Harary and Robert A. Melter. On the metric dimension of a graph. Ars Combinatoria, 2:191–195, 1976.
- [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]Philippe Jégou and Cyril Terrieux. Bag-connected tree-width: A new parameter for graph decomposition. In ISAIM, 2014.
- [23]Philippe Jégou and Cyril Terrieux. Combining restarts, nogoods and bag-connected decompositions for solving CSPs. Constraints, 22(2):191–229, 2017. doi: 10.1007/s10601-016-9248-8.DOI
- [24]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
- [25]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
- [26]Peter J. Slater. Leaves of trees. Congressus Numerantium, 14:549–559, 1975. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing.
- [27]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.
