2026-08-21T18:34:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27434 2026-08-21T14:42:39Z ddc:004 open_access

Increasing Arc-Connectivity by Bounded- and Fixed-Size Inversions Hörsch, Florian Picasarri-Arrieta, Lucas Bounded-size Inversions Strong Connectivity Approximation Algorithms Parameterized Complexity Given an integer k ⩾ 1, a digraph D is k-arc-strong if the removal of any set of at most k-1 arcs of D yields a strongly connected digraph. For a digraph D and some set X ⊆ V(D), the inversion of X is the operation of flipping all arcs both of whose endvertices are in X. We initiate the study of establishing arc-connectivity properties by applying inversions of bounded or fixed size. For fixed-size inversions, we consider the feasibility of the problem by characterizing, for all integers p ⩾ 2 and k ⩾ 1, the digraphs that can be made k-arc-strong by applying inversions of size exactly p, provided a minimum size of the digraphs. For bounded-size inversions, the tractability of the feasibility problem follows easily from a famous theorem of Nash-Williams, so we focus on minimising the number of inversions. We prove that for all integers p ⩾ 3 and k ⩾ 1 and any ε > 0, there exists a polynomial-time (4k-2+ε)-approximation algorithm for computing the minimum number of inversions of size at most p that make a given digraph k-arc-strong. This is in stark contrast to other results on inversion optimization problems. On the other hand, we show that for any p ⩾ 3 and k ⩾ 1 the problem is NP-hard, and, moreover, APX-hard. As a result on parameterized complexity, we show that for any k ⩾ 2, it is W[1]-hard with respect to p to decide whether a given digraph can be made k-arc-strong by applying a single inversion of size at most p. We also prove that for a given multidigraph, it is W[1]-hard with respect to 𝓁 to decide whether it can be made 2-arc-strong by applying 𝓁 inversions of size 2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Hörsch and Lucas Picasarri-Arrieta 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.52 urn:nbn:de:0030-drops-274340 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.52 eng https://creativecommons.org/licenses/by/4.0/legalcode