Complexity of interval numbers in tournament graph convexities analyzed
Interval number for tournaments in P3-convexity
Computational Complexity
Summary
This paper looks at how hard it is to find certain 'interval numbers' in special networks called tournaments. The authors study two types of these interval numbers and find that deciding if these numbers are below a certain value is very computationally tough. They prove that no fast algorithm is likely to exist for these problems unless certain common assumptions in computer science fail. They also identify cases where some quick approaches are possible and others where the problem remains difficult and not fully classified.
What this means in practice
- •For algorithm designers: Avoid designing parameterized algorithms expecting sub-exponential time for interval number problems in P3-convexities on tournaments.
- •For complexity theorists: Use the proven NP-intermediate classification to guide research on complexity boundaries within graph convexities on tournaments.
A theory result. No direct application yet.
Authors
Idian C. Capozzoli, Yan S. Couto, Enrique Junchaya
Abstract
We study the complexity of determining the interval numbers of tournaments in the $\overrightarrow{P_3}$ and $\overrightarrow{P_3^*}$ convexities, denoted by $\overrightarrow{\mathrm{in}}_{P_3}(T)$ and $\overrightarrow{\mathrm{in}}_{P_3^*}(T)$ on a tournament $T$. For each $\overrightarrow{\mathcal{X}} \in \{\overrightarrow{P_3}, \overrightarrow{P_3^*}\}$, we show that determining whether $\overrightarrow{\mathrm{in}}_{\mathcal{X}}(T) \leq k$ is W[2]-complete when parameterized by $k$. Moreover, under ETH, we show that there is no parameterized algorithm for that problem with running time $f(k)\, n^{o(k)}$ on an $n$-vertex tournament, where $f$ is any computable function. For the $\overrightarrow{P_3}$-convexity, we also show that $\overrightarrow{\mathrm{in}}_{P_3}(T) = \mathcal{O}(\log n)$, which yields a simple quasi-polynomial $n^{\mathcal{O}(\log n)}$ brute-force algorithm. On the other hand, under ETH, we show that the problem is NP-intermediate, that is, it is neither NP-hard nor in P. For the $\overrightarrow{P_3^*}$-convexity, the same brute force algorithm is not quasi-polynomial, since we present a family of instances with $\overrightarrow{\mathrm{in}}_{P_3^*}(T) = Θ(n)$. We conjecture that this problem is NP-complete.