Матроид-оракул

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

Наиболее часто используемый оракул этого типа — оракул независимости — подпрограмма для проверки независимости набора элементов матроида. Также использовались несколько других типов оракулов; Было показано, что некоторые из них слабее оракулов независимости, некоторые сильнее, а некоторые эквивалентны по вычислительной мощности. ^[1]

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

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

Почему оракулы?

Хотя некоторые авторы экспериментировали с компьютерными представлениями матроидов, в которых явно перечислены все независимые множества или все базисные наборы матроида, ^[4] эти представления не являются краткими : матроид с $\scriptstyle n$ элементы могут расширяться в представление, которое занимает экспоненциальную величину пространства. $\scriptstyle n$ . Действительно, число различных матроидов на $\scriptstyle n$ элементы растут в два раза экспоненциально, поскольку

2^{2^{n}n^{-3/2+o(1)}}

^[5]

из чего следует, что любое явное представление, способное обрабатывать все возможные матроиды, обязательно будет использовать экспоненциальное пространство. ^[6]

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

История

Начиная с Радо (1942) , «функции независимости» или « $\scriptstyle I$ -функции» изучались как один из многих эквивалентных способов аксиоматизации матроидов. Функция независимости отображает набор элементов матроида в число $\scriptstyle 1$ если множество независимо или $\scriptstyle 0$ если он зависим; то есть это индикаторная функция семейства независимых множеств, по сути то же самое, что и оракул независимости. ^[7]

Матроидные оракулы также были частью самых ранних алгоритмических работ по матроидам. Так, Эдмондс (1965) , изучая проблемы разделения матроида, предположил, что доступ к данному матроиду осуществляется через подпрограмму, которая принимает на вход независимый набор $\scriptstyle I$ и элемент $\scriptstyle x$ , и либо возвращает схему в $\scriptstyle I\cup \{x\}$ (обязательно уникальный и содержащий $\scriptstyle x$ , если она существует) или определяет, что такой схемы не существует. Эдмондс (1971) использовал подпрограмму, которая проверяет, является ли данный набор независимым (то есть, в более современной терминологии, оракул независимости ), и заметил, что предоставляемой ею информации достаточно, чтобы найти базис минимального веса за полиномиальное время.

Начиная с работы Корте и Хаусманн (1978) и Хаусманн и Корте (1978) исследователи начали изучать оракулы с точки зрения доказательства нижних границ алгоритмов для матроидов и родственных структур. Обе эти статьи Хаусмана и Корте касались проблемы поиска независимого от максимальной мощности множества, которое легко для матроидов, но (как они показали) труднее аппроксимировать или точно вычислить для более общих систем независимости, представленных оракулом независимости. Эта работа вызвала шквал статей в конце 1970-х и начале 1980-х годов, показавших аналогичные результаты по твердости для задач на матроидах. ^[8] и сравнение силы разных типов матроидных оракулов. ^[9]

С тех пор оракул независимости стал стандартом для большинства исследований матроидных алгоритмов. ^[10] Также продолжались исследования нижних границ, ^[11] и сравнение различных типов оракулов. ^[12]

Виды оракулов

Были рассмотрены следующие типы матроидных оракулов.

