July 16, 2026
What problems can one solve on a tournament if only its score sequence is known?
Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs (digraphs), both from combinatorial and algorithmic perspectives. Over the years, researchers have identified multiple classical digraph problems that can be solved on a tournament from only its score sequence (indegree sequence). These problems include acyclicity testing and topological sorting [Chakrabarti, Ghosh, McGregor, and Vorotnikova; SODA’20], \(s,t\)-reachability, strong connectivity, and decomposition into strongly connected components (SCC) [Ghosh and Kuchlous; ESA’24], and vertex-ordering problems such as cutwidth and optimal linear arrangement [Barbero, Paul, and Pilipczuk; ICALP’17]. These prior works showed the sufficiency of the score sequence by designing distinct algorithms for the individual problems. In this work, we give a simple unified framework that solves all these problems using only indegrees and, in fact, completely characterises the class of problems that is determined by the indegree information: problems whose answers are invariant under cycle reversals.
As a byproduct of our results, we obtain algorithms for a variety of connectivity-based, cut-based, and vertex-ordering problems on tournaments and “almost tournaments” in the streaming, the two-player communication, and the cut-query models of computation. Some of these algorithms match existing optimal bounds and others provide bounds improving the state of the art. Specifically, our polynomial-time algorithms for almost tournaments improve upon the exponential-time algorithms of Ghosh and Kuchlous and have much simpler analysis.
The said characterisation is a special case of a much more general result that we establish: for any arbitrary digraph, the knowledge of its skeleton (underlying undirected graph) and the vertex indegrees completely determines its properties that are invariant under cycle reversal. In particular, this gives us an \(O(n^2)\)-cut-query algorithm to solve directed minimum cut on \(n\)-node graphs in polynomial time, a significant result that has been observed in the literature but not concretely stated in this form. Our results also unveil interesting general connections between two well-studied sublinear models for graph problems: semi-streaming and cut-query.
Tournaments are directed graphs (digraphs) where each pair of nodes shares exactly one directed edge. They have a rich literature that dates back more than half a century (see the book on tournaments by Moon [1]). In particular, the score sequence of a tournament, which is the sequence of its indegrees, has been a topic of extensive study [2]–[7]. It has been noted sporadically in the literature that multiple classical digraph problems can be solved on a tournament from only its indegree sequence. For instance, Chakrabarti, Ghosh, McGregor, and Vorotnikova [8] observed that the acyclicity of a tournament and the topological ordering of an acyclic tournament are completely determined by its score sequence: for the former, check if the indegree sequence is a permutation of \(\{0,\ldots, n-1\}\), and for the latter, sort the nodes by indegree. Again, it is known that sorting by indegree yields optimal solutions for two widely-studied vertex ordering problems: cutwidth (as shown by Fradkin [9]) and optimal linear arrangement (shown by Barbero, Paul, and Pilipczuk [10]); see 2.3 for the definition of these problems. A recent and more surprising result of Ghosh and Kuchlous [11] says that the indegree information also determines \(s,t\)-reachability, strong connectivity, and, in general, all strongly connected components (SCCs) of a tournament. This raises an interesting combinatorial question:
Can we characterise the class of problems determined by the score sequence of a tournament?
We answer this question in the affirmative and show that this class is precisely the set of all digraph problems whose answers are invariant under cycle reversal, i.e., whose answers remain the same even if we flip any number of cycles in the graph. Then, given only the score sequence, we always have an algorithm to solve such a problem, even if at the cost of exponential runtime: brute force over all possible tournaments on the given number of nodes to find one satisfying the given score sequence and solve the problem on that input using a classical algorithm. Can we, however, always guarantee a polynomial-time algorithm? We answer this in the affirmative as well, provided that the problem admits a polynomial-time solution in the classical model. Indeed, we achieve this by designing a polynomial-time (in fact, almost-linear time) algorithm to generate a tournament satisfying a given indegree sequence. We thus have the following theorem.
theoremindegt The class of graph problems determined by the indegree sequence of a tournament is precisely the class of problems whose answers are invariant under cycle reversal. Moreover, each problem can be determined with an additive overhead of almost-linear time (\(n^{2+o(1)}\) time for an \(n\)-node tournament) on its classical time-complexity.
Since all problems mentioned in the first paragraph can be easily shown to belong in this class, our result generalises all of them. To solve those problems using the indegree information, prior work proposed different algorithms to process the indegrees, tailored according to the respective problems. [thm:tour-comb] gives a simple unified polynomial-time framework for all those problems since all of them admit polynomial-time algorithms in the classical setting where the entire input can be accessed.
Since tournaments form a rather narrow subclass of digraphs, it is natural to ask: can we generalise the result to a broader class of graphs? [thm:tour-comb] is indeed a special case of our more general theorem: all problems whose answers are invariant under cycle reversal can be solved on any general digraph only from the knowledge of its underlying undirected graph a.k.a. skeleton and indegree sequence.
theoremmaincomb The class of graph problems determined by the skeleton and indegree sequence of a directed graph is precisely the class of problems whose answers are invariant under cycle reversal. Moreover, each problem can be determined with an additive overhead of almost-linear time (\(m^{1+o(1)}\) time for an \(m\)-edge graph) on its classical time-complexity.
Since the skeleton of a tournament is the complete graph, its score sequence suffices.
In the modern world of massive graphs, a natural goal is to analyse them by extracting as little information as possible from the graphs. Tournaments, which have the maximum possible edges, are prime examples of such graphs. They appear in the real world when, for example, there is a pairwise ranking or preference (represented by directed edges) among all elements in a dataset [12]–[14]. Common questions that arise here include detecting whether the rankings are consistent (acyclicity testing), and if so, ordering the elements in increasing order of preference (topological sorting), whether an element \(t\) is (directly or indirectly) preferred over another element \(s\) (\(s,t\)-reachability), or partitioning the elements into groups such that there is a linear ordering of preference among the groups (SCC decomposition).
This motivates the study of streaming algorithms for tournaments [8], [11], [15], [16]. These algorithms make one or a few passes over the edges while maintaining a small summary and then process the summary to generate an output. They usually aim for semi-streaming space, i.e., \(\widetilde{O}(n):= O(n\mathop{\mathrm{poly}}(\log n))\) space for \(n\)-node graphs.3 Observe that problems completely determined by the vertex indegrees admit single-pass semi-streaming algorithms: while processing the stream, we just keep count of the indegrees using \(O(n\log n)\) space. We thus get semi-streaming algorithms for all cycle-reversal-invariant problems on tournaments, and they also carry over to a couple of other popular models for sublinear graph algorithms: (a) the cut-query model where we solve a problem by optimizing queries to an oracle that returns the (directed) cut size for any subset of nodes, i.e., the number of edges incoming to that subset, and (b) the two-player communication model where the input graph is split between two players who need to communicate (possibly in multiple rounds of interaction) as few bits as possible to solve the problem. For (a), we need \(n\) (singleton) cut queries to find all vertex indegrees. For (b), it suffices for one player, say Alice, to communicate to the other player, say Bob, \(O(n\log n)\) bits that encode the indegrees restricted to her edges, since Bob can then compute the score sequence of the entire tournament by adding the indegrees induced by his edges. Hence, we have the following theorem.
theoremcycinvgen Given any digraph problem \(\mathcal{P}\) whose answer is invariant under cycle reversal, there is a single-pass \(O(n\log n)\)-space streaming algorithm, an \(O(n)\)-cut-query algorithm, and an \(O(n\log n)\)-bit communication protocol for the problem \(\mathcal{P}\) on \(n\)-node tournaments. Each algorithm’s runtime has an additive \(n^{2+o(1)}\)-factor overhead on the runtime of a classical algorithm for \(\mathcal{P}\).
In fact, Chakrabarti et al. [8] and Ghosh and Kuchlous [11] discovered their aforementioned results while studying streaming algorithms for tournaments and consequently obtained semi-streaming algorithms for acyclicity testing, topological sorting, \(s,t\)-reachability, strong connectivity, and SCC decomposition. Our result implies such algorithms for all these problems, and also the first semi-streaming algorithms for the fundamental problems of directed minimum cut and minimum \(s,t\)-cut on tournaments. Notably, although there is a substantial body of work on undirected min-cut in the streaming and communication models [18]–[25], BlikstadBEMN22?, the complexity of directed (global or \(s,t\)) min-cut was unknown, even for tournaments. In particular, we obtain the following corollary.
corollarytourimps There is a single-pass \(O(n\log n)\)-space streaming algorithm, an \(O(n)\)-cut-query algorithm, and an \(O(n\log n)\)-bit communication protocol for the following problems on \(n\)-node tournaments, each of which runs in polynomial time.
(i) Connectivity-based problems: \(s,t\)-reachability, strong connectivity, SCC decomposition (or more generally finding the SCC-graph);
(ii) DAG-based problems: acyclicity testing, topological sorting;
(iii) Vertex ordering problems: optimal linear arrangement (OLA), cutwidth;
(iv) Directed cut problems: minimum cut, minimum \(s,t\)-cut.
All these bounds are optimal (up to a \(\log n\) factor).
We remark that having the same “sketch” of the tournament—the indegree-count—for a large variety of problems is very convenient from a practical perspective: the sketch is deterministic, can be computed very easily and quickly, and rather than storing separate summaries based on the respective problems at hand, we can just post-process this single sketch accordingly upon receiving the respective queries.
Again, a natural question about generalisability arises: can we extend these streaming algorithms to a broader class of graphs? Indeed, we cannot fully generalise them since most of these problems are hard in streaming (i.e., require \(\Omega(n^2)\) space for a single pass) for general digraphs [8], [17]. However, Ghosh and Kuchlous [11] showed that they are tractable when the digraph is an “almost tournament”: for digraphs \(k\)-close to a tournament, i.e., digraphs that can be obtained by deleting at most \(k\) edges from a tournament, they gave single-pass \(\widetilde{O}(n+k)\)-space streaming algorithms for the connectivity-based problems mentioned above. Our general theorem for arbitrary digraphs ([thm:gendig-comb]) implies these algorithms and extends them to any cycle-reversal-invariant problem. This is because we can compute the skeleton of such a graph using \(O(k\mathop{\mathrm{poly}}(\log n))\) space: as shown by the said work, we can recover the \(k\) non-edges using this space. Again, in the cut-query model, they can be retrieved using \(O(k \log n)\) queries by standard techniques. We thus get the following corollary.
corollarykcloseimps Given any digraph problem \(\mathcal{P}\) whose answer is invariant under cycle reversal, there is a single-pass \(\widetilde{O}(n+k)\)-space streaming algorithm, an \(\widetilde{O}(n+k)\)-cut-query algorithm, and an \(\widetilde{O}(n+k)\)-communication protocol for \(\mathcal{P}\) on \(n\)-node digraphs that are \(k\)-close to tournaments. Each algorithm’s runtime has an additive \(m^{1+o(1)}\)-factor overhead on the runtime of a classical algorithm for \(\mathcal{P}\), where \(m\) is the number of edges in the digraph.
Furthermore, we get an exponential improvement in runtime over [11]’s algorithm for almost tournaments. Their runtime for \(s,t\)-reachability and strong connectivity is \(\widetilde{O}(2^{\min(k, n)})\) and that for SCC decomposition or SCC-graph construction is \(\widetilde{O}(2^n)\). Our algorithm is not only polynomial time for any \(k\), but it also has much simpler analysis, especially for the SCC decomposition algorithm where their analysis is somewhat intricate.
We remark that our general theorem ([thm:gendig-comb]) for arbitrary digraphs implies the following results in the cut-query model.
corollaryquadquery For any directed graph, global- and \(s,t\)-minimum cut can be solved with \(O(n^2)\) directed cut queries and polynomial runtime.
Indeed, the directed global-minimum cut problem in the cut-query model is a special instance of the fundamental submodular function minimisation (\(\mathsf{SFM}\)) problem since the cut function (directed or undirected) is submodular.4 The \(\mathsf{SFM}\) problem asks to minimise a submodular function \(f : 2^\mathcal{U}\to \mathbb{R}\) when given access to an oracle that, upon query \(S\subseteq \mathcal{U}\), returns the value of \(f(S)\). There has been a long line of work [26]–[40] to pin down the exact complexity of \(\mathsf{SFM}\). The current best algorithm due to Jiang [41] makes \(\widetilde{O}(n^2)\) queries but has has exponential runtime. The best-known (strongly) polynomial-time algorithm has query complexity \(\widetilde{O}(n^3)\), also by [41]. Therefore, these algorithms for \(\mathsf{SFM}\) do not imply [{cor:quadcutq}]. Again, while the undirected analogue of [{cor:quadcutq}] is trivial [24], the directed version is not; since unlike undirected graphs, it is provably impossible to recover a directed graph exactly using \(O(n^2)\) cut queries.5
[cor:quadcutq], however, follows from some observations in prior work ([30] Section 2) but was not stated in this form, which we believe is worth stating explicitly in light of the discussion above. We also remark that our proof technique and algorithm seem simpler than that of [30].
Finally, in 5, we show that our results establish an interesting connection between the streaming and the cut-query models. For tournament problems, existence of a cut-query algorithm (irrespective of the number of queries) implies the existence of a semi-streaming algorithm ([lem:qry-solve-semi-str]). Thus, strong streaming lower bounds can be a useful tool for proving intractability in the cut query model. Again, since this implies that the semi-streaming model is at least as (algorithmically) strong as the cut-query model for tournament problems, a natural question is whether it is strictly stronger: is there a tournament problem that is undecidable by cut queries, but solvable by a semi-streaming algorithm? We answer this question in the affirmative ([prop:qrystrsep]).
Apart from the results mentioned above, Chakrabarti et al. [8] obtained algorithms and lower bounds for approximate feedback arc set in tournaments (FAST) and for source/sink-finding, both in adversarial-order and random-order streams. Baweja, Jia, and Woodruff [15] then improved [8]’s results for feedback arc set. They also gave \((p+1)\)-pass \(O(n^{1+1/p})\)-space algorithms for SCC decomposition (also implying an algorithm for reachability), strong connectivity, and hamiltonian path on tournaments. Ghosh and Kuchlous [11] improved upon their results for the connectivity-based problems by designing single-pass semi-streaming algorithms for each of them. They also gave new algorithms for hamiltonian cycle and FAST, and established lower bounds for multiple problems including (exact and approximate) FAST, \(s,t\)-distance, source/sink finding, and the connectivity and DAG-based problems. All these works considered the respective tournament problems in the two-party communication model in order to establish lower bounds. Mande, Paraashar, Sanyal, and Saurabh [42] recently studied the communication complexity of multiple tournament problems including king finding, source finding, and maximum degree, giving both upper and lower bounds.
The connectivity- and DAG-based problems on general digraphs have been studied in the streaming and communication models by multiple works [8], [15], [17], [43]–[46]. These works mostly studied lower bounds for the problems, with the best-known ones being \(\Omega(n^2)\) space for a single pass, \(\Omega(n^{2-o(1)})\) space for \(O(\sqrt{\log n})\) passes, and \(\Omega(n^{1+\Omega(1/p)})\) space for \(p\) passes, thereby needing at least \(\Omega(\log n/\log \log n)\) passes for semi-streaming algorithms. The \(s,t\)-reachability problem is the only one among them (to the best of our knowledge) that has a non-trivial pass upper bound for semi-streaming algorithms: \(O(n^{1/2+o(1)})\) passes suffice [43]. On arbitrary graphs under W-streams (allowing outputs to be streamed), Laura and Santaroni lauraS11? studied SCC decomposition obtaining an \(O(n)\)-pass \(O(n\log n)\)-space algorithm.
Graur et al. [47] showed that a directed graph can be fully learned up to cycle reversals via \(O(n^2)\) cut queries,6 which implies exponential-time \(O(n^2)\)-cut-query algorithms for directed global- and \(s,t\)-minimum cut. They, however, did not mention a concrete polynomial-time algorithm that generates such a digraph, which would have then implied our [cor:quadcutq]. Cunningham [30] proved a statement similar to [cor:quadcutq] using general techniques for submodular function minimisation; we use simpler techniques specific to graphs. We are not aware of any prior work that studied tournaments in the cut-query model. The undirected cut-query model has been recently studied extensively [18], [21]–[24], [37], [47], [49]–[51], BlikstadBEMN22?.
Frank and Gyárfás [52] studied the problem of orienting the edges of an undirected graph so as to satisfy target upper and lower bounds on the vertex in- and out-degrees, a generalised version of our main problem (1). They mentioned an algorithm for this problem that flips directed paths and also remarked that the problem can be solved using network-flows, but did not specify the algorithm. While they might have alluded to an algorithm similar to ours, the final result we get for general digraphs ([thm:gendig-comb]) is novel. We also note that Coppersmith et al. [53] proved that the indegree sequence of a tournament suffices in achieving a \(5\)-approximation to FAST. The problems of optimal linear arrangement (OLA) and cutwidth have been widely studied from the perspective of computational complexity as well as fixed parameter tractability (FPT) [9], [10], [54]–[56].
We state some notation and terminology that we use throughout the paper. The notation \(\widetilde{O}(f)\) hides factors polylogarithmic in \(f\). For \(a\in \mathbb{N}\), we have \([a]:=\{1,\ldots,a\}\). Unless otherwise specified, a general digraph is denoted by \(G = (V, E)\) where \(|V| = n\) and \(|E| = m\). The skeleton of a digraph is its underlying undirected graph, and is denoted by \(\mathsf{S}= (V,\widetilde{E})\) where \(\widetilde{E}= \{\{u, v\}: (u, v)\in E\}\) is a multiset—allowing \(\mathsf{S}\) to contain up to two parallel edges (corresponding to directed \(2\)-cycles in \(G\)). For a vertex \(v\), we use \(d_{\text{in}}(v, G)\) and \(d_{\text{out}}(v, G)\) to denote the indegree and outdegree of \(v\) respectively in the digraph \(G\). We simply write \(d_{\text{in}}(v)\) and \(d_{\text{out}}(v)\) if the graph \(G\) is clear from the context. The vector \(\mathbf{d}\) is an \(n\)-length sequence of non-negative integers and may denote the indegree sequence of a graph, given by \(\langle d_{\text{in}}(1),\ldots, d_{\text{in}}(n)\rangle\) where the vertex set is \([n]\). We use \(\mathcal{G}[\mathsf{S}, \mathbf{d}]\) to denote the equivalence class of all graphs that have skeleton \(\mathsf{S}\) and indegree sequence \(\mathbf{d}\). We say that two graphs \(G_1\) and \(G_2\) are related, i.e., \(G_1 \sim G_2\) iff both of them have the same skeleton and indegree sequence. Unless otherwise specified, a cut refers to a directed cut. Given a vertex subset \(U\) of a digraph, the cut size of \(U\), i.e., the number of edges incoming to \(U\), is given by \(\overleftarrow{\mathcal{C}}_G(U):=|\{(v,u) \in E(G) : u\in U\}|\). We often refer to cut sizes by simply “cuts”. For a directed graph \(G\), we define its cut profile as the set \(\{(U,\overleftarrow{\mathcal{C}}(U)): U\subseteq V\}\). The number of edges outgoing from \(U\) is given by \(\overrightarrow{\mathcal{C}}_G(U):=|\{(u,v) \in E(G) : u\in U\}|\)
We describe the algorithmic models that appear in this work.
The undirected cut-query model was introduced by Rubinstein, Schramm, and Weinberg [24]. Here, we define the analogous directed cut-query model [47], [48]. We are given query access to an oracle that holds a digraph \(G=(V,E)\), where we know \(V\) but not \(E\). Upon a query \(U\subseteq V\), the oracle returns \(\overleftarrow{\mathcal{C}}_G(U)\), the number of edges incoming to \(U\) in \(G\). The goal is to solve a problem on \(G\) by making as few queries as possible.
Equivalently, we could define the model as returning \(\overrightarrow{\mathcal{C}}_G(U)\), the number of edges outgoing from \(U\), but since \(\overleftarrow{\mathcal{C}}_G(U) = \overrightarrow{\mathcal{C}}_G\left(V\setminus U\right)\), WLOG and incurring at most a factor of \(2\) in the number of queries, we can assume that we have access to just one type of queries. We drop the subscript \(G\) if the graph is clear from the context.
In this paper, we only focus on the insert-only streaming setting and define only this variant. Here, we have an input digraph \(G=(V,E)\), where the vertex set \(V=[n]\) and the elements of the edge set \(E\) arrive one by one. The input graph and the stream order are chosen adversarially (worst case). The goal is to make one or a few passes over the stream elements, store as few bits of information as possible, and after the final pass, run a post-processing algorithm on the stored data to generate an output. The goal is to minimise the space usage and the number of passes. The semi-streaming model [17] restricts the space usage to \(\widetilde{O}(n)\). In this work, we only deal with single-pass algorithms.
We study graph problems in the two-player communication model of Yao [57]. Here, players Alice and Bob both know the vertex set \(V\) and receive disjoint edge sets \(E_A, E_B \subseteq V\times V\) respectively. They send messages to each other (possibly over multiple rounds) to compute \(\mathcal{F}(G)\) for some relation \(\mathcal{F}\) defined on the graph \(G=(V, E_A\sqcup E_B)\). The communication cost of a protocol for \(\mathcal{F}\) is defined as the maximum number of bits exchanged by the players, over all possible inputs \((E_A,E_B)\). If the protocol is randomised, then the maximum is also taken over all possible random strings used by the players. The communication complexity of a relation \(\mathcal{F}\) is the minimum communication cost over all protocols that return a valid output for \(\mathcal{F}\) on all inputs. If the protocol is randomised, we require the answer to be correct on all inputs with probability at least \(2/3\) over the randomness of the players’ random strings. All our protocols in this paper are deterministic and single-round, i.e., Alice sends a single message to Bob, following which he returns the output. Our lower bounds hold even for the stronger model allowing randomness and unlimited rounds of interaction.
Fact 1 (Sparse recovery [58], gilbertI10?). Given streaming updates to a vector \(\mathbf{x}\in [-M,M]^N\), there is a deterministic \(O(k\cdot\mathop{\mathrm{polylog}}(M,N))\)-space algorithm that, at the end of the stream, recovers \(\mathbf{x}\) in polynomial time if \(\mathbf{x}\) has at most \(k\) non-zero entries.
Fact 2 (Undirected Graph Recovery [24]). Given cut-query access to an undirected graph \(G\) on \(n\) nodes and \(m\) edges, there is a deterministic \(O(\min(m\log n, n^2))\)-query algorithm that recovers \(G\).
We formally define some problems considered in this paper. The input to each of them is a digraph \(G = (V,E)\).
\(s,t\)-Reachability: Given \(s,t\in V\), is there a directed path from \(s\) to \(t\)?
Strong connectivity: Does each node have a directed path to every other node?
SCC decomposition: Partition of the vertex set \(V\) into \(V_1, \ldots, V_\ell\) such that each \(V_i\) induces a strongly connected component (SCC), i.e., a maximal subgraph that is strongly connected.
Acyclicity testing: Is there a directed cycle in \(G\)?
Topological sorting: Given that \(G\) is a DAG, output an ordering of \(V\) such that for each edge \((u,v)\in E\), \(u\) appears (somewhere) before \(v\) in the ordering.
Minimum cut: Find the size of the smallest directed cut, i.e., \(\min_{U\subseteq V} \overleftarrow{\mathcal{C}}(U)\).
Minimum \(s,t\)-cut: Find the size of the smallest directed cut whose removal makes \(s\) unreachable from \(t\), i.e., \(\min \{\overleftarrow{\mathcal{C}}(U): U\subseteq V: s\in U, t\not\in U \}\).
For an ordering \(\sigma\) of the digraph nodes, the width of \(\sigma\) is defined as the maximum cut value over the prefixes of \(\sigma\). The cutwidth of the digraph is the minimum width over all vertex orderings, i.e., \[\text{cutwidth}(G):=\min_{\sigma\in S_n} \left\{\max_{\text{prefix P of }\sigma} \overleftarrow{\mathcal{C}}(P) \right\}.\]
Optimal Linear Arrangement (OLA) is a vertex ordering that minimises the sum (rather than maximum) of the prefix-cut values, i.e., \[\mathsf{OLA}(G):=\text{argmin}_{\sigma\in S_n} \left\{\sum_{\text{prefix P of }\sigma}\overleftarrow{\mathcal{C}}(P) \right\}.\] Equivalently, it is an ordering that minimises the sum of the stretches of the induced back edges [10].
For each of cutwidth and OLA, we refer to the problem version that asks for the value and the one that asks for the ordering as its “value version” and “ordering version” respectively.
Recall that \(\mathcal{G}[\mathsf{S},\mathbf{d}]\) is the equivalence class of all graphs with skeleton \(\mathsf{S}\) and indegree sequence \(\mathbf{d}\). Two graphs \(G_1\) and \(G_2\) are related, i.e., \(G_1 \sim G_2\), iff both have the same skeleton and indegree sequence, i.e., both belong to the same equivalence class. We prove the following general lemma that implies our main theorems.
Lemma 1.
For any two digraphs \(G_1\) and \(G_2\), we have \(G_1 \sim G_2\) iff there is a set of cycles in \(G_1\), flipping the directions of which yields \(G_2\).
Given an undirected graph \(\mathsf{S}\) on \(n\) nodes and \(m\) edges and a sequence \(\mathbf{d}\) of \(n\) non-negative integers, we have an \(O(m^{1+o(1)})\)-time deterministic algorithm that outputs a directed graph from \(\mathcal{G}[\mathsf{S},\mathbf{d}]\) if \(\mathcal{G}[\mathsf{S},\mathbf{d}]\) is non-empty, and otherwise outputs \(\bot\).
We first prove 1 (1), which characterises graphs based on skeleton and indegree sequence.
Proof of 1 (1). The “if” direction is straightforward. Given any \(v\in V\), each cycle in \(G_1\) has one edge outgoing from \(v\) and one edge incoming to \(v\). Therefore, reversing a cycle preserves the indegree of vertex \(v\). Also, reversing the direction of a cycle does not change the skeleton of the graph. Hence, if \(G_2\) is obtained by reversing cycles in \(G_1\), the graphs \(G_1\) and \(G_2\) must have the same skeleton and indegree sequence, i.e., \(G_1\sim G_2\).
For the “only if” direction, let us first fix some notation. For a subset of undirected edges \(H\) in the skeleton of a digraph \(G\), let \(H[G]\) denote the directed subgraph of \(G\) induced by \(H\) (i.e., edges in \(H\) oriented as in \(G\)).
Here, \(G_1\) and \(G_2\) have the same skeleton, say \(\mathsf{S}\). Let \(F\) be the set of (undirected) edges in \(\mathsf{S}\) that have opposite directions in \(G_1\) and \(G_2\). Let \(\overline{F}:= \mathsf{S}\setminus F\). Fix any vertex \(v\in V\). We have \[\begin{align} \label{eq:indegGprime} d_{\text{in}}(v, G_2) = d_{\text{in}}(v, F[G_2]) + d_{\text{in}}(v, \overline{F}[G_2]) = d_{\text{out}}(v, F[G_1]) + d_{\text{in}}(v, \overline{F}[G_1]) \end{align}\tag{1}\] The second equality follows since precisely the edges in \(F\) have opposite directions in \(G_1\) and \(G_2\), and the edges in \(\overline{F}\) have the same direction in \(G_1\) and \(G_2\). Again, \[\begin{align} \label{eq:indegG}d_{\text{in}}(v, G_1) = d_{\text{in}}(v, F[G_1]) + d_{\text{in}}(v, \overline{F}[G_1]) \end{align}\tag{2}\] But since \(G_1\) and \(G_2\) have the same indegree sequence, \(d_{\text{in}}(v,G_1)=d_{\text{in}}(v,G_2)\). Hence, from 1 and 2 , we get \(d_{\text{out}}(v, F[G_1]) = d_{\text{in}}(v, F[G_1])\). Since this is true for all \(v\in V\), \(F[G_1]\) is an Eulerian circuit, a collection of edge-disjoint cycles. We can obtain \(G_2\) from \(G_1\) by precisely reversing \(F[G_1]\). ◻
Therefore, if a graph property is invariant under cycle reversal, then the skeleton and the indegree sequence suffice in determining it.
We note that if a property is not invariant under cycle reversal, then the skeleton and the degrees alone cannot decide the property. Assume to the contrary that there is a property \(\mathcal{P}\) that is not invariant under cycle reversal, but there is an algorithm that decides it from only the skeleton and the indegree information. By definition of \(\mathcal{P}\), there must exist graphs \(G\) and \(G'\) such that \(G'\) is obtained by reversing cycles of \(G\), but \(\mathcal{P}\) has different answers on \(G\) and \(G'\). By 1 (1), \(G\sim G'\). Therefore, they have the same skeleton, say \(\mathsf{S}\), and the same indegree sequence, say \(\mathbf{d}\). Our algorithm outputs an answer that is a function of only \(\mathsf{S}\) and \(\mathbf{d}\). Thus, it outputs the same answer for \(\mathcal{P}\) on both \(G\) and \(G'\), and hence, must be incorrect on one of them. This shows that the class of cycle-reversal-invariant properties completely characterizes the set of properties determined by the skeleton and the indegrees.
Corollary 1. The set of well-defined properties for the equivalence under skeleton and indegree sequence is exactly the class of properties that are invariant under reversal of cycles.
Remark 3. The characterisation can be equivalently stated with the flipped cycles being “edge-disjoint.” This is because the effect of reversing two overlapping cycles \(C_1\) and \(C_2\) with \(C_1\cap C_2 = F\) can be obtained by reversing the cycle \((C_1\cup C_2) \setminus F\).
1 (1) only implies an exponential-time algorithm for any cycle-reversal-invariant problem when we are given the skeleton and indegree sequence of the input digraph: we brute force over all orientations of the given skeleton and find one that satisfies the given indegree sequence. The invariance guarantees that solving the problem on this digraph would give us the solution for the original digraph. Now we focus on generating such a feasible digraph efficiently in polynomial time.
Proof of 1 (2). We describe a polynomial-time algorithm to assign directions to edges in \(\mathsf{S}\) so as to obtain a digraph \(G'\in \mathcal{G}[\mathsf{S}, \mathbf{d}]\). Let \(w(u, v)\) be the number of edges between \(u\) and \(v\) in \(\mathsf{S}\). If \(w(u, v) = 2\), \(G'\) must have both \(\overrightarrow{uv}\) and \(\overrightarrow{vu}\). Therefore, we can assign direction to all such edges.
Ignore all edges whose directions have been marked. Therefore, for remaining edges \(\{u,v\}\) in \(\mathsf{S}\), we have \(w(u, v) =0 \text{ or }1\). Now, we find a flow \(f\) which satisfies the following equations: \[\begin{align} \forall \{u,v\}\in E(\mathsf{S}) &:~~ f(u,v)=-f(v,u)\tag{3}\\ \forall \{u,v\}\in E(\mathsf{S}) &:~~|f(u, v)| \leq w(u, v) &&w(u, v) = 0 \text{ or }1\tag{4}\\ \forall u\in V &: \sum_{v\in N_{\mathsf{S}}(u)} f(u, v) = d_{out}(u) - d_{in}(u)\tag{5} \end{align}\] where \(E(\mathsf{S})\) are the edges in \(\mathsf{S}\) and \(N_\mathsf{S}(u)\) is the neighbourhood of \(u\) in the graph \(\mathsf{S}\).
We check for a feasible flow satisfying these constraints. This is the well-studied circulation problem with vertex demands [59]–[61] and can be solved using any polynomial-time \((s,t)\)-maxflow algorithm in the following way: let us define the demand of a vertex \(u\) to be \(\mathsf{dem}(u) := d_{out}(u) - d_{in}(u)\). We create a source node \(s\) and a sink node \(t\). For each node \(u\) with \(\mathsf{dem}(u) > 0\), we put an edge from \(s\) to \(u\) with capacity \(\mathsf{dem}(u)\). Similarly, for every node \(u\) with \(\mathsf{dem}(u)< 0\), we put an edge from \(u\) to \(t\) with capacity \(-\mathsf{dem}(u)\). Note that this augmentation makes the flow conservation constraints to be \(\forall u\in V: \sum_{v\in N_{\mathsf{S}}(u)} f(u, v) = 0\), which means now we can run an \((s,t)\)-max-flow algorithm on this augmented graph, and the corresponding flow on the original graph will maintain all original constraints. Using the recent breakthrough result of [62], we can solve it deterministically in \(O\left(m^{1+o(1)}\right)\) time. If there is no feasible flow, then we return \(\bot\), announcing that \(\mathcal{G}[\mathsf{S}, \mathbf{d}] = \emptyset\). Observe that if \(\mathcal{G}[\mathsf{S}, \mathbf{d}] \neq \emptyset\) and \(G=(V,E)\in \mathcal{G}[\mathsf{S}, \mathbf{d}]\), then the following flow is feasible. \[f(u,v) = \begin{cases} 1 & \text{if } (u,v) \in E, \\ -1 & \text{if } (v,u) \in E, \end{cases}\] Thus, we shall always find a feasible flow in this case. The contrapositive says that if we do not find a feasible flow, then \(\mathcal{G}[\mathsf{S}, \mathbf{d}]\) must be empty. Hence, we return the correct answer in this case.
Suppose that we do find a feasible flow. Then we describe a strategy to orient the remaining edges to construct a graph \(G\) that we output. As \(w(u, v)\) and \(\mathsf{dem}(u)\) are integers, we know that the flow \(f\) is also integral (therefore, \(f(u, v) > 0 \implies f(u, v) = 1\)). Now for all \(u, v\in V\) such that \(f(u, v) = 1\), we assign direction \(\overrightarrow{uv}\) to edges \(uv\) in \(\mathsf{S}\). Consider the subgraph \(\mathsf{S}'\) of \(\mathsf{S}\) induced by the edges that have not been assigned a direction, i.e., the edges \(\{u,v\}\in \mathsf{S}\) that have flow \(f(u,v)=0\). Because the demand constraint of each node \(v\in V\) has been satisfied, we know that \(d_{\text{in}}(v, \mathsf{S}') = d_{\text{out}}(v, \mathsf{S}')\) for all \(v\in V\). This is equivalent to the fact that the subgraph \(\mathsf{S}'\), i.e., the edges in \(\mathsf{S}\) yet to be assigned directions, must form an Eulerian circuit. We can now find an Euler tour in \(O(m)\) time [63] and orient the edges in \(\mathsf{S}'\) along the direction of the tour. If \(\mathsf{S}'\) is not Eulerian, then we know that \(\mathcal{G}[\mathsf{S}, \mathbf{d}] = \emptyset\). Thus, we ensure that for every vertex \(u\), the in- and out-degree of \(u\) restricted to edges in \(\mathsf{S}'\) are equal. Therefore, we have managed to assign a direction to each edge in \(\mathsf{S}\) without violating the indegree sequence \(\mathbf{d}\). The total runtime is \(O\left(m^{1+o(1)}\right)+O(m) = O\left(m^{1+o(1)}\right).\) ◻
The proof of 1 is now complete. From 1 and 1, we have our main theorem.
Since for any subset of nodes \(U\) of a digraph, the cut size \(\overleftarrow{\mathcal{C}}(U)\) is invariant under cycle reversal, we have the following corollary of [thm:gendig-comb] that is significant from the perspective of cut-query algorithms.
Corollary 2. Given an undirected graph \(\mathsf{S}\) and a sequence \(\mathbf{d}\) of non-negative integers, the cut profiles of all graphs in \(\mathcal{G}[\mathsf{S}, \mathbf{d}]\) are identical.
Although it follows immediately from [thm:gendig-comb], we give an independent direct and simple proof of the statement.
Proof. If \(\mathcal{G}[\mathsf{S}, \mathbf{d}] =\emptyset\), then this is vacuously true. Hence, we assume that \(\mathcal{G}[\mathsf{S}, \mathbf{d}] \neq \emptyset\). Let \(G\) be any graph in \(\mathcal{G}[\mathsf{S}, \mathbf{d}]\). For any \(T\subseteq V\), let \(\mathcal{C}_{\mathsf{S}}(T)\) denote the undirected cut size of \(T\) in \(\mathsf{S}\). Observe that \[\begin{align} &\overrightarrow{\mathcal{C}}_G(T) + \overleftarrow{\mathcal{C}}_G(T) = \mathcal{C}_{\mathsf{S}}(T),\tag{6}\\ &\overrightarrow{\mathcal{C}}_G(T) - \overleftarrow{\mathcal{C}}_G(T) = \sum_{v\in T} (d_{\text{out}}(v) - d_{\text{in}}(v)).\tag{7} \end{align}\] 7 follows since each edge \((u,w)\) inside \(T\) (i.e., both \(u,w\in T\)) contributes to both \(d_{\text{out}}(u)\) and \(d_{\text{in}}(w)\) and cancels. Now, for each \(T\subseteq V\), the values \(\overleftarrow{\mathcal{C}}_G(T)\) and \(\overrightarrow{\mathcal{C}}_G(T)\) are determined by the linearly independent equations (6 ) and (7 ). The RHS of 6 7 are completely determined by \(\mathsf{S}\) and \(\mathbf{d}\). Hence, for fixed \(\mathsf{S}\) and \(\mathbf{d}\), \(\overleftarrow{\mathcal{C}}_G(T)\) and \(\overrightarrow{\mathcal{C}}_G(T)\) are identical for all \(G\in \mathcal{G}[\mathsf{S}, \mathbf{d}]\). ◻
We restate [cor:quadcutq] that captures an important implication as discussed in 1.
Proof. For an input digraph \(G\), we find the indegree profile \(\mathbf{d}\) using \(n\) queries. We recover its skeleton \(\mathsf{S}\) using \(O(n^2)\) queries (2). Then using 1 (2), we generate \(G' \sim G\) in polynomial time and then find the global- or \(s,t\)-min-cut of \(G'\) using any polynomial-time classical algorithm for the problem. By 2, the answer for \(G\) must be the same. ◻
Recall that a tournament graph is one where each pair of vertices shares exactly one directed edge. In other words, a tournament is an oriented complete graph. The indegree sequence of a tournament is also called its score sequence. We obtain the following characterisation of tournaments based on their score sequences.
Corollary 3 (score sequence characterisation). Two tournaments \(T\) and \(T'\) have the same indegree sequence iff \(T\) can be obtained from \(T'\) by only reversing a set of cycles of \(T\).
Proof. Since \(T\) and \(T'\) have the same skeleton (the complete graph), the statement immediately follows from 1 (1). ◻
Again, we have the following implication of [thm:gendig-comb].
[thm:tour-comb] now implies our algorithmic results for tournaments in various computational models.
Proof. Given an input tournament, we can find its indegree sequence in the cut-query model using \(n\) singleton cut queries; in the streaming model, indegree count takes \(O(n\log n)\) space and a single pass; in the communication model, Alice can send Bob \(O(n \log n)\) bits that encode the indegree sequence induced by her edges \(E_A\), from which Bob can compute the indegree sequence induced by all edges \(E_A\sqcup E_B\). Then, by [thm:tour-comb], we can determine the problem \(\mathcal{P}\) with an additive \(n^{2+o(1)}\)-factor overhead on the runtime of a classical algorithm that solves it. ◻
Proof. It is easy to see that reachability, strong connectivity, or in general, any strongly connected component of a graph does not change when cycles in the graph are flipped. Since a DAG has no cycle, the DAG-based properties indeed remain intact. For the vertex ordering problems and cut problems, we note that they are all certain functions of the cuts of a graph. All cuts in the graph are preserved under cycle reversal, and hence all these properties are, in turn, preserved. Therefore, all these problems are invariant under cycle reversal, and since they all have polynomial-time classical algorithms, the upper-bound results follow from [thm:cycinv].
The optimality of the bounds up to a factor of \(\log n\) in each model–including streaming and cut query—follows from \(\Omega(n)\) communication complexity of the problems. By standard streaming-to-communication simulations, an \(S\)-bit communication lower bound for a problem implies an \(S\)-space single-pass lower bound for the same problem in the streaming model. Again, an \(\Omega(n/\log n)\) cut-query lower bound for each problem follows from its \(\Omega(n)\) communication lower bound: a \(C\)-cut-query algorithm for the problem implies an \(O(C\log n)\)-communication protocol for it, since the players can communicate to each other the answer for each query using \(O(\log n)\) bits.
We now justify the \(\Omega(n)\) communication lower bound for each problem. [11] showed such lower bounds for the connectivity-based and the DAG-based problems. The lower bounds on the value versions of the vertex-ordering problems follow via trivial reductions from the acyclicity problem: the cutwidth or the OLA-value of a tournament is zero if and only if it is acyclic. Along similar lines, the lower bounds for their ordering versions follow from the topological ordering problem: the cutwidth-ordering and OLA of an acyclic tournament is also a valid topological ordering of the tournament.
Again, the lower bounds for global- and \(s,t\)-minimum-cut follow via easy reductions from the strong connectivity and \(s,t\)-reachability problems respectively: observe that in any digraph, the minimum cut value is non-zero if and only if the graph is strongly connected. Again, the minimum \(s,t\)-cut value is non-zero if and only if \(s\) is reachable from \(t\). ◻
Define a digraph to be \(k\)-close to tournament if it is obtained by deleting at most \(k\) edges from a tournament. [11] showed that these graphs are some generalisations of tournaments that still admit sublinear-space streaming algorithms for connectivity-based problems. Our results imply a much more general statement.
Proof. For a digraph that is \(k\)-close to tournament, its \(k\) non-edges can be recovered deterministically in the single-pass streaming model using \(O(k\cdot \text{polylog }n)\) space via sparse recovery (1), and the degree information takes an additional \(O(n\log n)\) space. This streaming algorithm can be easily simulated in the communication model along standard lines: Alice runs the algorithm on her edges and sends Bob the algorithm’s memory state at the end of her stream. Given this state, Bob continues the stream with his edges and finds the solution for the entire graph at the end of the stream. The total communication is at most the space usage of the algorithm, which is \(\widetilde{O}(n+k)\).
Now consider the cut-query model. Let \(\mathsf{S}\) be the skeleton of the input graph \(G\). We recover the complement graph \(\overline{\mathsf{S}}\) of \(\mathsf{S}\). Note that \(\overline{\mathsf{S}}\) is an undirected graph on at most \(k\) edges. For each \(U\subseteq V\), we need \(2\) queries to the directed cut oracle on \(G\) to recover the undirected cut \(\mathcal{C}_{\overline{\mathsf{S}}}(U)\) since \(\mathcal{C}_{\overline{\mathsf{S}}}(U) = |\overline{U}| - \overleftarrow{\mathcal{C}}_{G}(U) - \overleftarrow{\mathcal{C}}_{G}(\overline{U})\), where \(\overline{U}:=V\setminus U\). Thus, by 2, we need \(O(k\log n)\) directed cut queries on \(G\) to recover \(\overline{\mathsf{S}}\). Once we do that, we can compute \(\mathsf{S}\). The indegree sequence is obtained by \(n\) additional queries. The results then follows from [thm:gendig-comb]. ◻
This gives us an improvement over a prior result of [11]. They gave an \(\widetilde{O}(2^{\min(k, n)})\)-time algorithms for reachability and strong connectivity, and \(\widetilde{O}(2^n)\)-time algorithms for SCC decomposition and constructing the SCC-graph. This is because they go over every possible “completion” of the almost tournament and on each completion, call a blackbox for tournaments. Our results improve the runtime to polynomial time (in fact, almost-linear \(O(m^{1+o(1)})\) time since SCC-decomposition has a classical \(O(m+n)\)-time algorithm for any digraph).
Finally, we observe the following interesting connection between the semi-streaming and cut-query models with respect to tournament problems.
lemmaqryimplystr If a tournament problem \(\mathcal{P}\) is decidable/solvable by cut queries (regardless of the number of queries), then it has a single-pass \(O(n\log n)\)-space algorithm. More generally, if a problem \(\mathcal{P}\) on a digraph that is \(k\)-close to tournament, is solvable by cut queries, then it has a single-pass \(\widetilde{O}(n+k)\)-space streaming algorithm.
Proof. Given a tournament \(T\), we can store its indegrees in a single-pass using \(O(n\log n)\) space. By 1 (2), this would let us generate in polynomial time a tournament \(T'\) in the same equivalence class as \(T\). Then 2 says that \(T'\) has the same cut profile as \(T\), and so we can now access all cut queries on \(T\) for free.
The “more general” statement follows along similar lines since we can recover the skeleton of a digraph that is \(k\)-close to tournament in \(\widetilde{O}(n+k)\) space (as in the proof of [cor:kclose]). ◻
The contrapositive is also interesting: stronger than semi-streaming lower bounds for a tournament problem would imply its undecidability in the directed cut query model.
By [lem:qry-solve-semi-str], the single-pass semi-streaming model is at least as strong as the cut query model for tournament problems. Can we show that it is strictly stronger? That is, can we exhibit a tournament problem that is solvable in single-pass semi-streaming but not in the cut query model? The answer is yes, as long as the model allows randomness.
Recall that the FAST problem asks to find the minimum Feedback Arc Set in a Tournament, a set of arcs whose removal deletes all cycles. We are interested in the FAST-size.
propositionseparation The problem of finding a \((1+\varepsilon)\)-approximation to FAST-size has a single-pass semi-streaming (randomized) algorithm, but even a \(o(n)\)-approximation is not possible using cut queries.
Proof. The single-pass \((1+\varepsilon)\)-approximation semi-streaming algorithm was given by [8].
For the impossibility, let \(T\) be the tournament on vertex set \([n]\) defined as follows. Add the edge \(n\rightarrow 1\). For remaining pairs \((i,j)\in [n]\times [n]\) with \(i<j\), add the edge \(i\rightarrow j\). Let \(T'\) be the tournament obtained by reversing the cycle \(1\rightarrow 2 \rightarrow\ldots \rightarrow n \rightarrow 1\) in \(T\). Hence, \(T\) and \(T'\) have the same cut profile and any cut-query algorithm must output the same answer for both of them.
In \(T\), the FAST-size is \(1\) (deleting the edge \(n\rightarrow 1\) makes it acyclic). But in \(T'\), the FAST-size \(=\Omega(n)\) since \(T'\) has \(\Omega(n)\) edge-disjoint triangles: for each odd \(i\leq n-2\), we have the triangle \(i\rightarrow i+2 \rightarrow i+1 \rightarrow i\). Hence, \(\alpha\)-approximate FAST-size for \(\alpha=o(n)\) is undecidable by cut queries. ◻
In this paper, we characterised the class of all digraph problems decidable by only its skeleton and indegrees, and consequently the class of all tournament problems decidable by only its score sequence. We also developed a polynomial-time algorithm to generate a feasible digraph satisfying a given skeleton and indegree sequence. We then exhibited a variety of applications of these results in several domains such as streaming algorithms, cut-query algorithms, and communication complexity. The complete characterisation should be influential in future research on these properties, from either an algorithmic or a combinatorial point of view.
One of the immediate future directions is to show that directed minimum cut can be solved by \(\widetilde{O}(n)\) cut queries or, towards hardness, requires \(\Omega(n^2)\) queries. Any of these results will be a breakthrough as directed minimum cut is a great candidate for proving a superlinear \(\mathsf{SFM}\) lower bound—an outstanding question that has remained open for the last five decades [28], [64]–[66]. Because cut queries cannot fully specify edge directions, we conjecture that any improvement of the form \(O(n^{2-\epsilon})\) will require designing a minimum-cut algorithm that does not crucially use the individual edge directions. This will be a departure from the standard combinatorial ways of solving this problem and will be of interest.
Another intriguing future direction is designing streaming algorithms for tournament problems that are not invariant under cycle reversal. We showed that one can obtain the entire cut profile of a tournament in semi-streaming space. Combining this strong tool with other useful sketching and sampling techniques known in the streaming literature, can we resolve the streaming complexities of important tournament problems that remain open? A couple of these problems are (approximate) Feedback Arc Set in Tournaments (FAST) and finding Hamiltonian paths and cycles. For the former problem, we showed a separation between cut-query and semi-streaming: \(o(n)\)-approximation is intractable by cut queries but a \((1+\varepsilon)\)-approximate semi-streaming algorithm exists. However, that algorithm (by [8]) takes exponential time. The best-known polynomial-time single-pass semi-streaming algorithm achieves a \(5\)-approximation simply by sorting with respect to indegrees [53]. Can we improve upon this approximation factor in polynomial time and a single pass?
Finally, we remark that the complexity of each digraph problem studied in this paper is unsettled for general digraphs in the multipass streaming model. In fact, even after a series of works [8], [43], [44], [46], [67] on reachability, there is an exponential gap in the pass-complexity of semi-streaming algorithms for the problem, and it is one of the biggest open problems in multipass streaming (see the survey [68]). Our theorem for arbitrary digraphs provides new insights on the problem, and coupled with sophisticated ideas, might lead to improved multipass algorithms for \(s,t\)-reachability and related problems on general digraphs.
Tennessee Technological University, USA↩︎
University of Birmingham, UK↩︎
Most graph problems turn out to be intractable when restricted to smaller memory [17].↩︎
A function \(f : 2^\mathcal{U}\to \mathbb{R}\) is submodular iff for any \(S, T \subseteq \mathcal{U}\), we have \(f(S) + f(T) \geqslant f(S \cup T) + f(S \cap T)\).↩︎
In fact, the impossibility holds for any number of cut queries; to wit, a directed cycle and its reversal are distinct labelled graphs, but all cut queries have identical answers on both of them.↩︎
We came to know via personal communication that an independent unpublished work by Chakrabarty, Chen, and Khanna [48] also obtained a similar result.↩︎