Search for the longest chains of matching devices

Question

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

I want all compatible devices to be connected to each other as much as possible. (It is not necessary that device a in and b in B be mutually compatible.)

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

In the end, all devices (or all but two, if the "ends" do not match) must be connected together 1 to 1. It is possible to connect any device to any other device. But no device in is compatible with any device in (but they are connected), and the same is 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 the optimal graph.

G does not have to be cyclic, but it can be.

Are there any smart ways to get close to this?

Answer 1

I believe that this problem is NP-complicated due to the reduction from the non-oriented problem of the long path, which is known to be NP-difficult due to the reduction from the problem of the non-oriented Hamiltonian path (see Sipser's Introduction to Computational Theory for more information on why).

In the problem of an undirected long path, we introduce as an undirected graph G = (V, E) together with a pair of nodes u and v and some number k and we want to determine whether or not a simple (no node appears twice) path from u to v of length not less than k. We can transform this into your problem using the polynomial-time reduction as follows:

• For each node v _i & in; V, there is a device in (call it d _i ).
• For each edge {v _i , v _j } & in; 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 a polynomial size, since the total number of generated devices has a size | V | + | E | and the number of connections is 2 | E |. Moreover, we can see that there exists a path of length k from v _i to v _j in column G if there is a chain of devices 2k + 1 in length from d _i to d _j . In particular, if ((v _{i 1} , v _{i 2} ), (v _{i 2} , v _{i 3} ), ..., (v _{i k - 1} , v _{i k} )) this is a simple way from v _i to v _j , then the chain d _{i 1} → e _{i 1 , i 2} → d _{i 2} → e _{i 2 , i 3} → d _{i 3} → ... → e _{i k - 1 , i k} → d _{i k} and vice versa. Thus, we have a reduction in polynomial time from the non-oriented longest path to your problem as follows:

• It is indicated as an input (G, v _i , v _j , k) to the problem of an omnidirectional long path:
  • Build sets A and B, as described above, with C compatibility, as described above.
  • Check if there is a chain of devices 2k + 1 in length from d _i to d _j .
  • If so, print "yes"
  • If not, print "no."

This reduction solves the problem of the non-directional long path in non-deterministic polynomial time using a solver for your problem, so your problem is NP-hard. As a result, you should not expect to find a polynomial-time algorithm for your problem; finding the exact answer is likely to take an exponential time, if only P = NP.

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

Answer 2

This is np-hard, but I think that approximate approximations of the maximum loop can help you (in each group, link devices with an edge of size 0). You can also add an additional node, which connects to all other nodes by weight 0), for example, in this article: Approximation of maximum cycles of the weight cycle in direct graphs with Zero and One weights will help you.