色数的快速精确求解器

Question

求图的色数是一个 NP-Hard 问题，因此没有快速求解器 'in theory'。是否有任何公开可用的软件可以快速计算图形的准确色数？

我正在编写一个 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

我希望计算精确的色数，但我会对计算近似色数的算法感兴趣，前提是它们具有合理的理论保证，例如常数因子近似等。

Answer 1

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

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

输入：图G和自然数k。

输出：G 是 k 色的。

为了求解 COL_k，您将其编码为一个命题布尔公式，每对 (u,c) 包含一个命题变量，由顶点 u 和颜色 1<=c<=k 组成。您需要编写子句以确保每个顶点至少被一种颜色着色。您还需要子句来确保每条边都是正确的。然后，您只需进行二分搜索即可找到 k 的值，使得 G 可着色为 k 而不是 (k-1) 可着色。有各种免费的 SAT 求解器。我成功地使用了 Lingeling，但是您可以在 SAT competition website 上找到许多其他的。它们都使用相同的输入和输出格式。 Google "MiniSAT User Guide: How to use the MiniSAT SAT Solver" 以获取有关此格式的说明。

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

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

色数的快速精确求解器

Fast Exact Solvers for Chromatic Number

graph-algorithm

graph-theory

gurobi

np-hard