Invertibility of Digraphs and Tournaments

DOI10.1137/23M1547135MaRDI QIDQ6141864zbMATH OpenWikidataFDO

Authors Noga Alon, Emil Powierski, Alex Scott, Elizabeth L. Wilmer

Publication date 23 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.11969

zbMATH Keywords

decycling setdigraphsdijoin operationinversion numbertournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: For an oriented graph $D$ and a set $XsubseteqV(D)$, the inversion of $X$ in $D$ is the digraph obtained by reversing the orientations of the edges of $D$ with both endpoints in $X$. The inversion number of $D$, $operatornameinv(D)$, is the minimum number of inversions which can be applied in turn to $D$ to produce an acyclic digraph. Answering a recent question of Bang-Jensen, da Silva, and Havet, we show that for each fixed $kinmathbbN$ the problem of deciding whether a tournament $T$ has $operatornameinv(T)leqk$ is solvable in time $O(lvertV(T)ver{t}^2)$. This exponent is optimal for all $k$. On the other hand, we build on their work to prove their conjecture that for $kgeq1$ the problem of deciding whether a general oriented graph $D$ has $operatornameinv(D)leqk$ is NP-complete. We also construct oriented graphs with inversion number equal to twice their cycle transversal number, confirming another conjecture of Bang-Jensen, da Silva, and Havet, and we provide a counterexample to their conjecture concerning the inversion number of so-called 'dijoin' digraphs while proving that it holds in certain cases. Finally, we asymptotically solve the natural extremal question in this setting, improving on previous bounds of Belkhechine, Bouaziz, Boudabbous, and Pouzet to show that the maximum inversion number of an $n$-vertex tournament is $(1+o(1))n$.

Recommendations

• Inversions in tournaments
• Cycle reversions and dichromatic number in tournaments

Cites work

• Boolean designs and self-dual matroids
• Combinatorics of genome rearrangements.
• Feedback arc set. A history of the problem and algorithms
• Fundamentals of parameterized complexity
• Genome Rearrangements and Sorting by Reversals
• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 871927 (Why is no real title available?)
• Introduction to algorithms.
• Inversions in tournaments
• On Subsets with Intersections of Even Cardinality
• On the Boolean dimension of a graph and other related parameters
• On the maximum cardinality of a consistent set of arcs in a random tournament
• Optimal ranking of tournaments
• Optimally ranking unrankable tournaments
• Orthogonal Matrices Over Finite Fields
• Ranking Tournaments
• Reducibility among combinatorial problems
• Structure theorem for tournaments omitting N₅
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Tournament Ranking with Expected Profit in Polynomial Time
• Transforming cabbage into turnip
• Transitiv orientierbare Graphen

Cited in

(7)

• On the minimum number of inversions to make a digraph k-(arc-)strong
• On tournament inversion
• A note on the invertibility of oriented graphs
• Problems, proofs, and disproofs on the inversion number
• Diameter of the inversion graph
• Parameterized algorithms for k-inversion
• Inversion diameter and treewidth

This page was built for publication: Invertibility of Digraphs and Tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6141864)