RUS  ENG
Полная версия
ЖУРНАЛЫ // Moscow Mathematical Journal // Архив

Mosc. Math. J., 2004, том 4, номер 2, страницы 523–528 (Mi mmj159)

Weighted well-covered graphs and complexity questions

[Взвешенные хорошо укрытые графы и вопросы сложности]

I. É. Zverovich

Rutgers, The State University of New Jersey

Аннотация: Взвешенный граф $G$ называется хорошо укрытым, если все его максимальные независимые множества имеют одинаковый вес. Пусть $S$ – независимое множество, возможно пустое, в графе $G$. Подграф $G-N[S]$ называется костабильным подграфом графа $G$. Обозначим через ${\rm CSub}(G)$ множество всех костабильных подграфов графа $G$, рассматриваемых с точностью до изоморфизма. Класс взвешенных графов $\mathscr P$ называется конаследственным, если он замкнут относительно перехода к костабильному подграфу, т.е. из $G\in\mathscr P$ следует включение ${\rm CSub}(G)\subseteq\mathscr P$.
Класс $\mathscr{WEIGHT}$ $\mathscr{WELL}$ всех взвешенных хорошо укрытых графов является конаследственным. Получена характеризация этого класса в терминах запрещенных костабильных подграфов.
Используя сведение задачи Выполнимость, показано, что следующие проблемы распознавания являются NP-полными.
Задача распознавания 1(Костабильный подграф).
Условие: Граф $G$ и множество $U\subseteq V(G)$, которое порождает в $G$ подграф $H$.
Вопрос: Является ли $H$ костабильным подграфом графа $G$?
Задача распознавания 2 (Костабильный подграф $H$).
Условие: Граф $G$.
Вопрос: Является ли $H$ костабильным подграфом графа $G$?
Пусть $\Delta(G)$ обозначает наибольшую из степеней вершин графа $G$. Показано, что распознавание взвешенных хорошо укрытых графов с ограниченной степенью $\Delta(G)$ может быть выполнено за полиномиальное время.

MSC: 05C85

Статья поступила: 22 апреля 2004 г.

Язык публикации: английский

DOI: 10.17323/1609-4514-2004-4-2-523-528



Реферативные базы данных:


© МИАН, 2024