Оракул независимости принимает на вход набор элементов матроида и возвращает на выходе логическое значение , истинное, если данный набор является независимым, и ложное в противном случае. ^[13] Его можно легко реализовать на основе базовой структуры, из которой был определен матроид для графических матроидов , трансверсальных матроидов , гаммоидов и линейных матроидов, а также для матроидов, сформированных из них с помощью стандартных операций, таких как прямые суммы. ^[3]
Базовый оракул принимает на вход набор элементов матроида и возвращает на выходе логическое значение, истинное, если данный набор является базовым, и ложное в противном случае. ^[9]
Схемный оракул принимает на вход набор элементов матроида и возвращает на выходе логическое значение, истинное, если данный набор является схемой, и ложное в противном случае. ^[9]
Оракул поиска цепей Эдмондса (1965) принимает на вход независимое множество и дополнительный элемент и либо определяет, что их объединение независимо, либо находит в объединении цепь и возвращает ее.
Оракул ранга принимает на вход набор элементов матроида и возвращает на выходе числовое значение — ранг данного набора. ^[9]
Были рассмотрены три типа оракула закрытия : один, который проверяет, принадлежит ли данный элемент замыканию данного набора, второй, который возвращает замыкание набора, и третий, который проверяет, закрыто ли данное множество. ^[9]
Охватывающий оракул принимает на вход набор элементов матроида и возвращает на выходе логическое значение, истинное, если данный набор является охватывающим (т. е. содержит базис и имеет тот же ранг, что и весь матроид), и ложное в противном случае. ^[14]
Оракул обхвата принимает на вход набор элементов матроида и возвращает на выходе числовое значение — размер наименьшей схемы в этом наборе (или $\scriptstyle +\infty$ если данное множество независимо). ^[14]
для Порт-оракул фиксированного элемента $\scriptstyle x$ матроида принимает на вход набор элементов матроида и возвращает на выходе логическое значение, истинное, если данный набор содержит схему, включающую $\scriptstyle x$ и ложь в противном случае. ^[15]

Относительная сила разных оракулов

Хотя известно множество типов оракулов, выбор которых можно упростить, поскольку многие из них эквивалентны по вычислительной мощности. Оракул $\scriptstyle X$ называется полиномиально сводимым к другому оракулу $\scriptstyle Y$ если есть звонок $\scriptstyle X$ может быть смоделирован алгоритмом, который обращается к матроиду, используя только оракул $\scriptstyle Y$ и занимает полиномиальное время , измеряемое количеством элементов матроида; с точки зрения теории сложности, это сокращение Тьюринга . Два оракула называются полиномиально эквивалентными , если они полиномиально сводимы друг к другу. Если $\scriptstyle X$ и $\scriptstyle Y$ полиномиально эквивалентны, то каждый результат, доказывающий существование или отсутствие алгоритма с полиномиальным временем для задачи матроида с использованием oracle $\scriptstyle X$ также доказывает то же самое для оракула $\scriptstyle Y$ .

Например, оракул независимости полиномиально эквивалентен оракулу поиска цепей Эдмондса (1965) . Если доступен оракул для поиска цепей, набор можно проверить на независимость, используя не более $\scriptstyle n$ вызовы оракула, начиная с пустого набора , добавляя элементы данного набора по одному элементу за раз и используя оракул поиска цепей, чтобы проверить, сохраняет ли каждое добавление независимость набора, который был создан до сих пор. В другом направлении, если доступен оракул независимости, схема в наборе $\scriptstyle I\cup \{x\}$ можно найти, используя не более $\scriptstyle n$ вызовы оракула путем тестирования для каждого элемента $\scriptstyle y\in I$ , ли $\scriptstyle I\setminus \{y\}\cup \{x\}$ является независимым и возвращает элементы, для которых ответ отрицательный. Оракул независимости также полиномиально эквивалентен оракулу ранга, охватывающему оракулу, первым двум типам оракула закрытия и портовому оракулу. ^[1]

Базисный оракул, оракул схемы и оракул, проверяющий, является ли данное множество замкнутым, слабее, чем оракул независимости: их можно моделировать за полиномиальное время с помощью алгоритма, который обращается к матроиду с помощью оракула независимости, но не наоборот. . Кроме того, ни один из этих трех оракулов не может моделировать друг друга за полиномиальное время. В том же смысле оракул обхвата сильнее оракула независимости. ^[9]

Помимо полиномиальных сокращений Тьюринга по времени, рассматривались и другие типы сводимости. В частности, Карп, Упфал и Вигдерсон (1988) показали, что:в параллельных алгоритмах оракулы ранга и независимости существенно различаются по вычислительной мощности. Оракул ранга позволяет построить базис минимального веса путем $\scriptstyle n$ одновременные запросы префиксов отсортированного порядка элементов матроида: элемент принадлежит оптимальному базису тогда и только тогда, когда ранг его префикса отличается от ранга предыдущего префикса. Напротив, поиск минимального базиса с помощью оракула независимости происходит намного медленнее: его можно решить детерминированно в $\scriptstyle O({\sqrt {n}})$ временные шаги, и существует нижняя граница $\scriptstyle \Omega ((n/\log n)^{1/3})$ даже для рандомизированных параллельных алгоритмов.

