Splitting a tournament into two subtournaments with given minimum outdegree

Frédéric Havet 1 Bernard Lidicky 2
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A {\it $(k_1,k_2)$-outdegree-splitting} of a digraph $D$ is a partition $(V_1,V_2)$ of its vertex set such that $D[V_1]$ and $D[V_2]$ have minimum outdegree at least $k_1$ and $k_2$, respectively. We show that there exists a minimum function $f_T$ such that every tournament of minimum outdegree at least $f_T(k_1,k_2)$ has a $(k_1,k_2)$-outdegree-splitting, and $f_T(k_1,k_2) \leq k_1^2/2+3k_1/2 +k_2+1$. We also show a polynomial-time algorithm that finds a $(k_1,k_2)$-outdegree-splitting of a tournament if one exists, and returns 'no' otherwise. We give better bound on $f_T$ and faster algorithms when $k_1=1$.
Document type :
Reports
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00943152
Contributor : Frederic Havet <>
Submitted on : Friday, February 7, 2014 - 9:53:34 AM
Last modification on : Thursday, August 1, 2019 - 2:12:06 PM
Long-term archiving on: Monday, May 12, 2014 - 11:51:27 AM

File

RR-8469.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00943152, version 1

Citation

Frédéric Havet, Bernard Lidicky. Splitting a tournament into two subtournaments with given minimum outdegree. [Research Report] RR-8469, INRIA. 2014. ⟨hal-00943152⟩

Share

Metrics

Record views

433

Files downloads

484