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

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

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

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

Ссылки

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