Premium
Kernelization and complexity results for connectivity augmentation problems
Author(s) -
Guo Jiong,
Uhlmann Johannes
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20354
Subject(s) - kernelization , combinatorics , graph , vertex connectivity , computer science , mathematics , vertex (graph theory) , connectivity , theoretical computer science , discrete mathematics
Abstract Connectivity augmentation problems ask for adding a set of at most k edges (called links) whose insertion makes a given graph satisfy a specified connectivity property, such as bridge‐connectivity or biconnectivity. A bridge‐connected (biconnected) graph is a connected graph that does not possess an edge (a vertex) whose removal results in a disconnected graph. We show that, for bridge‐connectivity and biconnectivity, the respective connectivity augmentation problems admit problem kernels with O ( k 2 ) vertices and links. Moreover, we study partial connectivity augmentation problems, naturally generalizing connectivity augmentation problems. Here, we do not require that, after adding the edges, the entire graph should satisfy the connectivity property, but a large subgraph. In this setting, three polynomial‐time solvable connectivity augmentation problems behave differently, namely, the partial bridge‐connectivity augmentation problem and the partial biconnectivity augmentation problem remain polynomial‐time solvable, whereas the partial strong connectivity augmentation problem becomes W[2]‐hard with respect to k . © 2009 Wiley Periodicals, Inc. NETWORKS, 2010