Interval number for tournaments in P3-convexity

Idian C. Capozzoli; Yan S. Couto; Enrique Junchaya

In the authors' words

We study the complexity of determining the interval numbers of tournaments in the $P_{3}$ and $P_{3}^{*}$ convexities, denoted by $in_{P_{3}} (T)$ and $in_{P_{3}^{*}} (T)$ on a tournament $T$ . For each $X \in {P_{3}, P_{3}^{*}}$ , we show that determining whether $in_{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 $P_{3}$ -convexity, we also show that $in_{P_{3}} (T) = O (lo g n)$ , which yields a simple quasi-polynomial $n^{O (l o g 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 $P_{3}^{*}$ -convexity, the same brute force algorithm is not quasi-polynomial, since we present a family of instances with $in_{P_{3}^{*}} (T) = Θ (n)$ . We conjecture that this problem is NP-complete.

Main resultLimitation the authors admit

Interval number for tournaments in P3-convexity

In the authors' words

More on Algorithms & complexity that day

Smoothed Analysis of Inconsistent A*

Hardness of Online Directed Steiner Network

Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

Parameter-Free Triangle Counting