Affiliations: [a] Department of Computer Engineering and Information Technology, Amirkabir University of Technology, Tehran, Iran. mroayaei@aut.ac.ir | [b] Department of Computer Engineering and Information Technology, Amirkabir University of Technology, Tehran, Iran; School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
Correspondence:
[*]
Address for correspondence: P.O. Box 15875-4413, #424 Hafez Avenue, Amirkabir University of Technology, Tehran, Iran.
Note: [†] This research was in part supported by a grant from IPM. (No. CS1396-5-01).
Abstract: 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.
