Minimum Cardinality Point-to-point Connectivity Augmentation Problem

We consider an augmentation problem to establish point-to-point connectivity on unweighted graphs where there is no restriction on choosing the augmenting edges (arcs). Given a directed (an undirected) graph G and set P = {(si, ti) : 1 ≤ i ≤ m} of pairs of vertices in the graph, one has to find the minimum cardinality set of arcs (edges) to be added to the graph so that the resulting graph has (can be oriented in order to have) directed paths between the specified pairs of vertices. In the case of undirected graphs, an efficient polynomial-time algorithm is presented. In the case of directed graphs, we find that this problem is NP-hard. In addition, we show that it is fixed-parameter tractable with respect to the combined parameter the number of sink vertices and the number of source vertices of a graph, however, it is W[1]-hard with respect to both parameters the number of new edges and the number of input pairs.

---

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).