Алгоритмы

Известно, что многие проблемы с матроидами могут быть решены за полиномиальное время с помощью алгоритмов, которые получают доступ к матроиду только через независимого оракула или другого оракула эквивалентной мощности, без необходимости каких-либо дополнительных предположений о том, какой тип матроида им предоставлен. К этим полиномиально решаемым задачам относятся:

Нахождение минимального или максимального веса взвешенного матроида с использованием жадного алгоритма . ^[2]
Разбиение элементов матроида на минимальное количество независимых наборов и поиск наибольшего набора, одновременно независимого в двух заданных матроидах. Последняя проблема называется пересечением матроидов , и решения обеих проблем тесно связаны друг с другом. ^[16]
Проверка того, является ли матроид $\scriptstyle k$ -связный (в смысле Тутте 1966 ) для $\scriptstyle k\leq 3$ . ^[17]
Проверка того, является ли данный матроид графическим ^[18] или обычный . ^[19]
Нахождение разложения уха данного матроида, последовательности цепей, объединением которых является матроид и в которой каждая цепь остается схемой после того, как все предыдущие цепи в последовательности сжимаются. Такое разложение можно найти и с тем дополнительным свойством, что выбранный элемент матроида принадлежит каждой схеме. ^[15]
Нахождение разложения ветвей данного матроида, когда ширина его ветвей не превышает фиксированной константы. ^[20]
Перечисление всех оснований, квартир или схем матроида за полиномиальное время для каждого выходного набора. ^[21]
Аппроксимация количества оснований с помощью полностью полиномиальной рандомизированной схемы аппроксимации для матроида с $\scriptstyle n$ элементы и ранг $\scriptstyle r$ , с дополнительным предположением, что количество оснований находится в пределах полиномиального коэффициента числа $\scriptstyle r$ - наборы элементов. ^[22]

Доказательства невозможности

Для многих задач матроида можно показать, что оракул независимости не обеспечивает достаточной мощности, чтобы позволить решить проблему за полиномиальное время. Основная идея этих доказательств — найти два матроида. $\scriptstyle M$ и $\scriptstyle M'$ на которых ответ на задачу различается и которые алгоритму трудно отличить друг от друга. В частности, если $\scriptstyle M$ имеет высокую степень симметрии и отличается от $\scriptstyle M'$ только в ответах на небольшое количество запросов, тогда алгоритму может потребоваться очень большое количество запросов, чтобы быть уверенным в различении входных данных типа $\scriptstyle M$ из входных данных, сформированных с использованием одной из симметрий $\scriptstyle M$ к обменам $\scriptstyle M'$ . ^[3]

Простой пример этого подхода можно использовать, чтобы показать, что трудно проверить, является ли матроид однородным . Для простоты изложения пусть $\scriptstyle n$ будь четным, пусть $\scriptstyle M$ будь единым матроидом $\scriptstyle U{}_{n}^{n/2}$ , и пусть $\scriptstyle M'$ быть матроидом, состоящим из $\scriptstyle M$ сделав один из $\scriptstyle n/2$ -элементные базисы $\scriptstyle M$ зависимый, а не независимый. Чтобы алгоритм правильно проверял, являются ли его входные данные однородными, он должен уметь различать $\scriptstyle M$ из всех возможных перестановок $\scriptstyle M'$ . Но для того, чтобы детерминированный алгоритм мог это сделать, он должен протестировать каждый из $\scriptstyle n/2$ -элементные подмножества элементов: если он пропустит один набор, он может быть обманут оракулом, который выберет тот же самый набор в качестве зависимого. Поэтому проверка однородности матроида может потребовать

