Maximum cost flow in acyclic tournament

Question

Given a digraph with vertices numbered from $1$ to $n$, where the edge $(i,j)$ exists if and only if $i<j$, which is called an “acyclic tournament with order $n$”. The problem is to find the maximum cost of flow in the graph, in which the cost and weight of each edge are both $1$. The source of the flow is vertex $1$ and the sink is $n$.

An equivalent statement is to choose several paths from $1$ to $n$, where every path contains completely different edges (the intersect of the edge set of any two paths is empty), and to maximize the number of edges in the paths in total. Notice that you don't have to maximize the number of paths.

Take $n=4$ for example, where one of the maximum cost flows are shown below. Entry $a_{ij}$ in the matrix indicates the flow for edge $(i,j)$ (or if the edge is contained in any of the paths, equivalently). More examples in the same format, where $n=5,6,25$, respectively, will be shown at the bottom of the post. Some rule can be discovered by studying these examples. For example, from vertex $2$ it connects with $1$ successive vertex, and the number of the successive vertices are $2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$ for vertex $3, 4, 5, \dots$, respectively.

0111
0001
0001
0000

Since this is a maximum cost flow problem, A program can be written to solve it for given $n$. Actually, the matrices mentioned above are generated by the program. For small $n$ the answer is consistent with the formula $\sum_{k=0}^{n-1} \lceil \sqrt k \rceil$ ($n-1$ in the formula was originally $n$, which was a typo), which is A327672, in which the problem is not mentioned. I suppose that the conjecture can be proved by analyzing the process of the program in this particular graph, but it might make the proof verbose and complicated, which is beyond my ability.

In general, I'd appreciate it if you could prove whether the formula is true or not. Any suggestions and comments are welcome.

n=5
01101
00100
00011
00001
00000

n=6
011101
001000
000101
000011
000001
000000

n=25
0111111111111110000000001
0010000000000000000000000
0001100000000000000000000
0000110000000000000000000
0000011100000000000000000
0000001110000000000000000
0000000111000000000000000
0000000011110000000000000
0000000001111000000000000
0000000000111100000000000
0000000000011100000000001
0000000000001111000000001
0000000000000111100000001
0000000000000011110000001
0000000000000001110000001
0000000000000000111000001
0000000000000000011100001
0000000000000000001110001
0000000000000000000110001
0000000000000000000011001
0000000000000000000001101
0000000000000000000000101
0000000000000000000000011
0000000000000000000000001
0000000000000000000000000

---

Update: I've solved the problem with the help of the comment. However, simpler proofs are still appreciated. By the way, I'm going to add this problem to the OEIS page, so it might appear in the page when you read this post.

Answer 1

As I've said in the comment, I'm going to give a proof to the theorem based on the frame given by @MishaLavrov. However, I'll only give the construction and the details will be ommited, since they are easy to prove but proving them needs lots of time and typing them is too much trouble. Small examples will be given as well since the construction is quite complicated.

First, construct a solution to the problem.

• Let $f_i$ be the flow through the vertex $i$, then $f_i=f_{n+1-i}$.
• For $i = 2, 3, 4, \dots, \lfloor \frac{n}{2} \rfloor$, $f_i = 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots$ ($k$ appears $k$ times), respectively.
• For $n = 2, 3, 4, \dots$, $f_1 = 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 9, 10, 10, 10, 10, \dots$ ($k$ appears $j$ times if $k$ is $j$-th triangular number, otherwise $1$ time), respectively.
• The flow through vertex $i$ comes only from either $1$ or the previous vertices of $i$ and $1$, and goes only to either $n$ or the subsequent vertices of $i$.

Second, write the problem as a linear program and take its dual. The problem can be written as $$ \begin{aligned} & \text{max} & \sum_{i=1}^n \sum_{j=1}^n x_{ij} \\ & \text{s.t.} & \sum_{j=1}^{i-1} x_{j,i} - \sum_{j=i+1}^n x_{i,j} & = 0, 1<i<n \\ & & 0 \le x_{i,j} & \le 1, 1 \le i<j \le n \end{aligned} $$ and its dual is $$ \begin{aligned} & \text{min} & \sum_{i=1}^n \sum_{j=1}^n y_{ij} \\ & \text{s.t.} & z_i - z_j + y_{i,j} & \ge 1, 1 \le i<j \le n \\ & & y_{i,j} & \ge 0, 1 \le i<j \le n \\ \end{aligned} $$ where $z_1$ and $z_n$ are defined as $0$.

Since the constraint can be rewritten as $z_j \le z_i + y_{i,j} - 1$, which is simular to that in the single-source shortest path (SSSP) prblem where $y_{i,j} - 1$ is the length and $z_i$ is the distance (length of shortest path) from $1$ to $i$, the dual can be explained as: given an acyclic tournament with order $n$, choose a non-negative weight for each edge, whose length is defined as its weight minus $1$, so that the distance from $1$ to $n$ is positive, and the goal is to minimize the weights in total.

Third, construct a solution to the dual problem. We can just consider $z_i$ since $y_{i,j}$ can be calculated right after that. Excluding $z_1$ and $z_n$, it satisfies the following properties:

• $z_i=-z_{n+1-i}$.
• If we combine adjacent numbers of the same value into segments, then segment of $d$ $(d>0)$ comes first, and then $d-1, \dots, 1, 0, -1, \cdots, -d$. Negative segments are symmetry with positive ones.
• Let $l_i$ be the length of the segment of $i$, or $0$ if $i$ never exists. For $0 < i \le d$, $l_i-l_{i+1}$ is either $1$ or $2$, where $2$ exists no more than once.
• $l_0-l_1$ is $-1, 0$ or $1$, where $1$ can exist only if no $2$ in the last paragraph exists.
• It can be shown that for every $n$, the values of $z_i$ are unique if we construct them in this way.

Here are some examples of $z_1, z_2, \dots, z_n$ for small $n$.

0 0 0
0 1 -1 0
0 1 0 -1 0
0 1 0 0 -1 0
0 1 1 0 -1 -1 0
0 1 1 0 0 -1 -1 0
0 2 1 1 0 -1 -1 -2 0
0 2 1 1 0 0 -1 -1 -2 0
0 2 1 1 0 0 0 -1 -1 -2 0
0 2 1 1 1 0 0 -1 -1 -1 -2 0
...

It can be proved that both constructions satisfies the constraints, and the values to maximize/minimize for them are both $\sum_{k=0}^{n-1} \lceil \sqrt k \rceil$. According to the duality in linear programming, the answer is exactly $\sum_{k=0}^{n-1} \lceil \sqrt k \rceil$.

By the way, there probably exists simplier proofs, and I'd appreciate it if anyone could give such proof.