35588-Article Text-58978-1-10-20230714.pdf (373.84 kB)

# On the minimum number of inversions to make a digraph k-(arc-)strong

conference contribution

posted on 2024-04-03, 11:19 authored by Julien Duron, Frédéric Havet, Florian HörschFlorian Hörsch, Clément RambaudThe inversion of a set X of vertices in a digraph D consists of reversing the direction of all arcs of D(X). We study sinv k (D) (resp. sinv k (D) which is the minimum number of inversions needed to transform D into a k-arc-strong (resp. k-strong) digraph and sinv k (N) = max {sinv k (D) | D is a 2k-edge-connected digraph of order n}. We show : (i) 1/2 log (n-k+1) o;; (ii) for any fixed positive integers k and t, deciding whether a given oriented graph G satisfies sinv k (G) < t (resp. sinv k (G) < t) is NP-complete ; (iii) if T is a tournament of order at least 2k + 1 , then sinv k (T) < sinv k (T) < 2k, and 1/2 log (2k+1) < sinv k (T) < sinv k (T) for some T; (iv) if T is a tournament of order at least 28k - 5 (resp. 14k - 3), then sinv k (T) < 1 (resp. sinv k (T) < 6); (v) for every e > 0, there exists C such that sinv k (T) < C for every tournament T on at least 2k + 1 + Ek vertices.

## History

## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

European Conference on Combinatorics Graph Theory and Applications (EUROCOMB)## Journal

European Conference on Combinatorics Graph Theory and Applications## Volume

abs/2303.11719## Page Range

386-392## Publisher

Masaryk University Press## Open Access Type

- Hybrid

## BibTeX

@inproceedings{Duron:Havet:Hörsch:Rambaud:2023, title = "On the minimum number of inversions to make a digraph k-(arc-)strong", author = "Duron, Julien" AND "Havet, Frédéric" AND "Hörsch, Florian" AND "Rambaud, Clément", year = 2023, month = 8, journal = "European Conference on Combinatorics Graph Theory and Applications", number = "12", pages = "386--392", publisher = "Masaryk University Press", issn = "2788-3116", doi = "10.5817/cz.muni.eurocomb23-054" }## Usage metrics

## Categories

No categories selected## Keywords

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC