最小支配集軟件

Question

交叉發佈這個from CS Theory因爲它更像是一個軟件問題。

我需要一個代碼來計算確切的MIN-DOM-SET。目前建議的最佳選擇是將其制定爲SMT問題並將其投入SMT解決方案。

好奇的是，如果有任何良好的MIN-DOM-SET特定代碼或良好的SMT-LIB制定。

Answer 1

I coded one up Z3的Python綁定使用新的優化功能。

def min_dom_set(graph): 
    """Try to dominate the graph with the least number of verticies possible""" 
    s = Optimize() 
    nodes_colors = dict((node_name, Int('k%r' % node_name)) for node_name in graph.nodes()) 
    for node in graph.nodes(): 
      s.add(And(nodes_colors[node] >= 0, nodes_colors[node] <= 1)) # dominator or not 
      dom_neighbor = Sum ([ (nodes_colors[j]) for j in graph.neighbors(node) ]) 
      s.add(Sum(nodes_colors[node], dom_neighbor) >= 1) 
    s.minimize(Sum([ nodes_colors[y] for y in graph.nodes() ])) 

    if s.check() == sat: 
     m = s.model() 
     return dict((name, m[color].as_long()) for name, color in nodes_colors.iteritems()) 

    raise Exception('Could not find a solution.')