1
$\begingroup$

I'm facing difficulties in finding a representation for solving the following graph theory problem :

Two movies are considered related if they have the same director. Given a set of movies I need to find the longest playlist so that for each day exactly 2 related movies are to be watched and any two movies from different days can't be related.

I thought one solution could revolve around bipartite graphs and finding a maximum matching but I didn't get far this way.

Thank you for reading my question, any indication as to how I could solve this problem is greatly appreciated.

Edit: I've forgot to mention that a movie could have multiple directors (for example 2).

$\endgroup$
3
  • $\begingroup$ Isn't the length of the playlist equal to the number of directors who have directed at least two movies on the list? I'm assuming that each movie has exactly one director. This doesn't seem like a graph theory problem to me. Am I overlooking something? $\endgroup$
    – saulspatz
    Apr 24, 2021 at 17:30
  • $\begingroup$ Fair enough, thanks for the answer. I've forgot to mention the fact that a movie could be directed by more than 1 people. $\endgroup$
    – Nick Daniels
    Apr 24, 2021 at 18:27
  • $\begingroup$ Okay, that does make it sound a lot harder. $\endgroup$
    – saulspatz
    Apr 24, 2021 at 19:26

1 Answer 1

Reset to default
0
$\begingroup$

Let the vertices of the graph $G$ be all pairs of movies that share a director. That is, the vertices are the pairs of movies that can be watched on the same day. Two vertices of $G$ are adjacent if they share at least one director. Then the question is, what is the maximum cardinality of an independent set in $G$? (A set of vertices is independent if no two of them are adjacent.)

Maximum independent set is NP-hard, so this is a difficult problem in general.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.