Excogitatoris's blog

Need help with a problem
By Excogitatoris, history, 6 years ago, In English

I have an undirected bipartite graph with N nodes in set A and M nodes in set B, where N <= 50000 and M <= 1000. There can be N * M edges. Each node from set A can mark either zero or two nodes from set B if there is an edge between the node from set A and each of the two nodes from set B. Each node from set B can be marked only once by only one node from set A. I need to find the maximum number of nodes that can be marked from set B.

I'm stuck with this problem. Any kind of help is very much appreciated.

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

»
6 years ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

This is a wrong solution to the problem This is basically maximum matching with the condition that each node in a can connect to two nodes in b. Since the number edges is huge. we can reduce it by connecting all nodes in a to a node and all nodes in b to that node. Then run dinics algorithm complexity O((n + m)sqrr(n + m)).

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you give me hints on how to add edges (capacity?) in the new graph for applying Dinic's algorithm? Also, total number of edges isn't always N * M, only when number of edges is maximum. It seems that if we connect every node in A to a common node and every node in B to that same node then it is helping only when number of edges is N * M. And every node in set A must mark exactly two or zero nodes from set B (marking only one isn't allowed). Are you considering that?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please please share the link. Also, how are the edges given?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am trying to solve "Alien Rhyme" from GCJ Round 1A 2019 using this approach. I am assuming the set of all suffixes as nodes of set A and the indexes of the strings as nodes of set B. I know good analysis and editorials exist for this problem but I was wondering if I could solve it like this anyway. Here is the link to the problem.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          while redusing the problem to a graph problem you lost some important informations about the problem... (hint: if $$$s_i .. s_j$$$ is a common suffix then $$$s_{i+1}..s_j$$$ is also a common suffix)

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't see why that will be a problem. Can you give me an example where this approach will not work?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 2   Vote: I like it +11 Vote: I do not like it

              the reduction is correct (a result for the graph problem is a valid solution for the original problem). But the graph problem is harder to solve than the original problem...

              The problem you are reducing to is the same as "Bimatching" from the last neerc, where the intended solution is in $$$O(n^{5/2})$$$

              → Reply