METIS_PartGraphKway fails to respect allowed load-imbalance with Metis 5.1

Dear professor Karypis,

I am using your great software since a long time in my code.
It is a really great product and I am really satisfied by its performance and stability.
Recently, I have moved from version 4 to version 5.1 of Metis.
Most of the time, it gives decomposition as good as previous version and allow to treat bigger graphs thanks to better memory management which is great.

Unfortunalely, sometimes, I observed that it is like it fails to decompose respecting the load-imbalance given thru the ubvec vector.
Generally, I use multi-constraints with a value of 1.001 for the first one, and values between 1.05 and 1.10 for the others (between 1 and 4 constraints depending on options used).
When I compute the different weights of each partition after calling METIS_PartGraphKway I notice they are all good except for 1 or few of them for which I observe up to 30% imbalance resulting in a very poor performance of the solver afterwards.
I never observed such behavior with previous Metis version.

Is it something you are already aware?

Do you have some recommendation to avoid such behavior?

Thanks a lot for your kind help,


RE: This is the first time I hear

This is the first time I hear about it. Can you share some of those graphs so that I can take a look at it?


RE: Dear Professor, Did you get

Dear Professor,

Did you get the example I sent you directly yesterday?
Please, let me know if you are able to reproduce on you side.

Thank you for your investigation,


RE: Thank you for your quick

Thank you for your quick answer. I will try to reproduce some example outside of my code to share with you.