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

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

Примеры

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

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

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

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

Вычислительная сложность

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

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

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

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

Ссылки

^ Jump up to: ^а ^б Чо, Юнг Джин; Чен, Юн; Дин, Ю (2007), «О (со)обхвате связного матроида», Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR 2365057 .
^ Jump up to: ^а ^б ^с Панолан, Фахад; Рамануджан, М.С.; Саураб, Сакет (2015), «О параметризованной сложности задач обхвата и связности линейных матроидов» (PDF) , Дене, Франк; Зак, Йорг-Рюдигер; Стеге, Ульрике (ред.), Алгоритмы и структуры данных: 14-й международный симпозиум, WADS 2015, Виктория, Британская Колумбия, Канада, 5–7 августа 2015 г., Материалы докладов , Конспекты лекций по информатике, том. 9214, Springer, стр. 566–577, номер документа : 10.1007/978-3-319-21840-3_47 .
^ Донохо, Дэвид Л .; Элад, Майкл (2003), «Оптимально разреженное представление в общих (неортогональных) словарях через ℓ ¹ минимизация», Proceedings of the National Academy of Sciences of the United States of America , 100 (5): 2197–2202, 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, doi : 10.1007/BFb0120924 , MR 0600125 .

[ccd-1] Jump up to: ^а ^б Чо, Юнг Джин; Чен, Юн; Дин, Ю (2007), «О (со)обхвате связного матроида», Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016/j.dam.2007.06.015 , MR 2365057 .

[prs-2] Jump up to: ^а ^б ^с Панолан, Фахад; Рамануджан, М.С.; Саураб, Сакет (2015), «О параметризованной сложности задач обхвата и связности линейных матроидов» (PDF) , Дене, Франк; Зак, Йорг-Рюдигер; Стеге, Ульрике (ред.), Алгоритмы и структуры данных: 14-й международный симпозиум, WADS 2015, Виктория, Британская Колумбия, Канада, 5–7 августа 2015 г., Материалы докладов , Конспекты лекций по информатике, том. 9214, Springer, стр. 566–577, номер документа : 10.1007/978-3-319-21840-3_47 .

[3] Донохо, Дэвид Л .; Элад, Майкл (2003), «Оптимально разреженное представление в общих (неортогональных) словарях через ℓ ¹ минимизация», Proceedings of the National Academy of Sciences of the United States of America , 100 (5): 2197–2202, 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, doi : 10.1007/BFb0120924 , MR 0600125 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]