# 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?

Thank your for your help.

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

- Login to post comments

## 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.