I'm designing fictional fruits. Each fruit has three attributes; color, taste and smell. Also, each of the values of the attributes have some compatibility with the values of the other attributes. So, we get a tri-partite graph. An example is shown below. Here, 1 and 2 are color attributes, 3,4 and 5 are taste attributes and 6 and 7 are smell attributes. Also, color-1 is compatible with taste-3 and smell-6 and so on.
I want to tell if its possible to design a certain number of fruits in a way that all levels of all three attributes are covered. For instance, in the example graph shown above, this isn't possible. The only way to cover color-2 is to connect it with taste-5. But then, 5 connects with smell-6 while 2 connects with smell-7. So, we can't cover color-2 with any fruit while satisfying the constraints dictated by the graph above.
The next natural question once we determine feasibility is of course to actually find the fruits (minimal required). I asked a related question on this here: https://cs.stackexchange.com/questions/134766/triangles-covering-all-vertices-of-a-tri-partite-graph
Best Answer
The feasibility question is easy to answer: you just have to check whether every vertex is in a triangle. This entails checking for every vertex whether the neighbourhood of the vertex is an independent set, which can of course be done in polynomial time.
Finding a minimum triangle cover is hard. More specifically, in the special case when the three color classes have the same cardinality $k$, it is NP-hard to decide whether there is a triangle cover of size $k$, see here. (Note that such a triangle cover must necessarily consist of vertex-disjoint triangles.)
The question is then whether you want an algorithm that can solve small instances in a reasonable time, or one that can give an approximate solution for large instances efficiently. A simple approximation algorithm would be just to take a triangle for each vertex in the graph. Let $OPT$ denote the size of a minimum triangle cover and let $x,y,z$ denote the sizes of the color classes in the graph. The resulting triangle cover has size at most $x + y + z \leq 3 \cdot \max(x,y,z) \leq 3 \cdot OPT$.
You can do better by deleting the edges that are not in a triangle, covering the first color class by $x \leq OPT$ triangles and then finding a minimum edge cover of the bipartite graph induced by the other two color classes. Since every edge is in a triangle, the edge cover gives rise to a set of triangles that covers the last two color classes. Notice that a minimum triangle cover also gives an edge cover of size at most $OPT$, so the minimum edge cover has size at most $OPT$ as well. It follows that the triangle cover we constructed has size at most $2 \cdot OPT$.
For better algorithms (be it approximate or exact), you might want to look up the vertex clique cover problem. Note that a triangle cover gives a vertex clique cover of the same size after deleting overlaps, and conversely, after deleting the edges of the graph that are not in a triangle, any vertex clique cover can be made into a triangle cover of the same size. Finding a minimum clique cover is equivalent to optimally coloring the complement graph, and of course there is a vast literature on (the algorithmic aspects of) graph coloring.