1
$\begingroup$

This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers.

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.

Fig 1: fruit graph

I want to design a minimal number of fruits while still covering all attributes (all 2 colors, all 3 tastes and all 2 smells in this case). For example, the example graph above has the following solution (shown with pink lines, fruit-1 has color-1, taste-3 and smell-6; fruit-2 has color-1, taste-4 and smell-7 while fruit-3 has color-2, taste-5 and smell-6; hence covering all levels of all attributes with 3 fruits):

enter image description here

We know this is optimal since there are three tastes and we couldn't have used less than 3 fruits in this case.

The question is: how to design an algorithm to get the minimum number of fruits required and their configurations given a general graph like the one specified above.

Note that it might not have been possible to cover all attributes even if the graph has no isolated vertices and I asked a question on feasibility here: https://math.stackexchange.com/questions/3998648/possible-to-cover-all-vertices-of-a-tri-partite-graph-with-triangles

$\endgroup$
4
  • $\begingroup$ I don't see a question here. We require you to articulate a specific question. $\endgroup$
    – D.W.
    Jan 25 at 3:23
  • $\begingroup$ There is a question: what is the minimum number of fruits required to cover all attributes and what those fruits are. Editing the question to make this clearer. $\endgroup$ Jan 25 at 3:30
  • $\begingroup$ Do you mean 'minimal' or 'minimum' in your question? Finding 'minimal' is simple. $\endgroup$ Jan 26 at 7:38
  • $\begingroup$ @InuyashaYagami - I mean minimum number of triangles that cover all vertices. If that's simple, its great news :) Would be interested in maximal as well just for curiosity. $\endgroup$ Jan 26 at 21:26
2
$\begingroup$

First, let's invent a decision version of your problem, in which a number $t$ is given in addition to the graph, and the goal is to decide whether the vertices in the input graph can be covered with at most $t$ triangles.

If the NP-hard problem 3-dimensional matching (3DM) remains NP-hard under the restriction that $|V|$ is divisible by 3 and the target parameter $k=|V|/3$ (which I consider very likely but don't know for sure), then your problem is also NP-hard by reduction from it:

Given such an instance of 3DM, construct an instance of your problem on the same set of vertices by creating a triangle $abc$ for each 3-tuple $abc$ in the 3DM instance, and setting $t=|V|/3$. Clearly a solution to the 3DM instance corresponds to a solution to the constructed instance of your problem. Such a solution is optimal since all 3-tuples are disjoint. In the reverse direction, if all vertices can be covered using just $|V|/3$ triangles then the triangles must all be disjoint, meaning this corresponds to a valid solution to the original 3DM instance. Together, this means that the answer (YES or NO) is the same to both problem instances. Since the construction is polynomial time, and if the restricted variant of 3DM is NP-hard, so is your problem.

To extend this to a full proof of NP-hardness, one approach would be to try to prove NP-hardness of the restricted variant of 3DM -- e.g., by reducing the general variant to it.

$\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.