R igraph найти все максимальные клики без наложения

Question

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

например, если на выходе max_cliques() следующие клики:

{A, B, C}, {A, B, D}, {A, B, J, K}, {E, F, G, H}, {E, F, G, I}

Я хочу удалить некоторые клики, чтобы все вершины появлялись в одной клике, поэтому окончательный набор будет:

{A, B, J, K}, {E, F, G, H}

A и B включены в 3 клика, поэтому я хочу выбрать клики так, чтобы окончательный набор включал максимально возможные вершины. если есть две возможные клики одинаковой длины, возьмите случайную. (Я не против не включать все вершины)

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

заранее спасибо

Answer 1

По-видимому, решить эту проблему довольно сложно, когда вы спрашиваете о проблемах Coverage и Independent Set. Это NP-полные проблемы. Это означает, что по мере роста вашего графика время вычислений будет расти в геометрической прогрессии.

Я думаю, что это то, к чему вы стремитесь. Мой подход заключается в следующем:

1. Найти клики.
2. Преобразовать в матрицу инцидентности (клики по узлам).
3. Умножить матрицу заболеваемости на ее транспонирование (%*%) это создает матрицу смежности
4. создать график клик из матрицы смежности (клики связаны с другими кликами, если они совместно используют узел)
5. Найти все независимые множества вершин (это узкое место)
6. Получить оригинальные узлы для независимых наборов кликов
7. Найти множество с большинством узлов.

Код

library(igraph)  
set.seed(8675309)  
g <- graph_from_edgelist(matrix(sample(LETTERS[1:10], 50, replace=T), ncol = 2), directed = FALSE)  
plot(g, edge.arrow.size=0.5)

cliques <- max_cliques(g)

cliqueBP <- matrix(c(rep(paste0("cl", seq_along(cliques)), sapply(cliques, length)), names(unlist(cliques))), ncol=2, )
bp <- graph_from_edgelist(cliqueBP, directed = F)
V(bp)$type <- grepl("cl", V(bp)$name)
# plot(bp, layout=layout_as_bipartite)

bp.ind <- t(as_incidence_matrix(bp))
bp.adj <- bp.ind %*% t(bp.ind)

bp.adj.g <- graph_from_adjacency_matrix(bp.adj, mode = "undirected")
# plot(simplify(bp.adj.g))
bp.adj.mis <- independent.vertex.sets(bp.adj.g)

sets <- lapply(bp.adj.mis, function(x) cliqueBP[cliqueBP[,1] %in% as_ids(x), 2])
sets[which(sapply(sets, length) == max(sapply(sets, length)))]

# [[1]]
# [1] "G" "J" "E" "I" "B" "H" "F" "D"
# 
# [[2]]
# [1] "G" "J" "E" "I" "F" "C" "B" "H"
# 
# [[3]]
# [1] "G" "J" "E" "I" "F" "C" "A" "H"
# 
# [[4]]
# [1] "G" "B" "E" "I" "F" "C" "A" "H"
# 
# [[5]]
# [1] "G" "B" "E" "I" "F" "C" "H" "J"