inertial flow accelerated split the graph more than two parts

[zhangan90]

It is designed or just a bug?

[larsgottesbueren]

Not a bug! With vertex separators instead of edge cuts, this is perfectly normal. For most applications this is great because the recursive sub-problems shrink faster at no additional cost. If you need exactly two parts, you can always merge some smaller parts (which are then not connected).

[zhangan90]

@larsgottesbueren thanks for your reply, the experiments in the paper is intriguing, I try to use it in my application.

I need to recursive partition a huge undirected graph into exact two connected parts(trade off for balance and cuts size). I use the code in https://github.com/kit-algo/InertialFlowCutter/blob/master/src/console.cpp#L1850, it enumerate edge cuts as it suggested. But in some test, some edge cuts will cut the graph into three even four part. It this still normal?

As shown in the paper Graph Bisection with Pareto Optimization:

For edge cuts, FlowCutter guarantees that the two sides of the cut are connected subgraphs.

Does InertialFlowCutter violate this feature?

If merge connected small parts, it may break the balance and increase running time. Maybe FlowCutter is more applicable in my application? Any other suggestion?

[larsgottesbueren]

Ok, if you need actual edge cuts, then Inertial Flow and thus Inertial Flowcutter can indeed produce more than two components. This is due to the initialization and piercing. However, the internal balance check still thinks of them as exactly two components, so there must be a combination that fulfills your balance criteria and thus merging should be fine.

Connectedness of each component is a guarantee that only plain FlowCutter gives you -- again only for edge cuts, not separators. If you care about running time, then Inertial FlowCutter is just way faster (and the code has better parallelization).

I'd be interested to hear why you need exactly two parts, if you can share. Usually one doesn't mind more parts if they don't cause any extra cut edges.

[zhangan90]

I compute a multi-level partition with recursive bisection until a target size is achieved. The code is developed with the assumption that connectedness of each part is a guarantee. If so, I can just replace the partition algorithm with out any modification.

I will try to merge small parts, thanks for you patient.

[larsgottesbueren]

Sounds good. I'll close this issue for now but feel free to re-open if you encounter anything else.