1. Introduction and Problem Formulation
In recent years, there has been an increasing interest in connected p-center and p-median problems where the subgraph induced by the selected set is connected. Yen [1] studied the connected p-center problem on block graphs. Bai et al. [2] considered the connected p-median problem on cactus graphs and showed that the problem can be solved in polynomial time. In this paper we consider the inverse connected p-median problem on block graphs. We shall follow the notations and terminologies given in Kang et al. [3] , Nguyen and Hung [4] . Let
be a finite, connected, undirected graph with vertex set V of order
and edge set E of size
, where each vertex
is associated with a nonnegative weight
and each edge
is associated with a certain cost or length
. For convenience, we denote
as the graph that
for all edge
.
For any two vertices of
, a path from u to v is vertex-edge alternative sequence:
such that the
are all distinct and
for
. The number of edges of a path is its length. Let
be the length of a shortest path in G between u and v, called the distance of two vertices u and v. Furthermore, each edge
can be considered as a continuous interval, where a point
in e is identified by a parameter
such that
and
. We can also define the distance between two points similarly to the distance between two vertices. The classical p-median location model is to find the set of p points on G, say
, so as to minimize the median function
where
. By the dominating property of vertex set, we know that there exists an optimal solution to the p-median problem that is exactly the subset of V. Hence, we focus on the set
hereafter. For the sake of modern location model, the new facilities are required to be connected to a network for communication/security reasons. This fact motivates the so-called connected p-median problem on G, where the set S is the connected set on the underlying graph. For two vertices set
and
, we define
.
Given a graph G, a vertex u is called a cut vertex of G if
, where
denotes the number of components of G. A connected subgraph H of G is called a block of G if H is maximal and it contains no cut vertices. A graph G is a block graph if all blocks of G are cliques and any two distinct blocks
and
have at most one common vertex, where a clique in a graph is a complete subgraph maximal under inclusion.
Given a block graph G and a set
of p connected vertices, we denote by
the set of connected subgraphs induced by deleting all vertices in
and all edges in blocks containing at least one vertex of
. A vertex v is said to be in the border of
if there does not exist any pair
and
in
such that v is an intermediate vertex of the shortest path connecting them. Resultantly, we denote
the set of all vertices in the border of
. Furthermore, let
be the set of vertices, which are adjacent to some vertices in
and are not in
. Meanwhile, we define
, for v in
, as the set of all vertices in
that is adjacent to v. If a connected subgraph in
contains a vertex
, then this graph is defined as
. For a vertex
, let
be the subgraph induced by
.
Modifying vertex weights of a graph at minimum total cost so that a predetermined set of p connected vertices becomes a connected p-median on the perturbed graph. This problem is the so-called inverse connected p-median problem on graphs. Nguyen and Hung [4] consider the problem of a block graph with uniform edge lengths under various cost functions. To solve the problem, they first find an optimality criterion for a set that is a connected p-median. Based on this criterion, they can formulate the problem as a convex or quasiconvex univariate optimization problem. Finally, they develop combinatorial algorithms that solve the problems under the three cost functions in
time, where n is the number of vertices in the underlying block graph. In the scope of their paper, the following cost functions are considered.
1) Rectilinear norm:
2) Chebyshev norm:
3) Bottleneck Hamming distance:
where the Hamming distance
is identified by
if
and
otherwise. The following results are established in Nguyen and Hung [4] .
Lemma 1. [4] If there exists a vertex
and vertex
such that
, then
is not a connected p-median of G.
Theorem 1. [4] (Optimality Criterion) The set
is a connected p-median of the block graph G if and only if
for all
and
.
Theorem 2. [4] The inverse connected p-median problem on a block graph can be solved in
time.
Theorem 3. [4] The inverse connected p-median problem on block graphs under Chebyshev norm can be solved in
time.
Theorem 4. [4] The inverse connected p-median problem under bottleneck Hamming distance can be solved in
time.
2. Counterexample
As we observe, Lemma 1 and Theorem 1 in Nguyen and Hung [4] are incorrect. In this note, we point out these incorrect results by a counterexample.
Counterexample 1. Let us consider the block graph G in Figure 1, where the prespecified set of connected vertices is
and the weights are labeled on the corresponding vertices.
According to the symbols and definitions in Nguyen and Hung [4] , one can deduce the following results.
,
. Moreover, the subgraph
is induced by
and the subgraph
is induced by
. Based on the weights of vertices, one obtains the weights of subgraphs are calculated as in Table 1.
From Table 1, one can see that
for all
and
. If Lemma 1 and Theorem 1 are correct, then the set
is a connected p-median of the block graph. Let
. Since
, the set
is not a connected p-median of the block graph, this instance is indeed a counterexample for Lemma 1 and Theorem 1.
In addition, the proofs in Lemma 1 and Theorem 1 in Nguyen and Hung [4] are also incorrect. Let
. According to the symbols and definitions in Nguyen and Hung [4] , one can deduce that the subgraph
is induced by
and the subgraph
is induced by
. Then
Since
the deduction in Lemma 1 and Theorem 1 are clearly incorrect.
3. Erratum
The Lemma 1 and Theorem 1 in Nguyen and Hung [4] are incorrect mainly because of the following notation definitions:
,
,
,
,
and
. In this article, we will preserve the symbol definition of
and
, redefine symbols:
and
, and do not use
and
anymore to avoid confusion with
.
For a vertex
, let
be the subgraph induced by vertices that can only be served by v. In other words, for vertices
, only vertex
satisfies
. Let
be the set of vertices of
, which are adjacent to some vertices in
. If the shortest path from
to
passes through
, then
is said to be served by
through u. For a vertex
, let
be the subgraph induced by the vertices which are served by
through u.
Table 1. Weights of subgraphs in G.
Example 1. Let us consider the block graph G in Figure 1, where the prespecified set of connected vertices is
and the weights are labeled on the corresponding vertices.
According to the new symbols and definitions above, one can deduce the following results.
,
. Moreover, the subgraph
is induced by
and the subgraph
is induced by
.
Using the same method in the proof of Lemma 1 in Nguyen and Hung [4] , the following lemma can be proved.
Lemma 2. If there exists a vertex
and vertex
such that
, then
is not a connected p-median of
.
There is no problem in the method and thought of proving Theorem 1 in Nguyen and Hung [4] , but the description is not clear and concise enough. We will give a new proof of Theorem 1 in the following.
Theorem 5. (Optimality Criterion) The set
is a connected p-median of the block graph
if and only if
for all
and
.
Proof. If
is a connected p-median of the block graph G, then
for all
and
. This is the converse-negative proposition of Lemma 2, which is clearly true.
Conversely, we prove that if
for all
and
, then the set
is a connected p-median of the block graph G. Let
be a connected p-median such that
and
is as small as possible. Furthermore, if
, let’s assume that
contains as many vertices as possible. We take a vertex
such that
. As
, we know that there exists a vertex
such that
. Hence
. Similarly, we choose a vertex
such that
. There exists a vertex
such that
. Hence
. By assumption of
,
. Hence,
. On the other hand, since
is a connected p-median,
. Hence,
. We set
. Obviously
is connected. Using the same method in the proof of Lemma 1 in Nguyen and Hung [4] , we have
. Then
is also a connected p-median. If
, then
. If
, then
contains more vertices than
. This contradicts the choice of
. Therefore,
and
is a connected p-median of the block graph G.
In the solution approach of the inverse connected p-median problem on block graphs in [4] , we only need to change
,
and
into the new definition of
,
and
, respectively. The inverse connected p-median problem on block graphs
under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance, can be solved by using the approach in [4] . However, the description of Theorem 2, Theorem 3 and Theorem 4 in Nguyen and Hung [4] is not complete and rigorous enough. Let’s redescribe the three theorems in the following.
Theorem 6. The inverse connected p-median problem on block graphs
under Rectilinear norm can be solved in
time, where n is the number of vertices in the block graph.
Theorem 7. The inverse connected p-median problem on block graphs
under Chebyshev norm can be solved in
time, where n is the number of vertices in the block graph.
Theorem 8. The inverse connected p-median problem on block graphs
under Bottleneck Hamming distance can be solved in
time, where n is the number of vertices in the block graph.
Acknowledgements
This work was partially supported by the Natural Science Research Foundation of Colleges and Universities of Anhui Province (KJ2021A0968, KJ2021A0967), the Key Scientific and Technological Project of Higher Education of Henan Province (20A110018), the PhD Research Foundation of Henan Agricultural University (30601668).