F - Everywhere is Sparser than Whole (Judge) Editorial by ygussany
This problem can be solved by combination of the bipartite matching (maximum flow) problem and the strongly connected component decomposition. This is an advanced application of the so-called Dulmage–Mendelsohn (DM) decomposition.
Existence of an induced subgraph of density more than $D$.
We first consider how to test the existence of an induced subgraph of density more than \(D\). Suppose that there exists a non-empty proper vertex subset \(X\) such that the induced subgraph by \(X\) is of density more than \(D\). This is equivalent to the condition that there exists a non-empty proper vertex subset \(Y\) such that the number of edges having at least one endpoint in \(Y\) is less than \(D \cdot |Y|\). (The complement of \(X\) corresponds to \(Y\).)
Let us consider the bipartite graph \(H\) representing the incidence relation of vertices and edges in \(G\). That is, \(H\) is a bipartite graph with \((N + DN)\) vertices and \(2DN\) edges obtained as follows: let the two vertex sets of \(H\) be the vertex set and the edge set of \(G\), and for each edge \(e = (u, w)\) of \(G\) add two edges \((u, e)\) and \((w, e)\). We consider the perfect matching problem on this graph \(H\) with vertex capacity \(D\) on the vertex side and vertex capacity \(1\) on the edge side, i.e., finding an edge subset of \(H\) that contains exactly \(D\) edges incident to each vertex-side vertex and exactly \(1\) edge incident to each edge-side vertex. By Hall’s theorem (with a naive extension), what we want to test originally is equivalent to the condition that this vertex-capacitated bipartite graph \(H\) has no perfect matching.
Thus, it suffices to solve the vertex-capacitated bipartite matching problem on \(H\). This can be done in \(\mathrm{O}((DN)^{1.5})\) time by a naive extension of the Hopcroft–Karp algorithm or by Dinic’s algorithm via a reduction to the maximum flow problem.
On the computational complexity
When we reduce the problem to the maximum flow problem and apply Dinic's algorithm, the average of the maximum amount of flows around each vertex is at most $$\frac{D\cdot N + 1 \cdot DN}{N + DN} \le 2.$$ Thus, we can obtain a similar (at most about twice) upper bound of the computational time as application to the usual bipartite matching problem. (See, e.g., this entry, but in Japanese.)
The vertex-capacitated matching problem is reduced to the usual matching problem by creating the capacity values of copies of each vertex, but this naive reduction increases the number of edges as \(\Theta(D^2N)\). Without this explicit reduction, we can apply the Hopcroft–Karp algorithm to \(H\) almost in the same way by dealing with the vertex capacity virtually. The above bipartite graph \(H\) has vertex capacity \(1\) for all the vertices on one side, and we can obtain the same upper bound \(\mathrm{O}((DN)^{1.5})\) of the computational time as usual.
Existence of an induced subgraph of density exactly $D$.
When the above vertex-capacitated bipartite graph \(H\) has a perfect matching, we have to consider how to test the existence of an induced subgraph of density exactly \(D\) other than the entire graph. The existence of a perfect matching in \(H\) means that we can assign exactly \(D\) incident edges to each vertex in \(G\) without overlap. According to the assignment, orient the edges of \(G\) so that “each edge leaves the assigned vertex”, and let \(\vec{G}\) be the resulting directed graph. Then, what we want to test originally is equivalent to the condition that this directed graph \(\vec{G}\) is not strongly connected.
First, suppose that \(\vec{G}\) is not strongly connected. Pick a strongly connected component that has no leaving edge, and let \(X\) be its vertex set. Then, all of the \(D \cdot |X|\) edges assigned to some vertex in \(X\) must connect two vertices in \(X\), so the density of the induced subgraph by \(X\) is at least \(D\). Since we have already concluded that there is no induced subgraph of density more than \(D\), this subgraph is of density exactly \(D\).
Conversely, suppose that there exists a non-empty proper vertex subset \(X\) that induces the subgraph of density exactly \(D\). Then, all of the \(D \cdot |X|\) edges connecting two vertices in \(X\) must be assigned to some vertex in \(X\), so \(X\) has no leaving edge in \(\vec{G}\). Thus, \(\vec{G}\) is not strongly connected.
Since \(\vec{G}\) has \(N\) vertices and \(DN\) edges, the strongly connected component decomposition can be computed in \(\mathrm{O}(DN)\) time. Overall, this problem can be solved in \(\mathrm{O}((DN)^{1.5})\) time in total.
Sample Implementation (Dinic) (C, 1163 ms)
Sample Implementation (Hopcroft–Karp) (C, 83 ms)
posted:
last update: