How to find maximum number of such pairs of connected edges in a graph that each pair is separated from another pair by at least two edges?

2
votes

I need to find maximum number of pairs of connected edges in a graph such that each pair is separated from every other pair by at least two edges. This could be seen as the maximum matching without the constraint of covering all edges where each component in the alternating path is with length 2.

Clarification of terms:

  1. Connected pairs: Pairs of edges must be in the same connected component.

  2. Connected pairs: Two paired edges do not necessarily need to share a vertex.

  3. Each pair is separated by at least two edges: Given pairs [(u1, v1), (u2, v2)] and [(u3, v3), (u4, v4)], the minimum distance between u ∈ {u1, v1, u2, v2} and v ∈ {u3, v3, u4, v4} is no less than two?

  4. Each pair is separated by at least two edges: Given pairs [(u1, v1), (u2, v2)] and [(u3, v3), (u4, v4)], the minimum distance between, say u1 and u2 can be anything, including zero (the same vertex)?

1
algorithmgraphmatching
As per the comments in j_random_hacker's answer, could you please review the clarification of terms again? – Kittsil

1 Answers

1
votes

The straightforward way to do it would be to create a new graph G' in which you have a vertex for every pair of connected edges in G, and an edge connects two vertices in G' whenever the corresponding edge pairs in G are less than 2 edges apart. You could then look for a maximum independent set in G'.

This is far from ideal, since G' will be huge and independent set is NP-complete. If you can show that G' has some special structure, you might be able to do much better though. E.g., if it is necessarily bipartite, then König's theorem will let you find a maximum independent set in polynomial time using maximum matching. (This will still be very slow in practice, as there could be O(m^2) vertices...)