Test in practice on empirical test datasets (let Benoit know if you need more) if it matters and how many of those dangling vertices will actually occur.
Closed this issue · 0 comments
This is a good point. Today, I've played around a little bit with a couple of my instances. In my preliminary experiments the number of dangling vertices was in the order of thousands for hypergraphs with
~100000 vertices and relatively large hyperedges. Since I assume this depends on the structure of the hypergraphs, further experiments using your instances are certainly necessary.
When working with the dual approach, I think we have to keep the following things in mind:
1.) In order to produce correct results, the input hypergraph has to have uniform hypernode and hyperedge weights, otherwise the assignment of the dangling vertices might not lead to the correct solution.
2.) Hyperedges of the dual hypergraph should also have a weight of 1. In the example Lukas posted to the mailing list on Tuesday, the hyperedges were weighted, because they collapsed parallel hyperedges into
one. However, for partitioning the dual hypergraph, this does not make sense (i.e., this information is actually misleading for our problem formulation) and leads to suboptimal cuts (as pointed out in the example).
3.) Parallel hyperdges should be removed from the dual hypergraph for the same reason as in 2.