## Abstrakt

Augmenting an undirected or a directed graph (digraph) by adding new edges or arcs, to increase its connectivity to a target value, is a fundamental problem in combinatorial optimization and graph theory. In this paper we study the basic problem of augmenting an input digraph to make it strongly connected, which is known as the Strong Connectivity Augmentation problem. Here, the input is a digraph D = (V, A), a set of links L ⊆ V × V, and a positive integer k. The objective is to decide if there exists a subset F ⊆ L, of size at most k, such that D^{0} = (V, A ∪ F) is strongly connected. We consider the general version of this problem where, additionally, there is a weight function w : L → R^{+} on the links, and the goal is to find a minimum weight subset F ⊆ L of cardinality at most k, such that D^{0} = (V, A∪F) is strongly connected. We design an algorithm for this problem that runs in time 2^{O}(k log k)n^{O}^{(1)}, thereby showing that it is fixed parameter tractable (FPT). Here, n = |V |. This also resolves an open problem stated by Guo and Uhlmann more than a decade ago [ Networks 56(2): 131-142 (2010)].

Originalsprog | Engelsk |
---|---|

Titel | Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) |

Redaktører | Dániel Marx |

Antal sider | 16 |

Forlag | Association for Computing Machinery |

Publikationsdato | 2021 |

Sider | 219-234 |

ISBN (Elektronisk) | 9781611976465 |

DOI | |

Status | Udgivet - 2021 |

Begivenhed | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, USA Varighed: 10. jan. 2021 → 13. jan. 2021 |

### Konference

Konference | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |
---|---|

Land/Område | USA |

By | Alexandria, Virtual |

Periode | 10/01/2021 → 13/01/2021 |

Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics |

Navn | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Bibliografisk note

Funding Information:∗UniversityofBergen, Norway, andUniversityofSouthern Denmark, Odense, Denmark. kristine.knudsen@ii.uib.no †Max-PlanckInstituteforInformatics, SIC,Saarbrucken, Germany.pmisra@mpi-inf.mpg.de ‡TheInstituteofMathematicalSciences, HBNI,Chennai, India, and University of Bergen, Norway. saket@imsc.res.in Saket Saurabhissupportedbyfundingfrom theEuropeanResearchCouncil(ERC) under theEuropeanUnion’sHorizon2020research andinnovation programme(grantagreement No. 819416)andalsoacknowledgesthe supportofSwarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Publisher Copyright:

Copyright © 2021 by SIAM