Является ли пересечение

16

Известно, что пересечение трех общих матроидов является NP-трудным ( источником ), что осуществляется посредством сокращения из гамильтонова цикла. Сокращение использует один графический матроид и два матроида связи.

Частный случай проблемы, над которой я работаю, может быть решен путем пересечения нескольких графических матроидов, но я не смог найти, есть ли эта проблема в P.

Вопрос: это известно? Может кто-нибудь, пожалуйста, направьте меня к статье или что-то?

( Примечание: я задал этот вопрос по информатике и был упомянут здесь.)

Матей Конечны
источник

Ответы:

11

Я думаю, что он все еще NP-полный, путем сокращения от гамильтоновых путей в двудольных графах с двумя вершинами степени одна и всеми остальными вершинами, имеющими степень три. (Это аналогично нахождению гамильтоновых циклов через указанное ребро в кубическом двудольном графе - замените указанное ребро двумя листами.)

Чтобы уменьшить путь от гамильтоновых путей до пересечения графических матроидов, используйте один графический матроид, чтобы заставить выбранный вами подграф быть связующим деревом (верно для каждого пути), и еще два графических матроида, по одному на каждой стороне двудольного раздела, чтобы заставить подграф иметь степень два в каждой вершине степени три и иметь ребро в каждой вершине степени один. Это графические матроиды графа с непересекающимися копиями для каждой вершины степени три и K 2 для каждой вершины степени один.К3К2

Дэвид Эппштейн
источник
8

Как насчет использования того факта, что 3-е совпадение является NP завершенным, чтобы показать NP Полноту этой проблемы. Мы можем легко написать 3-мерное совпадение как пересечение трех матроидов разбиений, и матроид разбиений является частным случаем графического матроида (рассмотрим граф с параллельными ребрами).

Сахил Сингла
источник
3
Неверно, что матроид раздела всегда является графическим матроидом, но в вашем случае вы хотите выбрать ровно один элемент из каждой части, и этот матроид является графическим.
Сашо Николов