{\binom {n}{n/2}}=\Omega \left({\frac {2^{n}}{\sqrt {n}}}\right)

запросы независимости, намного выше, чем полиномиальные. Даже рандомизированный алгоритм должен выполнить примерно столько же запросов, чтобы быть уверенным в различении этих двух матроидов. ^[23]

Дженсен и Корте (1982) формализовали этот подход, доказав, что всякий раз, когда существуют два матроида $\scriptstyle M$ и $\scriptstyle M'$ на одном и том же наборе элементов, но с разными ответами на задачи, алгоритм, который правильно решает данную задачу на этих элементах, должен использовать как минимум

{\frac {|\operatorname {aut} (M)|}{\sum _{i}|\operatorname {fix} (M,Q_{i})|}}

запросы, где $\scriptstyle \operatorname {aut} (M)$ обозначает автоморфизмов группу $\scriptstyle M$ , $\scriptstyle Q_{i}$ обозначает семейство множеств, независимость которых отличается от $\scriptstyle M$ к $\scriptstyle M'$ , и $\scriptstyle \operatorname {fix} (M,Q_{i})$ обозначает подгруппу автоморфизмов, отображающую $\scriptstyle Q_{i}$ самому себе. Например, группа автоморфизмов однородного матроида — это просто симметрическая группа размером $\scriptstyle n!$ , а в задаче о тестировании единых матроидов был только один набор $\scriptstyle Q_{i}$ с $\scriptstyle |\operatorname {fix} (M,Q_{i})|=(n/2)!^{2}$ , меньший в экспоненциальном масштабе, чем $\scriptstyle n!$ . ^[24]

Проблемы, которые, как было доказано, невозможно вычислить с помощью матроидного алгоритма-оракула за полиномиальное время, включают:

Проверка того, является ли данный матроид однородным. ^[23]
Проверка того, содержит ли данный матроид фиксированный матроид. $\scriptstyle H$ будучи несовершеннолетним, за исключением особых случаев, когда $\scriptstyle H$ является однородным с рангом или корангом не более одного. В более общем смысле, если $\scriptstyle {\mathcal {H}}$ — фиксированное конечное множество матроидов, и в нем не существует однородного матроида. $\scriptstyle {\mathcal {H}}$ , то невозможно за полиномиальное время проверить, содержит ли данный матроид один или несколько матроидов в $\scriptstyle {\mathcal {H}}$ как несовершеннолетний. ^[25]
Проверка того, является ли данный матроид двоичным , представимым в любом конкретном фиксированном поле или существует ли поле, в котором он представим. ^[26]
Решение задачи сопоставления матроидов, в которой входными данными являются граф и матроид в его вершинах, а цель состоит в том, чтобы найти в графе соответствие как можно большего размера, при условии, что совпадающие вершины образуют независимое множество. . ^[27]
Проверка того, является ли данный матроид самодвойственным , трансверсальным , двудольным , эйлеровым или ориентируемым . ^[3]
Вычисление обхвата (размера наименьшего контура), размера наибольшего контура, количества контуров, количества оснований, количества квартир, количества квартир максимального ранга, размера наибольшего контура, полинома Тутте или связности заданного матроид. ^[3]

Среди множества всех свойств $\scriptstyle n$ -элементных матроидов, доля свойств, проверка которых не требует экспоненциального времени, в пределе обращается в ноль, так как $\scriptstyle n$ уходит в бесконечность. ^[6]

См. также

Группа «черный ящик» , похожая на оракула. — модель теории групп
Неявный граф — оракул-подобная модель для графовых алгоритмов.

Примечания

