Finding longest chains of matching devices

Question

Set A has n devices. Set B has m devices. Some devices in A are compatible with the devices in B, and some devices in B are compatible with those in A.

I want as many compatible devices connected to each other as possible. (It's not necessary to have the device a in A and b in B to be mutually compatible.)

Edit for clarity: any device can be linked to 0, 1 or 2 other devices, but not itself.

Eventually all devices (or all but two, if the "ends" don't meet) should be linked together 1 on 1. It's possible to link any one device to any other device. But no device in A are compatible with any device in A (but they are linkable), and the same holds true for devices in B.

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

Then the graph G

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

is an optimal graph.

G doesn't have to be cyclic, but it can be.

Are there any clever ways to approach this?

Answer 1

I believe that this problem is NP-hard by a reduction from undirected longest path problem, which is known to be NP-hard by a reduction from the undirected Hamiltonian path problem (see Sipser's Introduction to the Theory of Computation for details on why).

In the undirected longest path problem, we are given as input an undirected graph G = (V, E), along with a pair of nodes u and v and some number k, and want to determine whether or not there is a simple (no node appears twice) path from u to v of length at least k. We can convert this into your problem using a polynomial-time reduction as follows:

• For each node v_i ∈ V, there is a device in A (call it d_i).
• For each edge {v_i, v_j} ∈ V, there is a device in B (call it e_{i, j}).
• For each node v_i and edge {v_i, v_j}, device d_i is compatible with device e_{i, j}.

This reduction has polynomial size, since the total number of devices generated is of size |V| + |E| and the number of connections is 2|E|. Moreover, we can see that there is a path of length k from v_i to v_j in graph G iff there is a chain of devices of length 2k + 1 from d_i to d_j. Specifically, if ((v_i1, v_i2), (v_i2, v_i3), ..., (v_{ik - 1}, v_ik)) is a simple path from v_i to v_j, then the chain d_i1 → e_{i1, i2} → d_i2 → e_{i2, i3} → d_i3 → ... → e_{ik - 1, ik} → d_ik and vice-versa. We thus have a polynomial-time reduction from undirected longest path to you problem as follows:

• Given as input (G, v_i, v_j, k) to the undirected longest path problem:
  • Construct the sets A and B as above, with compatibilities C as above.
  • Check whether there is a chain of devices of length 2k + 1 from d_i to d_j.
  • If so, output "yes"
  • If not, output "no."

This reduction solves the undirected longest path problem in nondeterministic polynomial time using a solver for your problem, and so your problem is NP-hard. As a result, you should not expect to find a polynomial-time algorithm for your problem; finding an exact answer is likely to take exponential time unless P = NP.

Sorry to give a negative answer, but I hope this helps!

Answer 2

This is np-hard but I think a maximal cycle cover problem approximations can help you(in each group link devices with edge of size 0), Also you can add some extra node which connected to all other nodes by weight 0), for example this paper: Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One will help you.