Increasing arc-connectivity by bounded- and fixed-size inversions
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913059160719360 |
|---|---|
| author | Hörsch, Florian Picasarri-Arrieta, Lucas |
| author_facet | Hörsch, Florian Picasarri-Arrieta, Lucas |
| contents | For a digraph $D$ and some $X \subseteq 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, the feasibility problem is interesting. For all integers $p \geq 2$ and $k \geq 1$, we give a characterization of the digraphs that can be made $k$-arc-strong by applying inversions of size exactly $p$, provided they are sufficiently large.
For bounded-size inversions, the feasibility problem is easy, so we focus on minimising the number of inversions. We prove that for all integers $p\geq 3$ and $k \geq 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\geq 3$ and $k \geq 1$ the problem is NP-hard, and, moreover, APX-hard.
As a result on parameterized complexity, we show that for any $k \geq 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 $\ell$ to decide whether it can be made 2-arc-strong by applying $\ell$ inversions of size 2. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_22584 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Increasing arc-connectivity by bounded- and fixed-size inversions Hörsch, Florian Picasarri-Arrieta, Lucas Combinatorics Discrete Mathematics For a digraph $D$ and some $X \subseteq 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, the feasibility problem is interesting. For all integers $p \geq 2$ and $k \geq 1$, we give a characterization of the digraphs that can be made $k$-arc-strong by applying inversions of size exactly $p$, provided they are sufficiently large. For bounded-size inversions, the feasibility problem is easy, so we focus on minimising the number of inversions. We prove that for all integers $p\geq 3$ and $k \geq 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\geq 3$ and $k \geq 1$ the problem is NP-hard, and, moreover, APX-hard. As a result on parameterized complexity, we show that for any $k \geq 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 $\ell$ to decide whether it can be made 2-arc-strong by applying $\ell$ inversions of size 2. |
| title | Increasing arc-connectivity by bounded- and fixed-size inversions |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2604.22584 |