# partition result violates -ufactor setting

hMetis produces a partition that violates the default -ufactor setting. Consider the following hypergraph, the command, and the result below:

hmetis2.0pre1 graph 2

*******************************************************************************
HMETIS 2.0pre1 Copyright 1998-2007, Regents of the University of Minnesota

HyperGraph Information -----------------------------------------------------
Name: dma.2.graph.index, #Vtxs: 22, #Hedges: 33, #Cons: 1

Options --------------------------------------------------------------------
ptype=rb, ctype=H1, rtype=FAST, otype=cut, dbglvl=8
kwayrefine: No, reconstruct: No, fixed: No
Nruns: 10, NV-cycles: 1, CMaxNet: 50, RMaxNet: 50, Seed: -1
#Parts: 2, UBfactor: 5.00

Partitioning... ------------------------------------------------------------

Bisecting a hgraph of size [vertices=22, hedges=33, balance=0.50]

The mincut for this bisection = 131058.00 (average = 131058.0) (balance = [
0.33]
--------------------------------------------------------------------------
Summary for the 2-way partition:
Hyperedge Cut: 131058.00 (minimize)
Sum of External Degrees: 262116.00 (minimize)
Scaled Cost: 3.25e-03 (minimize)
Absorption: 26.75 (maximize)

Partition Sizes & External Degrees:
(5472299.000)[131058.000] (2752547.000)[131058.000]

Timing Information ---------------------------------------------------------
Partitioning Time: 0.003sec
I/O Time: 0.000sec
*******************************************************************************

If I understand the meaning of ufactor correctly, there is no legal bisection for this graph because there is a vertext with weight 5472299 and the sum of the remaining vertices is 2752547. So the partitioning should fail, right? Is -ufactor a soft constraint or a hard constraint?

33 22 11
5711 1 2
3559 1 19
2252 1 21
4112 2 18
5837 3 4
2507 3 5
5641 3 7
6188 3 8
5646 3 9
1772 3 10
5650 3 11
1404 3 12
5157 3 13
268 3 18
19952 4 14
17107 5 6
24772 7 15
16494 9 16
13975 11 17
3559 19 20
2252 21 22
7597 1 3 18
10641 2 3 18
2887 3 12 13
5451 3 14 18
5641 3 15 18
5122 3 16 18
5239 3 17 18
4112 2 3 10 16
29467 3 6 14 18
20392 3 8 15 18
20122 3 10 16 18
17006 3 12 13 17 18
27334
9823
1155222
102692
74176
75198
126139
65390
76588
21844
87301
39312
83106
193768
210925
185871
200425
5472299
7118
3559
4504
2252

### RE: The ufactor is a soft/hard

The ufactor is a soft/hard constraint that depends on the distribution of the vertex weights. If the weights are such that a balance cannot be achieved, then it becomes more or less a soft constraint, otherwise it is a hard constraint. Of course, in some cases (e.g., graphs that have a very small number of balanced partitions), then the hard constraint can also fail.

### RE: Dear Prof. Karypis, Thanks

Dear Prof. Karypis,

Thanks for your reply. Does hMetis explore different ufactors until a valid partition is found? Why not return a failure if the ufactor constraint is not met, after all it IS a constraint. If ufactor is treated as a soft constraints why not return all-in-one partition with zero cut as the best solution?

Thank you.

Regards,
Bala.

### RE: What hMetis does is based on

What hMetis does is based on the vertex weights it computes a new ufactor for which a partitioning can be computed. If this ufactor is greater than the one supplied it uses it instead of the one provided by the user. So, the ufactor internally is "hard", just under certain cases it can be different from what the user provided.