4
$\begingroup$

The function returns only one answer. But most graphs have more than one possible independent edge set.

g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 1 <-> 5}]
FindIndependentEdgeSet[g]

Mathematica returns {1 <-> 2, 3 <-> 4}. we know that {1,5} {3,4} is an answer too.

How do we list all possible answers?

$\endgroup$
4
$\begingroup$

Could could find independent vertex sets of the line graph.

g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 1 <-> 5}, VertexLabels -> "Name"]

enter image description here

lg = LineGraph[g, 
  VertexLabels -> Thread[Range@EdgeCount[g] -> EdgeList[g]]]

enter image description here

es = FindIndependentVertexSet[lg, Infinity, All]
(* {{3, 5}, {2, 5}, {2, 4}, {1, 4}, {1, 3}} *)

HighlightGraph[g, EdgeList[g][[#]], 
   GraphHighlightStyle -> "Thick"] & /@ es

enter image description here

$\endgroup$
2
$\begingroup$
Select[Subsets[EdgeList[g], {2, EdgeCount[g]}], 
 IndependentEdgeSetQ[g, #] &]

{{1 <-> 2, 3 <-> 4}, {1 <-> 2, 4 <-> 5}, {2 <-> 3, 4 <-> 5}, {2 <-> 3, 1 <-> 5}, {3 <-> 4, 1 <-> 5}}

HighlightGraph[g, #] & /@ %

enter image description here

Note I cut the subset length off at 2, obviously every individual edge is technically/trivially an independent edge set as well (at least according to IndependentEdgeSetQ )

$\endgroup$
  • $\begingroup$ very good solution! $\endgroup$ – bios Oct 4 '16 at 8:57

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.