156:
1661:". MS Thesis. Theorem 3.2.5. This is also Exercise 13.28 in Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dniel Marx, Marcin Pilipczuk, Micha Pilipczuk and Saket Saurabh, "Parameterized Algorithms", Springer, 2016. See also
141:. Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates
1693:
Segal-Halevi, Erel; Aigner-Horev, Elad (2019-01-28). "Envy-free
Matchings in Bipartite Graphs and their Applications to Fair Division".
690:
The above algorithm, in fact, finds an inclusion-minimal Hall violator. This is because, if any vertex is removed from
353:
1605:
Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01). "Envy-freeness in house allocation problems".
1522:
being an empty matching, call the procedure again and again, until either a Hall violator is found, or the matching
25:
126:
1544:
744:
In fact, finding a minimum-cardinality Hall violator is NP-hard. This can be proved by reduction from the
1769:
167:
A Hall violator can be found by an efficient algorithm. The algorithm below uses the following terms:
411:
246:
As an example, consider the figure at the right, where the vertical (blue) edges denote the matching
563:-alternating and it starts and ends with unmatched vertices, so by "inverting" it we can increase
1745:
1694:
1640:
1614:
1585:
1737:
1632:
1658:
1727:
1624:
1676:
32:
1715:
745:
1763:
1749:
1644:
1628:
17:
155:
1584:
Lenchner, Jonathan (2020-01-19). "On a
Generalization of the Marriage Problem".
732:. For example, in the above figure, it returns a Hall violator of size 5, while
1714:
Elffers, Jan; Gocht, Stephan; McCreesh, Ciaran; Nordström, Jakob (2020-04-03).
1741:
1732:
1662:
1636:
1551:
696:, then the remaining vertices can be perfectly matched to the vertices of
687:
is a Hall violator such that each of its subsets is not a Hall violator.
1699:
1590:
1619:
1505:
grow by one vertex. Hence, the algorithm must finish after at most
1468:, and so on. Following these connections must eventually lead to
1552:"Finding a subset in bipartite graph violating Hall's condition"
342:
The algorithm for finding a Hall violator proceeds as follows.
24:
is a set of vertices in a graph, that violate the condition to
1720:
Proceedings of the AAAI Conference on
Artificial Intelligence
756:
The following algorithm takes as input an arbitrary matching
1716:"Justifying All Differences Using Pseudo-Boolean Reasoning"
786:
It returns as output, either a Hall violator that contains
1477:, which is unmatched. Hence we have an M-augmenting path.
468:
is indeed a Hall-violator because of the following facts:
1534:. This provides a constructive proof to Hall's theorem.
184:, is a path in which the first edge is not an edge of
135:. Therefore, there is also no matching that saturates
1659:
Parameterized
Complexity of Minimum k Union Problem
674:
indeed satisfies the definition of a Hall violator.
1516:The procedure can be used iteratively: start with
728:The above algorithm does not necessarily find a
1677:"Bipartite Matching & the Hungarian Method"
752:Finding a Hall violator or an augmenting path
716:, or by edges of the M-alternating path from
8:
492:. Suppose by contradiction that some vertex
679:Finding minimal and minimum Hall violators
1731:
1698:
1618:
1589:
795:, or a path that can be used to augment
597:. This is because all these matches are
154:
1576:
125:is a Hall violator, then there is no
7:
1543:An application of Hall violators in
367:return "There is no Hall violator".
14:
1135:Consider the following two cases:
730:minimum-cardinality Hall violator
1629:10.1016/j.mathsocsci.2019.07.005
1556:Computer science stack exchange
685:inclusion-minimal Hall violator
569:, contradicting its maximality.
129:that saturates all vertices of
741:is a Hall violator of size 3.
389:be the set of all vertices of
1:
1607:Mathematical Social Sciences
1479:Return the M-augmenting path
577:contains all the matches of
104:is the set of neighbors of
1786:
1675:Mordecai J. Golin (2006).
1663:this CS stackexchange post
1528:saturates all vertices of
1382:, it is connected to some
1034:is a Hall violator, since
620:contains another vertex -
352:(it can be found with the
1084:Return the Hall-violator
917:are distinct vertices of
876:are distinct vertices of
777:that is not saturated by
762:in a graph, and a vertex
557:-augmenting path - it is
1733:10.1609/aaai.v34i02.5507
1168:is unmatched, and every
346:Find a maximum matching
297:(or any other vertex of
190:, the second edge is of
1216:must be some vertex of
629:- that is unmatched by
410:(it can be found using
380:be an unmatched vertex.
354:Hopcroft–Karp algorithm
230:-alternating path from
163:Finding a Hall violator
26:Hall's marriage theorem
1545:constraint programming
1204:, the partner of this
196:, the third is not of
159:
1441:is connected to some
976:is connected to some
158:
53:, a Hall-violator in
1462:) by an edge not in
1402:) by an edge not in
710:(either by edges of
412:Breadth-first search
178:, for some matching
1487:At each iteration,
524:be its neighbor in
359:If all vertices of
991:by an edge not in
365:are matched, then
252:. The vertex sets
160:
31:Formally, given a
1325:Go back to step 2
414:; in the figure,
224:, if there is an
218:from some vertex
176:-alternating path
1777:
1754:
1753:
1735:
1726:(2): 1486–1494.
1711:
1705:
1704:
1702:
1690:
1684:
1683:
1681:
1672:
1666:
1655:
1649:
1648:
1622:
1602:
1596:
1595:
1593:
1581:
1566:
1564:
1563:
1533:
1527:
1521:
1512:
1504:
1495:
1476:
1467:
1461:
1457: <
1451:
1440:
1431:
1425:
1417:is connected to
1416:
1407:
1401:
1396: <
1390:
1381:
1364:
1349:
1344:is unmatched by
1343:
1320:
1309:
1277:
1242:
1230:
1221:
1215:
1203:
1194:
1185:
1176:
1167:
1155:
1149:
1134:
1108:
1092:
1081:
1033:
1024:
996:
990:
975:
966:
956:
950:
941:
932:
922:
916:
907:
881:
875:
866:
837:
827:
811:
800:
794:
782:
776:
770:
761:
740:
724:
715:
709:
695:
673:
667:
634:
628:
619:
611:
603:-reachable from
602:
596:
590:
576:
568:
562:
556:
550:
544:
538:
530:. The path from
528:
523:
517:
512:is unmatched by
511:
497:
491:
485:
472:All vertices of
467:
456:
446:
437:
428:
419:
409:
401:-reachable from
400:
394:
388:
379:
364:
351:
338:
330:-reachable from
329:
323:
314:
305:
296:
288:-reachable from
287:
281:
251:
241:
235:
229:
223:
215:
210:
201:
195:
189:
183:
175:
146:
140:
134:
124:
115:
109:
103:
89:
70:
64:
58:
52:
1785:
1784:
1780:
1779:
1778:
1776:
1775:
1774:
1760:
1759:
1758:
1757:
1713:
1712:
1708:
1692:
1691:
1687:
1679:
1674:
1673:
1669:
1657:Aditya Kabra. "
1656:
1652:
1604:
1603:
1599:
1583:
1582:
1578:
1573:
1561:
1559:
1550:
1540:
1529:
1523:
1517:
1506:
1502:
1497:
1493:
1488:
1475:
1469:
1463:
1453:
1450:
1442:
1438:
1433:
1427:
1423:
1418:
1414:
1409:
1403:
1392:
1388:
1383:
1378:
1372:
1366:
1363:
1354:
1345:
1342:
1333:
1311:
1307:
1297:
1288:
1279:
1275:
1265:
1256:
1247:
1241:
1232:
1231:. Denote it by
1228:
1223:
1222:that is not in
1217:
1214:
1205:
1201:
1196:
1192:
1187:
1183:
1178:
1174:
1169:
1166:
1160:
1151:
1148:
1139:
1131:
1124:
1118:
1110:
1109:be a vertex in
1107:
1098:
1097:Otherwise, let
1090:
1085:
1079:
1070:
1061:
1044:
1035:
1031:
1026:
1022:
1015:
1009:
1003:
992:
989:
982:
977:
973:
968:
961:
952:
948:
943:
939:
934:
927:
918:
914:
909:
904:
898:
890:
885:
877:
873:
868:
863:
857:
849:
844:
834:
829:
825:
818:
813:
806:
796:
793:
787:
778:
772:
769:
763:
757:
754:
739:
733:
723:
717:
711:
702:
697:
691:
681:
669:
660:
649:
639:
630:
627:
621:
615:
610:
604:
598:
592:
583:
578:
572:
564:
558:
552:
546:
540:
537:
531:
526:
519:
513:
504:
499:
493:
487:
486:are matched by
478:
473:
463:
452:
445:
439:
436:
430:
427:
421:
415:
408:
402:
396:
390:
384:
378:
372:
371:Otherwise, let
360:
347:
337:
331:
325:
322:
316:
313:
307:
304:
298:
295:
289:
283:
280:
273:
266:
259:
253:
247:
237:
231:
225:
219:
213:
206:
197:
191:
185:
179:
173:
165:
153:
142:
136:
130:
120:
111:
105:
96:
91:
78:
72:
66:
60:
54:
35:
33:bipartite graph
12:
11:
5:
1783:
1781:
1773:
1772:
1762:
1761:
1756:
1755:
1706:
1685:
1667:
1650:
1597:
1575:
1574:
1572:
1569:
1568:
1567:
1548:
1539:
1538:External links
1536:
1500:
1491:
1485:
1484:
1483:
1482:
1473:
1446:
1436:
1426:by an edge in
1421:
1412:
1400: + 1
1386:
1376:
1368:
1358:
1337:
1330:
1329:
1328:
1322:
1319: + 1
1302:
1293:
1283:
1270:
1261:
1251:
1244:
1236:
1226:
1209:
1199:
1190:
1186:is matched to
1181:
1172:
1164:
1150:is matched by
1143:
1136:
1129:
1122:
1114:
1102:
1095:
1088:
1075:
1066:
1057:
1040:
1029:
1020:
1013:
1005:
1000:
999:
998:
984:
980:
971:
958:
946:
942:is matched to
937:
924:
912:
902:
896:
888:
883:
871:
861:
855:
847:
839:
832:
823:
816:
791:
767:
753:
750:
746:Clique problem
737:
721:
700:
680:
677:
676:
675:
658:
655:)| + 1 > |
647:
636:
635:by definition.
625:
613:
608:
581:
570:
535:
502:
476:
460:
459:
448:
443:
434:
425:
406:
381:
376:
369:
357:
335:
320:
311:
302:
293:
278:
271:
264:
257:
244:
243:
203:
164:
161:
152:
149:
94:
84:)| < |
76:
13:
10:
9:
6:
4:
3:
2:
1782:
1771:
1768:
1767:
1765:
1751:
1747:
1743:
1739:
1734:
1729:
1725:
1721:
1717:
1710:
1707:
1701:
1696:
1689:
1686:
1678:
1671:
1668:
1664:
1660:
1654:
1651:
1646:
1642:
1638:
1634:
1630:
1626:
1621:
1616:
1612:
1608:
1601:
1598:
1592:
1587:
1580:
1577:
1570:
1557:
1553:
1549:
1546:
1542:
1541:
1537:
1535:
1532:
1526:
1520:
1514:
1510:
1503:
1494:
1480:
1472:
1466:
1460:
1456:
1449:
1445:
1439:
1430:
1424:
1415:
1406:
1399:
1395:
1389:
1379:
1371:
1361:
1357:
1352:
1351:
1348:
1340:
1336:
1331:
1326:
1323:
1318:
1314:
1305:
1301:
1296:
1292:
1286:
1282:
1273:
1269:
1264:
1260:
1254:
1250:
1245:
1239:
1235:
1229:
1220:
1212:
1208:
1202:
1193:
1184:
1175:
1163:
1158:
1157:
1154:
1146:
1142:
1137:
1133:
1125:
1117:
1113:
1105:
1101:
1096:
1093:
1091:
1078:
1074:
1069:
1065:
1060:
1056:
1052:
1048:
1043:
1039:
1032:
1023:
1016:
1008:
1001:
995:
988:
983:
974:
964:
959:
955:
949:
940:
930:
925:
921:
915:
905:
895:
891:
884:
880:
874:
864:
854:
850:
843:
842:
840:
835:
826:
819:
809:
804:
803:
802:
799:
790:
784:
781:
775:
766:
760:
751:
749:
747:
742:
736:
731:
726:
720:
714:
707:
703:
694:
688:
686:
678:
672:
665:
661:
654:
650:
643:
637:
633:
624:
618:
614:
607:
601:
595:
588:
584:
575:
571:
567:
561:
555:
549:
543:
534:
529:
522:
516:
509:
505:
496:
490:
483:
479:
471:
470:
469:
466:
457:
455:
449:
442:
433:
424:
418:
413:
405:
399:
393:
387:
382:
375:
370:
368:
363:
358:
355:
350:
345:
344:
343:
340:
334:
328:
319:
310:
301:
292:
286:
277:
270:
263:
256:
250:
240:
234:
228:
222:
217:
209:
204:
200:
194:
188:
182:
177:
170:
169:
168:
162:
157:
150:
148:
145:
139:
133:
128:
123:
117:
114:
108:
101:
97:
87:
83:
79:
69:
63:
57:
50:
46:
43: +
42:
38:
34:
29:
27:
23:
22:Hall violator
19:
1770:Graph theory
1723:
1719:
1709:
1700:1901.09527v2
1688:
1670:
1653:
1610:
1606:
1600:
1591:1907.05870v3
1579:
1560:. Retrieved
1558:. 2014-09-15
1555:
1530:
1524:
1518:
1515:
1513:iterations.
1508:
1498:
1489:
1486:
1478:
1470:
1464:
1458:
1454:
1447:
1443:
1434:
1428:
1419:
1410:
1404:
1397:
1393:
1384:
1374:
1369:
1359:
1355:
1346:
1338:
1334:
1324:
1316:
1312:
1303:
1299:
1294:
1290:
1284:
1280:
1271:
1267:
1262:
1258:
1252:
1248:
1237:
1233:
1224:
1218:
1210:
1206:
1197:
1188:
1179:
1170:
1161:
1152:
1144:
1140:
1127:
1120:
1115:
1111:
1103:
1099:
1086:
1083:
1076:
1072:
1067:
1063:
1058:
1054:
1050:
1046:
1041:
1037:
1027:
1018:
1011:
1006:
993:
986:
978:
969:
962:
953:
944:
935:
928:
919:
910:
900:
893:
886:
878:
869:
859:
852:
845:
830:
821:
814:
807:
797:
788:
785:
779:
773:
764:
758:
755:
743:
734:
729:
727:
718:
712:
705:
698:
692:
689:
684:
682:
670:
663:
656:
652:
645:
641:
631:
622:
616:
605:
599:
593:
586:
579:
573:
565:
559:
553:
547:
541:
532:
525:
520:
514:
507:
500:
494:
488:
481:
474:
464:
461:
453:
450:
440:
431:
422:
416:
403:
397:
391:
385:
373:
366:
361:
348:
341:
332:
326:
317:
308:
299:
290:
284:
275:
268:
261:
254:
248:
245:
238:
232:
226:
220:
212:
207:
198:
192:
186:
180:
172:
166:
143:
137:
131:
121:
118:
112:
106:
99:
92:
85:
81:
74:
71:, for which
67:
61:
59:is a subset
55:
48:
44:
40:
36:
30:
21:
18:graph theory
15:
1613:: 104–106.
836: := {}
1620:1905.00468
1571:References
1562:2019-09-08
908:where the
867:where the
820: := {
216:-reachable
151:Algorithms
1750:208242680
1742:2374-3468
1645:143421680
1637:0165-4896
1315: :=
1289: :=
1257: :=
420:contains
395:that are
205:A vertex
1764:Category
1332:Case 2:
1138:Case 1:
1049:+1 >
960:For all
926:For all
841:Assert:
324:are not
127:matching
110:in
90:, where
39:= (
1025:, then
638:Hence,
451:Return
306:), but
47:,
1748:
1740:
1643:
1635:
1365:is in
1353:Since
1159:Since
551:is an
518:. Let
282:, are
202:, etc.
1746:S2CID
1695:arXiv
1680:(PDF)
1641:S2CID
1615:arXiv
1586:arXiv
1452:(for
1391:(for
1062:| ≥ |
899:,...,
858:,...,
668:, so
644:| = |
462:This
1738:ISSN
1633:ISSN
1496:and
1310:and
1278:and
1246:Let
1126:) \
1045:| =
1017:) ⊆
985:<
805:Set
438:and
429:and
383:Let
315:and
20:, a
1728:doi
1625:doi
1611:101
1298:U {
1266:U {
1195:in
1177:in
1053:= |
1002:If
965:≥ 1
951:by
931:≥ 1
892:= {
851:= {
828:},
810:= 0
771:in
725:).
683:An
591:by
545:to
539:to
498:in
236:to
211:is
171:An
119:If
65:of
16:In
1766::
1744:.
1736:.
1724:34
1722:.
1718:.
1639:.
1631:.
1623:.
1609:.
1554:.
1432:.
1408:.
1362:+1
1350:.
1341:+1
1306:+1
1287:+1
1274:+1
1255:+1
1240:+1
1213:+1
1156:.
1147:+1
1106:+1
1082:.
1080:)|
967:,
933:,
812:,
801:.
783:.
748:.
666:)|
447:).
356:).
339:.
274:,
260:,
147:.
116:.
28:.
1752:.
1730::
1703:.
1697::
1682:.
1665:.
1647:.
1627::
1617::
1594:.
1588::
1565:.
1547:.
1531:X
1525:M
1519:M
1511:|
1509:X
1507:|
1501:k
1499:Z
1492:k
1490:W
1481:.
1474:0
1471:x
1465:M
1459:i
1455:j
1448:j
1444:x
1437:i
1435:y
1429:M
1422:i
1420:y
1413:i
1411:x
1405:M
1398:k
1394:i
1387:i
1385:x
1380:)
1377:k
1375:W
1373:(
1370:G
1367:N
1360:k
1356:y
1347:M
1339:k
1335:y
1327:.
1321:.
1317:k
1313:k
1308:}
1304:k
1300:y
1295:k
1291:Z
1285:k
1281:Z
1276:}
1272:k
1268:x
1263:k
1259:W
1253:k
1249:W
1243:.
1238:k
1234:x
1227:k
1225:W
1219:X
1211:k
1207:y
1200:k
1198:Z
1191:i
1189:y
1182:k
1180:W
1173:i
1171:x
1165:0
1162:x
1153:M
1145:k
1141:y
1132:.
1130:k
1128:Z
1123:k
1121:W
1119:(
1116:G
1112:N
1104:k
1100:y
1094:.
1089:k
1087:W
1077:k
1073:W
1071:(
1068:G
1064:N
1059:k
1055:Z
1051:k
1047:k
1042:k
1038:W
1036:|
1030:k
1028:W
1021:k
1019:Z
1014:k
1012:W
1010:(
1007:G
1004:N
997:.
994:M
987:i
981:j
979:x
972:i
970:y
963:i
957:.
954:M
947:i
945:x
938:i
936:y
929:i
923:;
920:Y
913:i
911:y
906:}
903:k
901:y
897:1
894:y
889:k
887:Z
882:;
879:X
872:i
870:x
865:}
862:k
860:x
856:0
853:x
848:k
846:W
838:.
833:k
831:Z
824:0
822:x
817:k
815:W
808:k
798:M
792:0
789:x
780:M
774:X
768:0
765:x
759:M
738:0
735:X
722:0
719:x
713:M
708:)
706:W
704:(
701:G
699:N
693:W
671:W
664:W
662:(
659:G
657:N
653:W
651:(
648:G
646:N
642:W
640:|
632:M
626:0
623:x
617:W
612:.
609:0
606:x
600:M
594:M
589:)
587:W
585:(
582:G
580:N
574:W
566:M
560:M
554:M
548:y
542:x
536:0
533:x
527:W
521:x
515:M
510:)
508:W
506:(
503:G
501:N
495:y
489:M
484:)
482:W
480:(
477:G
475:N
465:W
458:.
454:W
444:2
441:X
435:1
432:X
426:0
423:x
417:W
407:0
404:x
398:M
392:X
386:W
377:0
374:x
362:X
349:M
336:0
333:x
327:M
321:3
318:X
312:3
309:Y
303:0
300:X
294:0
291:x
285:M
279:2
276:X
272:2
269:Y
267:,
265:1
262:X
258:1
255:Y
249:M
242:.
239:z
233:x
227:M
221:x
214:M
208:z
199:M
193:M
187:M
181:M
174:M
144:X
138:X
132:W
122:W
113:G
107:W
102:)
100:W
98:(
95:G
93:N
88:|
86:W
82:W
80:(
77:G
75:N
73:|
68:X
62:W
56:X
51:)
49:E
45:Y
41:X
37:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