^ Jump up to: ^а ^б Робинсон и Уэлш (1980) ; Хаусманн и Корте (1981) ; Куллард и Хеллерштейн (1996) .
^ Jump up to: ^а ^б Эдмондс (1971) .
^ Jump up to: ^а ^б ^с ^д ^и Дженсен и Корте (1982) .
^ Мэйхью (2008) .
^ Пифф и Уэлш (1971) ; Пифф (1973) ; Кнут (1974) ; Бансал, Пендавинг и ван дер Пол (2012) .
^ Jump up to: ^а ^б Робинсон и Уэлш (1980) .
^ Дополнительные исследования матроидов, основанные на аксиоматизации функции независимости, см., например, Радо (1957) , Лазарсон (1958) и Инглтон (1959) .
^ Ловас (1981) ; Сеймур (1981) ; Сеймур и Уолтон (1981) ; Дженсен и Корте (1982) ; Трумпер (1982) .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Робинсон и Уэлш (1980) ; Хаусманн и Корте (1981) .
^ См . Каннингем (1986) , Келманс и Полесский (1994), Фуджишиге и Чжан (1995) , Чавес Ломели и Уэлш (1996) , Хачиян и др. (2005) и Оум и Сеймур (2007) .
^ Азар, Бродер и Фриз (1994) .
^ Карп, Упфал и Вигдерсон (1988) ; Куллард и Хеллерштейн (1996) .
^ Эдмондс (1971) ; Робинсон и Уэлш (1980) ; Хаусманн и Корте (1981) .
^ Jump up to: ^а ^б Хаусманн и Корте (1981) .
^ Jump up to: ^а ^б Куллард и Хеллерштейн (1996) .
^ Эдмондс (1965) ; Каннингем (1986) .
^ Биксби и Каннингем (1979) . Статья, в которой утверждается аналогичный результат для любой фиксированной константы. $\scriptstyle k$ было объявлено Каннингемом и Эдмондсом примерно в одно и то же время, но, похоже, не было опубликовано. Трумпер (1998) , стр. 186–187, пишет: «Нахождение $\scriptstyle k$ -суммы на общее $\scriptstyle k\geq 4$ гораздо сложнее... Мы не знаем, как это можно эффективно реализовать для бинарных матроидов, не говоря уже о матроидах общего назначения».
^ Сеймур (1981) .
^ Трумпер (1982) .
^ Оум и Сеймур (2007) .
^ Хачиян и др. (2005) .
^ Чавес Ломели и Уэлш (1996) . Напротив, детерминированные алгоритмы не могут точно аппроксимировать количество оснований матроида за полиномиальное время ( Azar, Broder & Frieze 1994 ).
^ Jump up to: ^а ^б Робинсон и Уэлш (1980) ; Дженсен и Корте (1982) .
^ не только в Jensen & Korte (1982) Эта формализация рассматривается , но и в Korte & Schrader (1981) . В большинстве случаев применения этой техники в Jensen & Korte (1982 ) $\scriptstyle M$ является однородным, но Сеймур (1981) применил ту же идею к неоднородному, но очень симметричному матроиду.
^ Сеймур и Уолтон (1981) . Результаты Сеймура (1981) и Дженсена и Корте (1982) дают частные случаи этого для задач поиска $\scriptstyle U{}_{4}^{2}$ минор и минор матроида Вамоса соответственно. Проверка того, является ли матроид графическим или регулярным, может быть выражена через конечный набор запрещенных миноров и может быть решена за полиномиальное время, но запрещенные миноры для этих задач включают однородный матроид. $\scriptstyle U{}_{4}^{2}$ , поэтому они не противоречат этому результату о невозможности.
^ Сеймур (1981) показал это для бинарных матроидов, Сеймур и Уолтон (1981) для конечных полей, Трумпер (1982) для произвольных полей и Дженсен и Корте (1982) для существования поля, в котором матроид представим.
^ Ловас (1981) ; Дженсен и Корте (1982) . Однако частный случай этой проблемы для двудольных графов может быть решен за полиномиальное время как задача пересечения матроидов .

Ссылки

