У меня есть следующая проблема, которая, похоже, имеет некоторые сходства с проблемой покрытия вершин.
У нас есть ориентированный граф G = (V, E) с | V | вершины и | E | кромки. Давайте представим, что вершина представляет человека и что ребро от вершины A до ветрекс B представляет информационный путь от B к A, т. Е. Если B предоставлен фрагмент информации, то A также имеет его. Однако, если другое ребро переходит от вершины C к вершине A, то информация не достигнет C, если не будет ребра от C до B или если информация также передана непосредственно в A.
Теперь вопрос в том, какое максимальное количество вершин / лиц мы можем достичь, предоставив информацию (не более) k вершинам / людям. Я думаю, что это тесно связано с проблемой вершин, но где мы должны покрыть только k вершин вместо всех. Но, тем не менее, она не совсем подходит для другой проблемы.
Кто-нибудь может назвать хорошо известную проблему, имеющую сходную структуру? Это помогло бы мне лучше подойти к нему с помощью алгоритма аппроксимации.
Редактировать: я заинтересован в аспекте оптимизации этой проблемы, но мне кажется, что оптимальным подходом будет выбор набора связанных людей , насколько это возможно, а затем удалите выбранных людей из всех других наборов связанных людей и повторите процесс. Тогда проблема была бы в P, но это на самом деле NP-сложный. Такого я не вижу.