More Like this

1. Chained graphs and some applications

   https://doi.org/10.1007/s41109-021-00377-4  

   Concas, Anna; Reichel, Lothar; Rodriguez, Giuseppe; Zhang, Yunzi (December 2021, Applied Network Science)

   null (Ed.)

   Abstract This paper introduces the notions of chained and semi-chained graphs. The chain of a graph, when existent, refines the notion of bipartivity and conveys important structural information. Also the notion of a center vertex $$v_c$$ v c is introduced. It is a vertex, whose sum of p powers of distances to all other vertices in the graph is minimal, where the distance between a pair of vertices $$\{v_c,v\}$$ { v c , v } is measured by the minimal number of edges that have to be traversed to go from $$v_c$$ v c to v . This concept extends the definition of closeness centrality. Applications in which the center node is important include information transmission and city planning. Algorithms for the identification of approximate central nodes are provided and computed examples are presented. 

   more » « less
2. Vantage Point Selection Algorithms for Bottleneck Capacity Estimation

   https://doi.org/10.4230/lipics.wads.2025.6  

   Ashvinkumar, Vikrant; Chowdhury, Rezaul; Gao, Jie; Goswami, Mayank; Mitchell, Joseph_S B; Polishchuk, Valentin (August 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Morin, Pat; Oh, Eunjin (Ed.)

   Motivated by the problem of estimating bottleneck capacities on the Internet, we formulate and study the problem of vantage point selection. We are given a graph G = (V, E) whose edges E have unknown capacity values that are to be discovered. Probes from a vantage point, i.e, a vertex v ∈ V, along shortest paths from v to all other vertices, reveal bottleneck edge capacities along each path. Our goal is to select k vantage points from V that reveal the maximum number of bottleneck edge capacities. We consider both a non-adaptive setting where all k vantage points are selected before any bottleneck capacity is revealed, and an adaptive setting where each vantage point selection instantly reveals bottleneck capacities along all shortest paths starting from that point. In the non-adaptive setting, by considering a relaxed model where edge capacities are drawn from a random permutation (which still leaves the problem of maximizing the expected number of revealed edges NP-hard), we are able to give a 1-1/e approximate algorithm. In the adaptive setting we work with the least permissive model where edge capacities are arbitrarily fixed but unknown. We compare with the best solution for the particular input instance (i.e. by enumerating all choices of k tuples), and provide both lower bounds on instance optimal approximation algorithms and upper bounds for trees and planar graphs. 

   more » « less
3. Current Flow Group Closeness Centrality for Complex Networks?

   https://doi.org/10.1145/3308558.3313490  

   Li, Huan; Peng, Richard; Shan, Liren; Yi, Yuhao; Zhang, Zhongzhi (June 2019, The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019)

   Current flow closeness centrality (CFCC) has a better discriminating ability than the ordinary closeness centrality based on shortest paths. In this paper, we extend this notion to a group of vertices in a weighted graph, and then study the problem of finding a subset S of k vertices to maximize its CFCC C(S), both theoretically and experimentally. We show that the problem is NP-hard, but propose two greedy algorithms for minimizing the reciprocal of C(S) with provable guarantees using the monotoncity and supermodularity. The first is a deterministic algorithm with an approximation factor (1−kk−1⋅1e) and cubic running time; while the second is a randomized algorithm with a (1−kk−1⋅1e−ϵ)-approximation and nearly-linear running time for any ϵ>0. Extensive experiments on model and real networks demonstrate that our algorithms are effective and efficient, with the second algorithm being scalable to massive networks with more than a million vertices. 

   more » « less
4. Hardness of Approximation for Orienteering with Multiple Time Windows

   Garg, Naveen; Khanna, Sanjeev; Kumar, Amit (January 2021, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms)

   null (Ed.)

   Vehicle routing problems are a broad class of combinatorial optimization problems that can be formulated as the problem of finding a tour in a weighted graph that optimizes some function of the visited vertices. For instance, a canonical and extensively studied vehicle routing problem is the orienteering problem where the goal is to find a tour that maximizes the number of vertices visited by a given deadline. In this paper, we consider the computational tractability of a well-known generalization of the orienteering problem called the Orient-MTW problem. The input to Orient-MTW consists of a weighted graph G(V, E) where for each vertex v ∊ V we are given a set of time instants Tv ⊆ [T], and a source vertex s. A tour starting at s is said to visit a vertex v if it transits through v at any time in the set Tv. The goal is to find a tour starting at the source vertex that maximizes the number of vertices visited. It is known that this problem admits a quasi-polynomial time O(log OPT)-approximation ratio where OPT is the optimal solution value but until now no hardness better than an APX-hardness was known for this problem. Our main result is an -hardness for this problem that holds even when the underlying graph G is an undirected tree. This is the first super-constant hardness result for the Orient-MTW problem. The starting point for our result is the hardness of the SetCover problem which is known to hold on instances with a special structure. We exploit this special structure of the hard SetCover instances to first obtain a new proof of the APX-hardness result for Orient-MTW that holds even on trees of depth 2. We then recursively amplify this constant factor hardness to an -hardness, while keeping the resulting topology to be a tree. Our amplified hardness proof crucially utilizes a delicate concavity property which shows that in our encoding of SetCover instances as instances of the Orient-MTW problem, whenever the optimal cost for SetCover instance is large, any tour, no matter how it allocates its time across different sub-trees, can not visit too many vertices overall. We believe that this reduction template may also prove useful in showing hardness of other vehicle routing problems. 

   more » « less
5. Dispersed graph labellings

   Martin, William J; Stinson, Douglas R (February 2024, Australasian Journal of Combinatorics)

   Albert, Michael; Billington, Elizabeth J (Ed.)

   A k-dispersed labelling of a graph G on n vertices is a labelling of the vertices of G by the integers 1,...,n such that d(i,i+1) ≥ k for 1 ≤ i ≤ n − 1. Here DL(G) denotes the maximum value of k such that G has a k-dispersed labelling. In this paper, we study upper and lower bounds on DL(G). Computing DL(G) is NP-hard. However, we determine the exact value of DL(G) for cycles, paths, grids, hypercubes and complete binary trees. We also give a product construction and we prove a degree-based bound. 

   more » « less