2

查找图的色数是一个 NP-Hard 问题，因此“理论上”没有快速求解器。是否有任何公开可用的软件可以快速计算图形的确切色数？

我正在编写一个 Python 脚本来计算许多图的色数，但即使是小图也需要很长时间。我正在使用的图表范围很广，可以是稀疏的或密集的，但通常少于 10,000 个节点。我将问题表述为一个整数程序并将其传递给 Gurobi 来解决。您对软件、不同的 IP 公式或不同的 Gurobi 设置有什么建议来加快速度吗？

import networkx as nx
from gurobipy import *

# create test graph
n = 50
p = 0.5
G = nx.erdos_renyi_graph(n, p)

# compute chromatic number -- ILP solve
m = Model('chrom_num')

# get maximum number of variables necessary
k = max(nx.degree(G).values()) + 1

# create k binary variables, y_0 ... y_{k-1} to indicate whether color k is used
y = []
for j in range(k):
    y.append(m.addVar(vtype=GRB.BINARY, name='y_%d' % j, obj=1))

# create n * k binary variables, x_{l,j} that is 1 if node l is colored with j
x = []
for l in range(n):
    x.append([])
    for j in range(k):
        x[-1].append(m.addVar(vtype=GRB.BINARY, name='x_%d_%d' % (l, j), obj=0))

# objective function is minimize colors used --> sum of y_0 ... y_{k-1}
m.setObjective(GRB.MINIMIZE)
m.update()

# add constraint -- each node gets exactly one color (sum of colors used is 1)
for u in range(n):
    m.addConstr(quicksum(x[u]) == 1, name='NC_%d' % u)

# add constraint -- keep track of colors used (y_j is set high if any time j is used)
for u in range(n):
    for j in range(k):
        m.addConstr(x[u][j] <= y[j], name='SH_%d_%d' % (u,j))

# add constraint -- adjacent nodes have different colors
for u in range(n):
    for v in G[u]:
        if v > u:
            for j in range(k):
                m.addConstr(x[u][j] + x[v][j] <= 1, name='ADJ_%d_%d_COL_%d' % (u,v,j))

# update model, solve, return the chromatic number
m.update()
m.optimize()
chrom_num = m.objVal

我希望计算精确的色数，尽管如果它们具有合理的理论保证（例如常数因子近似等），我会对计算近似色数的算法感兴趣。

4

1 回答 1

2

您可能想尝试使用 SAT 求解器或 Max-SAT 求解器。我希望它们会比简化为整数程序更好，因为我认为可着色性更接近可满足性。

SAT 求解器接收联合范式中的命题布尔公式，并输出该公式是否可满足。以下问题 COL_k 在 NP 中：

输入：图 G 和自然数 k。

输出：G 是 k 可着色的。

为了解决 COL_k，您将其编码为一个命题布尔公式，其中每一对 (u,c) 都有一个命题变量，该对 (u,c) 由一个顶点 u 和一个颜色 1<=c<=k 组成。您需要编写确保每个顶点至少用一种颜色着色的子句。您还需要子句来确保每个边缘都是正确的。然后你只需进行二分搜索以找到 k 的值，使得 G 是 k 可着色但不是 (k-1) 可着色的。有各种免费的 SAT 求解器。我已经成功使用了灵灵灵，但是你可以在SAT 竞赛网站上找到很多其他的。它们都使用相同的输入和输出格式。谷歌“MiniSAT 用户指南：如何使用 MiniSAT SAT Solver”以获取有关此格式的说明。

您也可以使用 Max-SAT 求解器，再次咨询Max-SAT 竞赛网站。它们可以解决 Partial Max-SAT 问题，其中子句分为硬子句和软子句。在这里，求解器找到在满足所有硬子句的同时可以满足的最大软子句数，请参阅 Max-SAT 竞赛网站中的输入格式（在规则-> 详细信息下）。

您可以将色数问题表述为一个 Max-SAT 问题（与上面的几个 SAT 问题相反）。从这个意义上说，Max-SAT 更合适。另一方面，我的印象是 SAT 求解器通常比 Max-SAT 求解器执行得更好。我对这种求解器没有任何经验，所以不能多说。

于 2016-10-23T07:07:02.253 回答