Блог пользователя xuanquang1999

Автор xuanquang1999, история, 7 лет назад, По-английски

This is a problem I was given back when I'm training for APIO Vietnam team selection.

"There are n (n ≤ 600) factory that is planned to be built on a line, number from 1 to n. There are m (m ≤ 100000) restriction, each restriction has form uv, meaning that if both factory u and v is built, xu + 1 = xv. There are another p (p ≤ 100000) restriction, each restriction has form uv, meaning that if both factory u and v is built, xu ≤ xv. (xi mean coordinate of factory i, if it's going to be built)

Your task is to pick an appropriate coordinate for each factory, such that no restriction is violated, and the number of different coordinate is maximum. (If there's no way to do this, print "-1")

I didn't understand the solution to this problem well back then. And now I'm trying to solve this again, but I can't think of any good idea. Can anyone give me a hint? Thanks in advance.

UDP1: Sorry about the mistaken objective. The correct objective is "the number of distinct point", not "factory".

UDP2: The problem I'm asking is the same with this POI problem (Thanks Swistakk for informing me this). I've updated the statement summary in the blog.

  • Проголосовать: нравится
  • +59
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Constraints?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    I've updated the blog with constraints. I can't believe I forgot to give the constraints in the first place.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can you give a link to the problem?

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

You can combine both constraints to say if you choose x you can't choose y, which means the problem as stated is NP-complete (because you can reduce set cover to it). Is there anything else going on in the statement that you didn't mention?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We can reduce it to NP's but can we reduce any of them to this? Like you mentioned, set cover? If you think it because of "if you choose x you can't choose y" stuff, it doesn't mean it's NP-complete.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +28 Проголосовать: не нравится

      I was thinking in the of case 2 contradictory restrictions are applied to a couple of cities

      Xu +1 = Xv Xv <= Xu

      There is no way to place both of them and keep both satisfied. (Convert every edge (u,v) from set cover to those 2 and it's the same problem).

      The obvious conclusion is that for any pair of nodes you can have only 1 condition. (But that is not mentioned in the statement, so I dunno)

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Even if we calculate maximum independent set, it's not guaranteed to be answer. So your reduction is wrong.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +40 Проголосовать: не нравится

          I believe it is correct, because you don't need that. Let me elaborate:

          Let's say I have a polynomial time solution to the described problem and want to use it as subroutine to my set cover algorithm. I'll take each edge u,v and build two restrictions Xu +1 = Xv, Xv <= Xu. Then I'll ask my subroutine for a solution.

          For any two vertices in the correct solution there are no restrictions at all (because the constraints doesn't allow that) and the ordering on the line is therefore irrelevant. On the other hand, the set of chosen factories is the biggest independent set, because any correct independent set is also a correct factories choice. Note, that this is true because of the specific type of graph I constructed, but that's enough for my need of solving set cover.

          So, in conclusion, if I have a polynomial solution to the described problem then I also have a polynomial solution to set cover.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится -10 Проголосовать: не нравится

            Nope.

            If X1 + 1 = X2, X2 <= X1, X2 + 1 = X3, X3 <= X2, then also X1 + 2 = X3, X3 <= X1.

            That means, in your reduction edges 1-2 and 2-3 (might) induce 1-3.

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

              I don't think that's how the problem works. My reading of the OP is that if you place both u and v, then the relevant constraint must hold (e.g. xu ≤ xv). If you do not place both u and v, the constraint is ignored.

              You've just basically shown that if you want to place all of 1, 2 and 3, then there is a contradiction.

              Since the whole idea of the independent set problem is to pick a set of vertices such that no two of them share an edge, none of the constraints will apply.

              Personally I don't see the problem with the reduction, it looks fine to me. Assuming that my interpretation of how the constraints apply is correct of course. (that is, a constraint applies only when both factories are placed)

              • »
                »
                »
                »
                »
                »
                »
                »
                7 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится

                Ah, sorry. I misunderstood the problem statement given by OP. ania's reduction works. :)

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

wrong (I only thought for assigning coordinates, but we should find maximum assignable subset..)

»
7 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Can we build multiple factories at the same coordinate? Should coordinates be integral?

»
7 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

This problem is weirdly similar to that problem: http://main.edu.pl/en/archive/oi/19/fes Maybe someone was telling you that POI problem and you misheard it?

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

So the variant you give in your post is seemingly NP-Complete (unless constraints apply regardless of whether you place both factories or not?), but if your goal is to find any valid assignment or to solve the problem Swistakk linked then you could look into "Simple Temporal Networks", it's basically a generalization of this problem where you can have arbitrary constraints of the form xu ≤ xv + c.

»
7 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

If the objective is the number of factories — as Alex7 pointed out, (or even when m = 0 this is called feedback vertex set, a well-known NP complete problem) it looks unsolvable.

If the objective is the number of distinct points — add constraints 0 ≤ xi ≤ X for each i. The answer is the minimum possible value of X plus one. This kind of set of inequalities can be reduced to Bellman-Ford.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    How to reduce the set of inequalities to Bellman-Ford (I have understood how to find any valid assignment, but I can't see how to do assignment with maximum number of distinct coordinate).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Link to PDF If I have understood you correctly, what you are talking about is called System of Difference Constraints.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I think I figured how to do assignment with minimum number of distinct coordinate:

        For each restriction of type 1, create arc (u, v, 1) (arc from u to v with weight 1) and arc (v, u,  - 1). For each restriction of type 2, create arc (v, u, 0). Create a new vertex s, and connect s with all other vertex by an arc with weight 0. Run Bellman-Ford algorithm from s, and the answer is the |d| + 1 with d is minimum length of shortest path from s to other vertex.

        I still don't know how to apply that to do assignment with maximum number of distinct coordinate.