wowev15343's blog

Ideas needed regarding graph problem
By wowev15343, history, 4 years ago, In English

We are given a weighted directed graph with $$$N$$$ nodes (<= 40) and $$$M$$$ edges (<= 2000). We need to find the minimum weight sum of a subset $$$S$$$ of the edges such that the edges in $$$S$$$ can be partitioned into some disjoint cycles such that every vertex appears in exactly $$$k$$$ ($$$1 <= k$$$ and $$$k*N <= 100$$$) of these disjoint cycles.

Here's the link to the problem

Any ideas on how to solve this? Thanks in advance.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

I am going to assume, based solely on the last test case, that you are not allowed to visit the same vertex multiple times in a cycle. And I'll assume that "disjoint cycles" means that two cycles aren't allowed to share the same edge, but are allowed to share the same vertex.

In other words you want to find a set $$$S$$$ with minimum sum such that each vertex has $$$k$$$ outgoing and $$$k$$$ incoming edges in $$$S$$$ — can you see why that's equivalent?

Now the problem is a minimum cost flow problem. For every vertex $$$u$$$ in the original graph, we make two vertices $$$u$$$ and $$$u'$$$. Also add a source vertex $$$s$$$ and a sink vertex $$$t$$$. Now we add edges to this flow graph:

  • for every edge $$$u \to v$$$ with cost $$$c$$$ in the original graph, we add an edge $$$u \to v'$$$ with cost $$$c$$$ and capacity 1.
  • for every vertex $$$u$$$ we add an edge $$$s \to u$$$ with cost 0 and capacity $$$k$$$.
  • for every vertex $$$u$$$ we add an edge $$$u' \to t$$$ with cost 0 and capacity $$$k$$$.

Finally, push $$$nk$$$ flow through the graph (alternatively, find the minimum cost maximum flow, it is the same thing in this case). Now, we have a set of edges $$$u \to v'$$$ that have flow going through them — that is the solution to the problem.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks a LOT for the explanation. I couldn't solve this problem in the original contest, I decided to visit it later, and yesterday I realised I still don't know the solution so I should ask :)

    I could find through observation that it is equivalent to the setup that each node should have indegree and outdegree of k, but didn't prove it. Do you have any ideas on how to do that? Should I proceed in a manner similar to proving the degree property for the existence of an Eulerian cycle?

    And I had no ideas about flows. I'm going to learn that to understand the latter part of the explanation. Thanks again!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I'll try to sketch a proof that the conditions are equivalent, but yes, it's related to Eulerians.

      Suppose that we have a set of edges $$$S$$$, with each vertex having $$$k$$$ outgoing and $$$k$$$ incoming edges. We need to show that we can partition this set into disjoint, non-self-intersecting cycles such that each vertex appears in $$$k$$$ cycles.

      Imagine the graph, where we throw out all edges that are not in the set $$$S$$$. Each connected component in this graph has an Eulerian cycle. If we write down the vertices in all of these cycles, each vertex appears $$$k$$$ times.

      Some cycles may contain one vertex multiple times. If we have a cycle that contains the vertex $$$v$$$ multiple times like this:

      $$$u_1, u_2, \ldots, u_n, v, w_1, w_2, \ldots, w_m, v, x_1, \ldots, x_\ell$$$

      then we replace it with two cycles like this:

      $$$u_1, u_2, \ldots, u_n, v, x_1, \ldots, x_\ell \quad \text{and} \quad v, w_1, w_2, \ldots, w_m.$$$

      We repeat this process until no cycle contains the same vertex multiple times.

      At the end, every cycle contains every vertex at most once. Since every vertex still has outdegree and indegree $k$, it follows that every vertex must be involved in $$$k$$$ cycles.

      TLDR: Intuitively speaking, we find an Eulerian cycle (for each component) and then do such replacements until we can't anymore:

      Hopefully the converse statement is clear.

      → Reply