Дельта-матроид

В математике дельта-матроид или Δ-матроид — это семейство множеств, подчиняющихся аксиоме обмена, обобщающей аксиому матроидов . Непустое семейство множеств называется дельта-матроидом, если для каждых двух множеств $E$ и $F$ в семье, и для каждого элемента $e$ в их симметричном различии $E\triangle F$ , существует $f\in E\triangle F$ такой, что $E\triangle \{e,f\}$ есть в семье. Для базисных наборов матроида соответствующая аксиома обмена дополнительно требует, чтобы $e\in E$ и $f\in F$ , гарантируя, что $E$ и $F$ имеют одинаковую мощность. Для дельта-матроида любой из двух элементов может принадлежать любому из двух наборов, а также допускается, чтобы эти два элемента были равны. ^{[ 1 ]} Альтернативное и эквивалентное определение состоит в том, что семейство множеств образует дельта-матроид, когда выпуклая оболочка его индикаторных векторов (аналог матроидного многогранника ) обладает свойством, согласно которому каждая длина ребра равна единице или квадратному корню из двух .

Дельта-матроиды были определены Андре Буше в 1987 году. ^{[ 2 ]} Алгоритмы пересечения матроидов и проблема четности матроидов могут быть распространены на некоторые случаи дельта-матроидов. ^{[ 3 ]}^{[ 4 ]}

Дельта-матроиды также использовались для изучения проблем удовлетворения ограничений . ^{[ 5 ]} В частном случае четный дельта-матроид — это дельта-матроид, в котором либо все множества имеют четное количество элементов, либо все множества имеют нечетное количество элементов. Если задача удовлетворения ограничений имеет булеву переменную на каждом ребре плоского графа и если переменные ребер, инцидентных каждой вершине графа, ограничены принадлежностью четному дельта-матроиду (возможно, другому четному дельта-матроиду для каждой вершине), то задачу можно решить за полиномиальное время . Этот результат играет ключевую роль в характеристике плоских задач удовлетворения булевых ограничений, которые можно решить за полиномиальное время. ^{[ 6 ]}

Ссылки

^ Чун, Кэролин (13 июля 2016 г.), «Дельта-матроиды: Происхождение» , The Maroid Union
^ Буше, Андре (1987), «Жадный алгоритм и симметричные матроиды», Mathematical Programming , 38 (2): 147–159, doi : 10.1007/BF02604639 , MR 0904585
^ Буше, Андре; Джексон, Билл (2000), «Системы четности и проблема пересечения дельта-матроида» , Электронный журнал комбинаторики , 7 : R14:1–R14:22, MR 1741336
^ Гилен, Джеймс Ф .; Ивата, Сатору; Мурота, Кадзуо (2003), «Линейная проблема четности дельта-матроида», Журнал комбинаторной теории , серия B, 88 (2): 377–398, doi : 10.1016/S0095-8956(03)00039-X , MR 1983 636
^ Федер, Томас; Форд, Дэниел (2006), «Классификация удовлетворения двудольных логических ограничений посредством пересечения дельта-матроида», SIAM Journal on Discrete Mathematics , 20 (2): 372–394, CiteSeerX 10.1.1.124.8355 , doi : 10.1137/S0895480104445009 , MR 2257268
^ Казда, Александр; Колмогоров Владимир; Ролинек, Михал (декабрь 2018 г.), «Даже дельта-матроиды и сложность плоских логических CSP», Транзакции ACM в алгоритмах , 15 (2): 22:1–22:33, arXiv : 1602.03124 , doi : 10.1145/3230649

[chun-1] Чун, Кэролин (13 июля 2016 г.), «Дельта-матроиды: Происхождение» , The Maroid Union

[bouchet-2] Буше, Андре (1987), «Жадный алгоритм и симметричные матроиды», Mathematical Programming , 38 (2): 147–159, doi : 10.1007/BF02604639 , MR 0904585

[bj-3] Буше, Андре; Джексон, Билл (2000), «Системы четности и проблема пересечения дельта-матроида» , Электронный журнал комбинаторики , 7 : R14:1–R14:22, MR 1741336

[gim-4] Гилен, Джеймс Ф .; Ивата, Сатору; Мурота, Кадзуо (2003), «Линейная проблема четности дельта-матроида», Журнал комбинаторной теории , серия B, 88 (2): 377–398, doi : 10.1016/S0095-8956(03)00039-X , MR 1983 636

[ff-5] Федер, Томас; Форд, Дэниел (2006), «Классификация удовлетворения двудольных логических ограничений посредством пересечения дельта-матроида», SIAM Journal on Discrete Mathematics , 20 (2): 372–394, CiteSeerX 10.1.1.124.8355 , doi : 10.1137/S0895480104445009 , MR 2257268

[kkr-6] Казда, Александр; Колмогоров Владимир; Ролинек, Михал (декабрь 2018 г.), «Даже дельта-матроиды и сложность плоских логических CSP», Транзакции ACM в алгоритмах , 15 (2): 22:1–22:33, arXiv : 1602.03124 , doi : 10.1145/3230649

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]