Обхват матроида

Абстракция графа кратчайших циклов

В теории матроидов , математической дисциплине, обхват матроида — это размер его наименьшего контура или зависимого множества. Обхват матроида — это обхват его дуального матроида . Обхват матроида обобщает понятие кратчайшего цикла в графе, реберной связности графа, множеств Холла в двудольных графах , четных множеств в семействах множеств и общего положения множеств точек. Его трудно вычислить, но для линейных матроидов, параметризованных как рангом матроида , так и размером поля линейного представления, можно использовать метод фиксированных параметров .

Примеры

Термин «обхват» обобщает использование обхвата в теории графов , означая длину кратчайшего цикла в графе: обхват графического матроида такой же, как обхват его базового графа. ^[1]

Обхват других классов матроидов также соответствует важным комбинаторным задачам. Например, обхват ко-графического матроида (или обхват графического матроида) равен реберной связности базового графа, числу ребер в минимальном разрезе графа. ^[1] Обхват трансверсального матроида дает мощность минимального множества Холла в двудольном графе: это набор вершин на одной стороне двудольного графа, который не образует набор конечных точек паросочетания в графе. ^[2]

Любой набор точек в евклидовом пространстве порождает реальный линейный матроид , интерпретируя декартовы координаты точек как векторы представления матроида . Обхват результирующего матроида равен единице плюс размерность пространства, когда базовый набор точек находится в общем положении , и меньше в противном случае. Обхваты реальных линейных матроидов также возникают в сжатом измерении , где та же концепция называется искрой матрицы . ^[3]

Обхват бинарного матроида определяет мощность минимального четного набора, подмножества семейства наборов, которое включает четное число копий каждого элемента набора. ^[2]

Сложность вычислений

Определение обхвата бинарного матроида является NP-трудной задачей . ^[4]

Кроме того, определение обхвата линейного матроида, заданного матрицей, представляющей матроид, является W[1]-сложной задачей , если параметризовано обхватом или рангом матроида, но поддается обработке с фиксированными параметрами, если параметризовано комбинацией ранга и размера базового поля . [ ^2]

Для произвольного матроида, заданного независимым оракулом , невозможно найти обхват, используя субэкспоненциальное число запросов к матроиду. ^[5] Аналогично, для действительного линейного матроида ранга $r$ с $n$ элементами, описанного оракулом, который дает ориентацию любого кортежа из $r$ элементов, для определения обхвата требуются запросы к оракулу. ^[6] $\Омега (n^{r-1})$

Также были рассмотрены вычисления с использованием оракула обхвата (оракула, который сообщает наименьшее зависимое подмножество заданного набора элементов). ^[7]

Ссылки

^ ab Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), «О (со)обхвате связного матроида», Discrete Applied Mathematics , 155 (18): 2456– 2470, doi : 10.1016/j.dam.2007.06.015 , MR 2365057.
^ abc Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (2015), "О параметризованной сложности проблем обхвата и связности на линейных матроидах" (PDF) , в Dehne, Frank; Sack, Jörg-Rüdiger; Stege, Ulrike (ред.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings , Lecture Notes in Computer Science, vol. 9214, Springer, pp. 566– 577, doi :10.1007/978-3-319-21840-3_47, ISBN 978-3-319-21839-7.
^ Донохо, Дэвид Л .; Элад, Майкл (2003), «Оптимально разреженное представление в общих (неортогональных) словарях с помощью ℓ ¹ минимизации», Труды Национальной академии наук Соединенных Штатов Америки , 100 (5): 2197– 2202, Bibcode : 2003PNAS..100.2197D, doi : 10.1073/pnas.0437847100 , PMC 153464 , PMID 16576749 .
^ Чо, Чен и Дин (2007) отмечают, что это является следствием результата Александра Варди в теории кодирования: Варди, Александр (1997), «Неразрешимость вычисления минимального расстояния кода», IEEE Transactions on Information Theory , 43 (6): 1757– 1766, doi :10.1109/18.641542, MR 1481035 .
^ Йенсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184– 190, doi :10.1137/0211014, MR 0646772 .
^ Эриксон, Дж.; Зайдель, Р. (1995), «Лучшие нижние границы обнаружения аффинных и сферических вырождений», Дискретная и вычислительная геометрия , 13 (1): 41–57 , doi : 10.1007/BF02574027 , MR 1300508.
^ Хаусманн, Д.; Корте, Б. (1981), «Алгоритмические и аксиоматические определения матроидов», Математическое программирование в Обервольфахе (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979) , Исследования математического программирования, том. 14, стр. 98–111 , номер документа : 10.1007/BFb0120924, ISBN. 978-3-642-00805-4, МР 0600125.

[ccd-1] Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), «О (со)обхвате связного матроида», Discrete Applied Mathematics , 155 (18): 2456– 2470, doi : 10.1016/j.dam.2007.06.015 , MR 2365057.

[prs-2] Panolan, Fahad; Ramanujan, MS; Saurabh, Saket (2015), "О параметризованной сложности проблем обхвата и связности на линейных матроидах" (PDF) , в Dehne, Frank; Sack, Jörg-Rüdiger; Stege, Ulrike (ред.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015, Proceedings , Lecture Notes in Computer Science, vol. 9214, Springer, pp. 566– 577, doi :10.1007/978-3-319-21840-3_47, ISBN 978-3-319-21839-7.

[3] Донохо, Дэвид Л .; Элад, Майкл (2003), «Оптимально разреженное представление в общих (неортогональных) словарях с помощью ℓ ¹ минимизации», Труды Национальной академии наук Соединенных Штатов Америки , 100 (5): 2197– 2202, Bibcode : 2003PNAS..100.2197D, doi : 10.1073/pnas.0437847100 , PMC 153464 , PMID 16576749 .

[4] Чо, Чен и Дин (2007) отмечают, что это является следствием результата Александра Варди в теории кодирования: Варди, Александр (1997), «Неразрешимость вычисления минимального расстояния кода», IEEE Transactions on Information Theory , 43 (6): 1757– 1766, doi :10.1109/18.641542, MR 1481035 .

[5] Йенсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184– 190, doi :10.1137/0211014, MR 0646772 .

[6] Эриксон, Дж.; Зайдель, Р. (1995), «Лучшие нижние границы обнаружения аффинных и сферических вырождений», Дискретная и вычислительная геометрия , 13 (1): 41–57 , doi : 10.1007/BF02574027 , MR 1300508.

[7] Хаусманн, Д.; Корте, Б. (1981), «Алгоритмические и аксиоматические определения матроидов», Математическое программирование в Обервольфахе (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979) , Исследования математического программирования, том. 14, стр. 98–111 , номер документа : 10.1007/BFb0120924, ISBN. 978-3-642-00805-4, МР 0600125.