xuanquang1999's blog

A hard problem about graph theory(?)
By xuanquang1999, history, 8 years ago, In English

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.

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

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Constraints?

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

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

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

Can you give a link to the problem?

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

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?

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

    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.

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

      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)

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

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

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

          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.

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

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 3   Vote: I like it +15 Vote: I do not like it

              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)

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

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

                → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

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

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

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?

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

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.

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

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.

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

    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).

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

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

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

        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.

        → Reply