Азар, Ю.; Бродер, Аризона ; Фриз, AM (1994), «О проблеме аппроксимации числа оснований матроида», Information Processing Letters , 50 (1): 9–11, doi : 10.1016/0020-0190(94)90037-X , MR 1279491 .
Бансал, Н.; Пендавинг, Р.; ван дер Пол, Дж. (2012), О количестве матроидов , arXiv : 1206.6270 , Bibcode : 2012arXiv1206.6270B .
Биксби, Роберт Э.; Каннингем, Уильям Х. (1979), «Матроиды, графы и 3-связность», Теория графов и смежные темы (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977) , Нью-Йорк: Academic Press, стр. 91–103, МР 0538038 .
Чавес Ломели, Лаура; Уэлш, Доминик (1996), «Рандомизированная аппроксимация числа оснований», Теория матроидов (Сиэтл, Вашингтон, 1995) , Contemporary Mathematics, vol. 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 371–376, doi : 10.1090/conm/197/02534 , MR 1411698 .
Куллард, Коллетт Р .; Хеллерштейн, Лиза (1996), «Независимость и портовые оракулы для матроидов с применением к теории вычислительного обучения», Combinatorica , 16 (2): 189–208, doi : 10.1007/BF01844845 , MR 1401892 .
Каннингем, Уильям Х. (1986), «Улучшенные границы для алгоритмов разделения и пересечения матроидов», SIAM Journal on Computing , 15 (4): 948–957, doi : 10.1137/0215066 , MR 0861361 .
Эдмондс, Джек (1965), «Минимальное разделение матроида на независимые подмножества» , Журнал исследований Национального бюро стандартов , 69B : 67–72, doi : 10.6028/jres.069b.004 , MR 0190025 .
Эдмондс, Джек (1971), «Матроиды и жадный алгоритм», Mathematical Programming , 1 : 127–136, doi : 10.1007/BF01584082 , MR 0297357 .
Фудзисигэ, Сатору; Чжан, Сяодун (1995), «Эффективный алгоритм масштабирования стоимости для задачи независимого назначения», Журнал Японского общества исследования операций , 38 (1): 124–136, MR 1337446 .
Хаусманн, Дирк; Корте, Бернхард (1978), «Нижние границы сложности некоторых алгоритмов оракула в наихудшем случае», Discrete Mathematics , 24 (3): 261–276, doi : 10.1016/0012-365X(78)90097-3 , MR 0523316 .
Хаусманн, Д.; Корте, Б. (1981), «Алгоритмические и аксиоматические определения матроидов», Математическое программирование в Обервольфахе (Proc. Conf., Math. Forschungsinstitut, Oberwolfach, 1979) , Исследования математического программирования, том. 14, стр. 98–111, doi : 10.1007/BFb0120924 , MR 0600125 .
Инглтон, AW (1959), «Заметка о функциях независимости и ранге», Журнал Лондонского математического общества , вторая серия, 34 : 49–56, doi : 10.1112/jlms/s1-34.1.49 , MR 0101848 .
Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772 .
Карп, Ричард М .; Упфал, Эли ; Вигдерсон, Ави (1988), «Сложность параллельного поиска», Журнал компьютерных и системных наук , 36 (2): 225–253, doi : 10.1016/0022-0000(88)90027-X , MR 0950432 .
Кельманс, АК; Полесский В.П. (1994), "Экстремальные множества и задачи покрытия и упаковки в матроидах", Избранные темы дискретной математики (Москва, 1972–1990) , амер. Математика. Соц. Перевод Сер. 2, том. 158, Провиденс, Род-Айленд: Амер. Математика. Соц., стр. 149–174, МР 1269136 .
Хачиян, Л. ; Борос, Э.; Эльбассиони, К.; Гурвич В.; Макино, К. (2005), «О сложности некоторых задач перечисления для матроидов», SIAM Journal on Discrete Mathematics , 19 (4): 966–984, CiteSeerX 10.1.1.124.4286 , doi : 10.1137/S0895480103428338 , MR 2206374 .
Кнут, Дональд Э. (1974), «Асимптотическое число геометрий», Журнал комбинаторной теории , серия A, 16 : 398–400, doi : 10.1016/0097-3165(74)90063-6 , MR 0335312 .
Корте, Бернхард; Хаусманн, Дирк (1978), «Анализ жадной эвристики систем независимости», Алгоритмические аспекты комбинаторики (Конференция, остров Ванкувер, Британская Колумбия, 1976) , Анналы дискретной математики, том. Т. 2, стр. 65–74, doi : 10.1016/S0167-5060(08)70322-4 , MR 0500689 .
Корте, Б.; Шредер, Р. (1981), «Обзор методов оракула», в Груске, Йозефе; Хитил, Михал (ред.), Математические основы информатики, 1981 г., Материалы 10-го симпозиума Штрбске Плесо, Чехословакия, 31 августа - 4 сентября 1981 г. , Конспекты лекций по информатике, том. 118, Берлин: Springer, стр. 61–77, doi : 10.1007/3-540-10856-4_74 , MR 0652740 .
Лазарсон, Т. (1958), «Проблема представления функций независимости», Журнал Лондонского математического общества , вторая серия, 33 : 21–25, doi : 10.1112/jlms/s1-33.1.21 , MR 0098701 .
Ловас, Л. (1981), «Проблема сопоставления матроидов», Алгебраические методы в теории графов, Том I, II (Szeged, 1978) , Colloq. Математика. Сок. Янош Бояи, т. 1, с. 25, Амстердам: Северная Голландия, стр. 495–517, МР 0642059 .
Мэйхью, Диллон (2008), «Сложность матроида и некраткие описания», SIAM Journal on Discrete Mathematics , 22 (2): 455–466, arXiv : math/0702567 , doi : 10.1137/050640576 , MR 2399359 .
Oum, Санг-ил ; Сеймур, Пол (2007), «Тестирование ширины ветвей», Журнал комбинаторной теории , серия B, 97 (3): 385–393, doi : 10.1016/j.jctb.2006.06.006 , MR 2305892 .
Пифф, MJ (1973), «Верхняя граница числа матроидов», Journal of Combinatorial Theory , Series B, 14 : 241–245, doi : 10.1016/0095-8956(73)90006-3 , MR 0316282 .
Пифф, MJ; Уэлш, DJA (1971), «Число комбинаторных геометрий», Бюллетень Лондонского математического общества , 3 : 55–56, doi : 10.1112/blms/3.1.55 , MR 0282867 .
Радо, Р. (1942), «Теорема об отношениях независимости», Ежеквартальный журнал математики , вторая серия, 13 : 83–89, бибкод : 1942QJMat..13...83R , doi : 10.1093/qmath/os- 13.1.83 , МР 0008250 .
Радо, Р. (1957), «Заметки о функциях независимости», Труды Лондонского математического общества , третья серия, 7 : 300–320, doi : 10.1112/plms/s3-7.1.300 , MR 0088459 .
Робинсон, GC; Уэлш, DJA (1980), «Вычислительная сложность свойств матроида», Mathematical Proceedings of the Cambridge Philosophical Society , 87 (1): 29–45, Bibcode : 1980MPCPS..87...29R , doi : 10.1017/S0305004100056498 , МР 0549295 .
Сеймур, П.Д. (1981), «Распознавание графических матроидов», Combinatorica , 1 (1): 75–78, doi : 10.1007/BF02579179 , MR 0602418 .
Сеймур, Полиция ; Уолтон, PN (1981), «Обнаружение несовершеннолетних матроидов», Журнал Лондонского математического общества , вторая серия, 23 (2): 193–203, doi : 10.1112/jlms/s2-23.2.193 , MR 0609098 .
Трумпер, К. (1982), «Об эффективности тестов представимости матроидов», European Journal of Combinatorics , 3 (3): 275–291, doi : 10.1016/s0195-6698(82)80039-5 , MR 0679212 .
Трумпер, К. (1998), Разложение матроида (PDF) (переработанная редакция) .
Тутте, WT (1966), «Связность матроидов», Canadian Journal of Mathematics , 18 : 1301–1324, doi : 10.4153/CJM-1966-129-2 , MR 0205880 .

