MHB Is Creating a Subset of Incompatible Student Pairs a NP-Complete Problem?

[Mikazzum]

Can I start like this? The math is trivial, just a conjecture.
Create a subset of incompatible pairs of students which only names any student once. Put the resulting pairs in two columns. Pick successful room winners by choosing all of either of the columns. Assuming that creates less than 100 names, add one pair at a time, checking both students in the pair for compatibility with the list, discarding incompatible names until you reach 100. Is this P?

 

[Evgeny.Makarov]

Welcome to the forum.

The math is trivial, just a conjecture.

Do you have an answer to your question? The "Challenge Questions and Puzzles" subforum is for questions to which the OP knows the solution. See the https://driven2services.com/staging/mh/index.php?threads/3875/.

Create a subset of incompatible pairs of students

Which pairs of students do you call incompatible?

Pick successful room winners

What room are you talking about?

Is this P?

Is what P? And what do you mean by P?

 

[Mikazzum]

Welcome to the forum.

Do you have an answer to your question? The "Challenge Questions and Puzzles" subforum is for questions to which the OP knows the solution. See the https://driven2services.com/staging/mh/index.php?threads/3875/.

Which pairs of students do you call incompatible?

What room are you talking about?

Is what P? And what do you mean by P?

Sorry Evgeny, I should have articulated better. The problem is that you have 400 students but only 100 of them can have rooms in a dorm. But the dean has complicated matters by giving you pairs of students who are not compatible. You have to come up with a list of 100 students from the 400 which do not contain any of the pairs of incompatible students. The solution is easily verifiable, but the problem is hard to solve in polynomial time.
So we first create a list of compatible students by using a subset of the incompatible pairs which only uses any student's name once. By putting these pairs in two columns either column will only contain compatible students because neither of any pair in anyone column can be in the other column. But the resulting list may be less than 100, so you have to try adding one pair at a time, discarding names which result in an incompatible pair popping up, until one of the columns reaches 100 names.
This approach will eventually yield the 100 students, but the question is if this can be programmed to occur in polynomial time. The number of compatible students in the first stage may be very small and the computational advantage slight.
P stands for "Can be solved and verified in polynomial time" NP stands for "can be verified in polynomial time, but not solved (as yet) in polynomial time". The eventual goal is to prove whether or not P \ne NP

 

[MarkFL]

Sorry Evgeny, I should have articulated better. The problem is that you have 400 students but only 100 of them can have rooms in a dorm. But the dean has complicated matters by giving you pairs of students who are not compatible. You have to come up with a list of 100 students from the 400 which do not contain any of the pairs of incompatible students. The solution is easily verifiable, but the problem is hard to solve in polynomial time.
So we first create a list of compatible students by using a subset of the incompatible pairs which only uses any student's name once. By putting these pairs in two columns either column will only contain compatible students because neither of any pair in anyone column can be in the other column. But the resulting list may be less than 100, so you have to try adding one pair at a time, discarding names which result in an incompatible pair popping up, until one of the columns reaches 100 names.
This approach will eventually yield the 100 students, but the question is if this can be programmed to occur in polynomial time. The number of compatible students in the first stage may be very small and the computational advantage slight.
P stands for "Can be solved and verified in polynomial time" NP stands for "can be verified in polynomial time, but not solved (as yet) in polynomial time". The eventual goal is to prove whether or not P \ne NP

So, are you asking for help with this problem, or do you have a solution and are posting this as a challenge to our community? :D

 

[Mikazzum]

So, are you asking for help with this problem, or do you have a solution and are posting this as a challenge to our community? :D

I do not have a solution to this problem. It is a massive problem well beyond my capabilities. I am nevertheless fascinated by it! The above text is how I would begin this. But I do not know how to progress this further.

 

[Evgeny.Makarov]

The eventual goal is to prove whether or not $P \ne NP$

I need to think whether it is NP-complete, but if your goal is to solve P vs NP, it is surely beyond the level of this forum.

 

[MarkFL]

I do not have a solution to this problem. It is a massive problem well beyond my capabilities. I am nevertheless fascinated by it! The above text is how I would begin this. But I do not know how to progress this further.

Okay thanks, I have moved this thread to our "Computer Science" subforum as NP problems are generally regarded as being a part of computer science. :D

 

[Mikazzum]

Thanks Mark. Sorry I mis posted

 

[Mikazzum]

I need to think whether it is NP-complete, but if your goal is to solve P vs NP, it is surely beyond the level of this forum.

Evgeny, i think this problem is NP complete. I agree P vs NP is way beyond my capability. I hope to see it proved one way or another one day. I don't know if it is beyond the capability of this forum as I am a newbie and there seem to be some pretty good math brains here!

 

[Fallen Angel]

Hi,

I don't think this is an NP problem, taking a fast look at it I think you can simply take the graph where students are vertex and compatibility are edges and then apply DFS algorithm until you reach 100 students, discarding the last vertex when you get an odd length path.

This is just a sketch, if you want to solve it you will need to do this carefully. (I can be totally wrong)

 

[Fallen Angel]

Hi again,

A little observation, I am assuming that in the problem you have $4n$ students and just $n$ can have a room, if the problem is only when $n=100$ it becomes trivial in terms of complexity.

 

[Nono713]

I'll rephrase the problem mathematically here, just so there's no confusion. Let me know if I misunderstood.

INPUT: a non-empty set $S$, a natural number $n \leq \lvert S \rvert$, and a set $P$ of unordered pairs of elements of $S$.

OUTPUT: a subset $S' \subseteq S$ of cardinality $n$ such that for all $\{ i, j \} \in P$ at most one of $i$ or $j$ is in $S'$ (i.e. none, one or the other, but not both).

Actually this definition kind of sucks, I think it would be easier to work in terms of compatibility relation rather than incompatibility relation. Can we make the assumption that the compatibility relation is at least reflexive and symmetric? (I guess it is probably not transitive in the given example)

 

[Fallen Angel]

Hi,

I have probably misunderstood the problem.

Reading again, it seems the problem is like Bacterius said.

Now is harder than I thought, but through the compatibility graph may be related to finding Hamiltonian paths in a graph, which is an NP-complete problem.
Main problem is that the answer, in terms of the compatibility graph can be a set of disjoint subgraphs, and I can't see how to avoid this.