The implication “the answer to problem X is Possible” \(\Rightarrow\) “for every subset \(S\) of \(V\), \(\left(\sum_{i\in S}D_i\right)-2e_G(S)\leq \sum_{i\notin S}\min(D_i,e_G(i,S))\) holds” is clear.

Thus, conjecture Y fails exactly when the answer to problem X is Impossible but the inequality condition holds. So, let us first consider an algorithm that checks whether the inequality condition holds.

From now on, we also use \(e_G(i,S)\) for \(i \in S\) (the definition is the same).

Consider an \(S\) that is minimal among those maximizing the quantity \(f(S)=\left(\sum_{i\in S}D_i\right)-2e_G(S)- \sum_{i\notin S}\min(D_i,e_G(i,S))\). If there is an \(i \in S\) with \(D_i \leq e_G(i,S)\), then replacing \(S\) with \(S \setminus \{i\}\) does not decrease \(f(S)\), which contradicts the minimality of \(S\).

Now consider the quantity \(g(S) = \left(\sum_{i\in S}D_i\right)- \sum_{i \in V}\min(D_i,e_G(i,S))\), and let us find its maximum. We have shown that for an \(S\) maximizing \(f(S)\), we may assume \(D_i > e_G(i,S)\) for \(i \in S\); similarly, we may assume the same condition for an \(S\) maximizing \(g(S)\). It follows that the maximum of \(f(S)\) equals the maximum of \(g(S)\).

It remains to check whether the maximum of \(g(S)\) is \(0\), which reduces to a maximum flow problem as follows.

• Consider a graph with vertices \(S,L_1,\ldots,L_N,R_1,\ldots,R_N,T\), with edges as follows.
• An edge \(S \to L_i\) of capacity \(D_i\)
• An edge \(R_i \to T\) of capacity \(D_i\)
• For each edge \((u,v)\) of \(G\), edges \(L_u \to R_v\) and \(L_v \to R_u\) of capacity \(1\)
• The maximum flow from \(S\) to \(T\) is \(\sum_i D_i\) if and only if the maximum of \(g(S)\) is \(0\).

The last equivalence is shown by considering a minimum cut of this graph.

From a maximum flow of the above graph, we can construct a half-integral solution to problem X. Specifically, whenever a flow of \(1\) passes through \(L_u \to R_v\), increase the usage of the edge \((u,v)\) of the original graph by \(0.5\).

Let us make the half-integral solution as close to an integral solution as possible. Consider the graph consisting only of the edges whose current usage is \(0.5\). If this graph has a closed walk of even length (vertices may repeat, but all edges are distinct), setting the usages of its edges alternately to \(0,1,0,1,\ldots\) brings us closer to an integral solution while preserving the degree of each vertex.

Performing this operation as long as possible, the remaining edges form vertex-disjoint cycles of odd length.

Proof: Suppose there is a vertex \(v\) of degree at least \(4\). Since every vertex has even degree, we can take an Euler tour of the connected component containing this vertex. Splitting the Euler tour at \(v\) decomposes it into two or more walks. None of these has even length. However, concatenating two walks of odd length gives a walk of even length, which is a contradiction. Thus, every vertex has degree \(0\) or \(2\), and since there is no cycle of even length either, the remaining edges form vertex-disjoint cycles of odd length.

Next, for each odd half-integral cycle, if there is an edge other than the cycle edges (that is, an edge of usage \(0\) or \(1\)) connecting vertices of that cycle, we can use it to rearrange the solution and shorten the cycle.

For example, if the half-integral cycle is \(a \to b \to c \to d \to e \to a\) and there is an edge \((a,c)\) of usage \(0\), setting the usages of \((a,b),(b,c),(c,d),(d,e),(e,a),(a,c)\) to \(1/2,1/2,0,1,0,1/2\) makes the cycle length \(3\).

Also, if there is an edge connecting two odd half-integral cycles, we can use it to rearrange the solution and eliminate those \(2\) odd cycles.

Performing these operations as long as possible, we reach a state where no edge other than the cycle edges joins two vertices of the same odd cycle, and no edge connects different cycles.

Now suppose that at least \(1\) odd cycle remains. Delete from \(G\) the edges of usage \(0\) in the half-integral solution obtained here. Then, \(G\) satisfies the inequality condition of conjecture Y, while the answer to problem X is Impossible.

Constructing a graph \(G\) of this form from the degree sequence \(D_i\) turns out to be possible by the following procedure.

• First, choose the set \(C\) of vertices that will lie on the odd cycles. The size of \(C\) is an even number that is at least \(6\).
• Decompose \(C\) into odd cycles and set the usage of their edges to \(1/2\). Do not add any other edges within \(C\).
• Add edges of usage \(1\) between \(C\) and \(V \setminus C\) or within \(V \setminus C\), so that the total usage of the edges incident to each vertex \(i\) is \(D_i\).