[Robinson_1980-1] Jump up to: ^а ^б Робинсон и Уэлш (1980) ; Хаусманн и Корте (1981) ; Куллард и Хеллерштейн (1996) .

[e71-2] Jump up to: ^а ^б Эдмондс (1971) .

[jk82-3] Jump up to: ^а ^б ^с ^д ^и Дженсен и Корте (1982) .

[4] Мэйхью (2008) .

[5] Пифф и Уэлш (1971) ; Пифф (1973) ; Кнут (1974) ; Бансал, Пендавинг и ван дер Пол (2012) .

[rw80-6] Jump up to: ^а ^б Робинсон и Уэлш (1980) .

[7] Дополнительные исследования матроидов, основанные на аксиоматизации функции независимости, см., например, Радо (1957) , Лазарсон (1958) и Инглтон (1959) .

[8] Ловас (1981) ; Сеймур (1981) ; Сеймур и Уолтон (1981) ; Дженсен и Корте (1982) ; Трумпер (1982) .

[rwhk-9] Jump up to: ^а ^б ^с ^д ^и ^ж Робинсон и Уэлш (1980) ; Хаусманн и Корте (1981) .

[10] См . Каннингем (1986) , Келманс и Полесский (1994), Фуджишиге и Чжан (1995) , Чавес Ломели и Уэлш (1996) , Хачиян и др. (2005) и Оум и Сеймур (2007) .

