Позволять быть графом Набор вершинназывается критическим, если и нет вершины в смежна ровно с одной вершиной в , Проблема состоит в том, чтобы найти множество вершин минимального размера, такого что для каждого критического набора ,
Эта проблема имеет следующую распространяющуюся по слухам интерпретацию: Vertex распространяет слух своему соседу если и только если все остальные соседи уже проинформированы. Тогда возникает вопрос, сколько вершин мне нужно сообщить на начальном этапе, чтобы в конце все были проинформированы.
cc.complexity-theory
graph-theory
co.combinatorics
optimization
Томас Калиновский
источник
источник
Ответы:
Проблема известна как проблема распространения . Азами доказал в своей докторской диссертации, что взвешенная версия является NP-полной, даже когда график плоский, а веса узлов находятся в{ 0 , 1 } , Сложность для невзвешенной версии кажется открытой проблемой.
источник