On the fixed-parameter tractability of the maximum connectivity improvement problem

DOI10.1007/S00224-020-09977-6MaRDI QIDQ2195571zbMATH OpenOpenAlexFDO

Authors Federico Corò, Gianlorenzo D'Angelo, Vahan V. Mkrtchyan

Publication date 26 August 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.12000

zbMATH Keywords

connectivitygraph augmentationparameterized complexity

Mathematics Subject Classification ID

Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In the Maximum Connectivity Improvement (MCI) problem, we are given a directed graph $G=(V,E)$ and an integer $B$ and we are asked to find $B$ new edges to be added to $G$ in order to maximize the number of connected pairs of vertices in the resulting graph. The MCI problem has been studied from the approximation point of view. In this paper, we approach it from the parameterized complexity perspective in the case of directed acyclic graphs. We show several hardness and algorithmic results with respect to different natural parameters. Our main result is that the problem is $W[2]$-hard for parameter $B$ and it is FPT for parameters $|V|-B$ and $u$, the matching number of $G$. We further characterize the MCI problem with respect to other complementary parameters.

Recommendations

• On the maximum connectivity improvement problem
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• Fixed-parameter algorithms for minimum cost edge-connectivity augmentation
• Minimum Cardinality Point-to-point Connectivity Augmentation Problem
• Directed vertex-connectivity augmentation

Cites work

• Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
• Augmentation Problems
• Connections in combinatorial optimization
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation
• scientific article; zbMATH DE number 1670542 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• Improved approximation algorithms for minimum cost node-connectivity augmentation problems
• Improving the betweenness centrality of a node by adding links
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Minimizing the diameter of a network using shortcut edges
• On the approximability of the link building problem
• On the maximum connectivity improvement problem
• Parameterized algorithms for survivable network design with uniform demands
• Parameterized algorithms to preserve connectivity
• Path-contractions, edge deletions and connectivity preservation
• The Effect of New Links on Google Pagerank
• The parameterized complexity of centrality improvement in networks
• The parametric complexity of graph diameter augmentation

Cited in

(2)

• On the maximum connectivity improvement problem
• On the maximum betweenness improvement problem

This page was built for publication: On the fixed-parameter tractability of the maximum connectivity improvement problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2195571)