Here, how the edges within \(C\) are placed does not affect the decision at all. Moreover, if \(C\) has \(8\) or more vertices, we lose nothing by replacing \(C\) with any \(6\) of its vertices. Thus, it suffices to consider the following procedure.

• Take a vertex set \(C\) of size \(6\).
• Construct a graph in which vertices in \(C\) have degree \(D_i-1\) and the other vertices have degree \(D_i\), under the condition that no edge is placed within \(C\).

Next, we narrow down the candidates for \(C\). In fact, when the vertices are arranged in ascending order of \(D_i\), it suffices to consider only \(6\) consecutive vertices as candidates for \(C\).

Proof: Arrange the vertices in ascending order of \(D_i\) and renumber them in this order. Suppose that some vertex set \(C\) admits a graph \(G\) satisfying the conditions. Let \(x=\min(C),y=\max(C)\), and take a solution minimizing \(y-x\). If \(C\) does not consist of \(6\) consecutive vertices, there is a vertex \(z\) with \(x<z<y\) and \(z\notin C\), and we have \(D_x < D_z < D_y\).

Let \(t\) be the number of vertices in \(C\) adjacent to \(z\). Let \(u=x\) if \(t\leq1\) and \(u=y\) if \(t\geq2\), and let \(C'\) be the set obtained from \(C\) by removing \(u\) and adding \(z\). Let \(a_1,\ldots,a_q\) be the vertices in \(C\setminus\{u\}\) adjacent to \(z\). First, delete each edge \((z,a_j)\) and add \((u,a_j)\). Since there is no edge within \(C\), the edges to be added do not exist beforehand. If the edge \((u,z)\) exists, leave it unchanged. This operation decreases the degree of \(z\) by \(q\) and increases the degree of \(u\) by \(q\). Our goal is to decrease the former by \(1\) and increase the latter by \(1\), so we make the following adjustments using vertices in \(W=V\setminus(C\cup\{z\})\).

• Case \(q=0\): In this case \(u=x\), and \(z\) has \(D_z-D_u+1\geq1\) more neighbors in \(W\) than \(u\) does. So, choose one vertex \(b\in W\) adjacent to \(z\) but not to \(u\), delete the edge \((z,b)\), and add \((u,b)\).
• Case \(q=1\): No additional adjustment is needed.
• Case \(q\geq2\): In this case \(u=y\), and \(u\) has \(D_u-D_z+q-1\geq q-1\) more neighbors in \(W\) than \(z\) does. So, choose vertices \(b_1,\ldots,b_{q-1}\in W\) adjacent to \(u\) but not to \(z\), delete each edge \((u,b_j)\), and add \((z,b_j)\).

In every case, we can decrease the degree of \(z\) by \(1\) and increase the degree of \(u\) by \(1\) without creating self-loops or multi-edges. The degrees of the other vertices do not change and there is no edge within \(C'\), so the new graph also satisfies the conditions. However, \(\max(C')-\min(C')<y-x\), which contradicts the minimality.

We have now narrowed the candidates for \(C\) down to \(O(N)\). It remains to determine, for each candidate, whether such a graph actually exists.

In fact, conjecture Y can be used here. The problem for a fixed \(C\) can itself be interpreted as an instance of problem X. Namely, it is the instance with:

• Graph \(G\): the complete graph with the edges within \(C\) removed
• Degree sequence \(D'_i\): \(D'_i=D_i-1\) if \(i \in C\), and \(D'_i=D_i\) otherwise

For graphs of this form, conjecture Y always holds.

We use this to perform the check for each candidate \(C\).

Let \(X\) be the sequence of degrees of the vertices outside \(C\) sorted in descending order, and let \(Y\) be the sequence of degrees of the vertices inside \(C\) sorted in descending order.

First, consider the check for a single pair \(X,Y\). The sets \(S\) that need to be tested in the inequality of conjecture Y are those formed by taking a prefix from each of \(X\) and \(Y\). Here, fix \(L=|Y \cap S|\), and for each \(r=|X \cap S|\), maintain the slack \(v_r\) of the inequality.

In this form, increment and decrement operations on \(X,Y\) can be expressed as range additions on \(v_r\). See the sample solution for the specific formulas.

Moreover, shifting the candidate \(C\) corresponds to increment and decrement operations on \(X,Y\). Letting \(U\) be the size of \(C\) (we have \(U=6\), but we introduce a variable for clarity), the number of operations is \(O(UN)\) in total, counting both decrements on \(X\) and increments on \(Y\).

We can simply try all \(L\) in the range \(0 \leq L \leq U\).

Thus, the check can be performed for all candidates \(C\), and the overall time complexity is \(O(U^2 N \log N)\).

Sample solution (C++)