ALGORITHMS FOR FINDING A MAXIMUM NON-k-LINKED GRAPH

作者：Kobayashi Yusuke^*; Yoshida Yuichi

来源：SIAM Journal on Discrete Mathematics, 2012, 26(2): 591-604.

DOI：10.1137/110846725

• k-linkedness
• H-linkedness
• disjoint paths
• connectivity

A graph with at least 2k vertices is said to be k-linked if for any two ordered k-tuples (s(1),...,s(k)) and (t(1),...,t(k)) of 2k distinct vertices, there exist pairwise vertex-disjoint paths P-1,...,P-k such that P-i connects s(i) and t(i) for i = 1,...,k. For a given graph G, we consider the problem of finding a maximum induced subgraph of G that is not k-linked. This problem is a common generalization of computing vertex-connectivity and testing k-linkedness of G, and it is closely related to the concept of H-linkedness. In this paper, we give the first polynomial-time algorithm for the case of k = 2, whereas a similar problem to find a maximum induced subgraph without 2-vertex-disjoint paths connecting fixed terminal pairs is NP-hard. For the case of general k, we give an (8k-2)-additive approximation algorithm. We also investigate the computational complexity of the edge-disjoint case and the directed case.

• 出版日期2012