CODEWITHSUNDEEP
algorithmgraph-theory
WIZARD_
WIZARD_

Reputation: 35

Maximal number of vertex pairs in undirected not weighted graph

Given undirected not weighted graph with any type of connectivity, i.e. it can contain from 1 to several components with or without single nodes, each node can have 0 to many connections, cycles are allowed (but no loops from node to itself).

I need to find the maximal amount of vertex pairs assuming that each vertex can be used only once, ex. if graph has nodes 1,2,3 and node 3 is connected to nodes 1 and 2, the answer is one (1-3 or 2-3).

I am thinking about the following approach:

  1. Remove all single nodes.
  2. Find the edge connected a node with minimal number of edges to node with maximal number of edges (if there are several - take any of them), count and remove this pair of nodes from graph.
  3. Repeat step 2 while graph has connected nodes.

My questions are:

  1. Does it provide maximal number of pairs for any case? I am worrying about some extremes, like cycles connected with some single or several paths, etc.

  2. Is there any faster and correct algorithm?

    I can use java or python, but pseudocode or just algo description is perfectly fine.

Upvotes: 2

Views: 581

Answers (1)

snakile
snakile

Reputation: 54521

Your approach is not guaranteed to provide the maximum number of vertex pairs even in the case of a cycle-free graph. For example, in the following graph your approach is going to select the edge (B,C). After that unfortunate choice, there are no more vertex pairs to choose from, and therefore you'll end up with a solution of size 1. Clearly, the optimal solution contains two vertex pairs, and hence your approach is not optimal.

graph

The problem you're trying to solve is the Maximum Matching Problem (not to be confused with the Maximal Matching Problem which is trivial to solve):

Find the largest subset of edges S such that no vertex is incident to more than one edge in S.

The Blossom Algorithm solves this problem in O(EV^2).

The way the algorithm works is not straightforward and it introduces nontrivial notions (like a contracted matching, forest expansions and blossoms) to establish the optimal matching. If you just want to use the algorithm without fully understanding its intricacies you can find ready-to-use implementations of it online (such as this Python implementation).

Upvotes: 3

Related Questions