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

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

Download (373.84 kB)
conference contribution
posted on 2024-04-03, 11:19 authored by Julien Duron, Frédéric Havet, Florian Hörsch, Clément Rambaud
The 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" }