Computing the metric dimension for chain graphs

The metric dimension of a graph G is the smallest size of a set R of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in R. Computing the metric dimension is NP-hard, even when restricting inputs to bipartite graphs. We present a linear-time algorithm for computing the metric dimension for chain graphs, which are bipartite graphs whose vertices can be ordered by neighborhood inclusion. We show how to compute the metric dimension of bipartite chain graphs.Our algorithm works in linear time even on compact representations.We also conclude combinatorial results for simple chain graphs.Our order-theoretic arguments may be useful for other problems, as well.We indicate this for some variants of metric dimension.