Обхват матроида - Википедия - Matroid girth

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

Примеры

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

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

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

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

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

Определение обхвата двоичный матроид является NP-жесткий.[4]

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

Для произвольного матроида, заданного оракул независимости, невозможно найти обхват с помощью субэкспоненциального числа запросов матроида.[5] Аналогично для вещественного линейного матроида ранга р, с п элементы, описанные оракулом, который дает ориентация любой р-набор элементов, требуется запросы оракула для определения обхвата.[6]

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

Рекомендации

  1. ^ а б Чо, Чон Джин; Чен, Юн; Дин Ю (2007), «О (ко) обхвате связного матроида», Дискретная прикладная математика, 155 (18): 2456–2470, Дои:10.1016 / j.dam.2007.06.015, МИСТЕР  2365057.
  2. ^ а б c Панолан, Фахад; Ramanujan, M. S .; Саураб, Сакет (2015), «О параметризованной сложности задач обхвата и связности на линейных матроидах» (PDF)в Дене, Франк; Мешок, Йорг-Рюдигер; Стеге, Ульрике (ред.), Алгоритмы и структуры данных: 14-й Международный симпозиум, WADS 2015, Виктория, Британская Колумбия, Канада, 5-7 августа 2015 г., Материалы, Конспект лекций по информатике, 9214, Springer, стр. 566–577, Дои:10.1007/978-3-319-21840-3_47.
  3. ^ Донохо, Дэвид Л.; Элад, Майкл (2003), "Оптимально разреженное представление в общих (неортогональных) словарях через ℓ1 минимизация », Труды Национальной академии наук Соединенных Штатов Америки, 100 (5): 2197–2202, Дои:10.1073 / pnas.0437847100, ЧВК  153464, PMID  16576749.
  4. ^ Чо, Чен и Дин (2007) заметим, что это следствие результата Александр Варди в теории кодирования: Варди, Александр (1997), "Невозможность вычисления минимального расстояния кода", IEEE Transactions по теории информации, 43 (6): 1757–1766, Дои:10.1109/18.641542, МИСТЕР  1481035.
  5. ^ Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов свойств матроидов", SIAM Журнал по вычислениям, 11 (1): 184–190, Дои:10.1137/0211014, МИСТЕР  0646772.
  6. ^ Эриксон, Дж .; Зайдель, Р. (1995), "Лучшие оценки снизу для обнаружения аффинных и сферических вырождений", Дискретная и вычислительная геометрия, 13 (1): 41–57, Дои:10.1007 / BF02574027, МИСТЕР  1300508.
  7. ^ Hausmann, D .; Корте, Б. (1981), "Алгоритмические и аксиоматические определения матроидов", Математическое программирование в Обервольфахе (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979), Математическое программирование, 14, стр. 98–111, Дои:10.1007 / BFb0120924, МИСТЕР  0600125.