[11] Азар, Бродер и Фриз (1994) .

[12] Карп, Упфал и Вигдерсон (1988) ; Куллард и Хеллерштейн (1996) .

[13] Эдмондс (1971) ; Робинсон и Уэлш (1980) ; Хаусманн и Корте (1981) .

[hk01-14] Jump up to: ^а ^б Хаусманн и Корте (1981) .

[ch96-15] Jump up to: ^а ^б Куллард и Хеллерштейн (1996) .

[16] Эдмондс (1965) ; Каннингем (1986) .

[17] Биксби и Каннингем (1979) . Статья, в которой утверждается аналогичный результат для любой фиксированной константы. $\scriptstyle k$ было объявлено Каннингемом и Эдмондсом примерно в одно и то же время, но, похоже, не было опубликовано. Трумпер (1998) , стр. 186–187, пишет: «Нахождение $\scriptstyle k$ -суммы на общее $\scriptstyle k\geq 4$ гораздо сложнее... Мы не знаем, как это можно эффективно реализовать для бинарных матроидов, не говоря уже о матроидах общего назначения».

[18] Сеймур (1981) .

[19] Трумпер (1982) .

[20] Оум и Сеймур (2007) .

[21] Хачиян и др. (2005) .

[22] Чавес Ломели и Уэлш (1996) . Напротив, детерминированные алгоритмы не могут точно аппроксимировать количество оснований матроида за полиномиальное время ( Azar, Broder & Frieze 1994 ).

[rwjk-23] Jump up to: ^а ^б Робинсон и Уэлш (1980) ; Дженсен и Корте (1982) .

[24] не только в Jensen & Korte (1982) Эта формализация рассматривается , но и в Korte & Schrader (1981) . В большинстве случаев применения этой техники в Jensen & Korte (1982 ) $\scriptstyle M$ является однородным, но Сеймур (1981) применил ту же идею к неоднородному, но очень симметричному матроиду.

[25] Сеймур и Уолтон (1981) . Результаты Сеймура (1981) и Дженсена и Корте (1982) дают частные случаи этого для задач поиска $\scriptstyle U{}_{4}^{2}$ минор и минор матроида Вамоса соответственно. Проверка того, является ли матроид графическим или регулярным, может быть выражена через конечный набор запрещенных миноров и может быть решена за полиномиальное время, но запрещенные миноры для этих задач включают однородный матроид. $\scriptstyle U{}_{4}^{2}$ , поэтому они не противоречат этому результату о невозможности.

[26] Сеймур (1981) показал это для бинарных матроидов, Сеймур и Уолтон (1981) для конечных полей, Трумпер (1982) для произвольных полей и Дженсен и Корте (1982) для существования поля, в котором матроид представим.

[27] Ловас (1981) ; Дженсен и Корте (1982) . Однако частный случай этой проблемы для двудольных графов может быть решен за полиномиальное время как задача пересечения матроидов .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]