Всем доброе время суток.
Столкнулся я недавно с задачей, в рамках которой надо проверять, что данный граф раскрашиваем в k цветов. Специфика следующая:
графы довольно большие (до нескольких тысяч вершин), но не очень плотные (средняя степень около 10-20, максимальная степень может быть порядка 50).
k не слишком большое (до 10 примерно).
важно, чтобы результат был достоверным (т.е. даже односторонняя ошибка не допускается).
Я нашел либу, которая умеет считать хроматическое число графа (надо сказать, что для таких масштабов она в среднем довольно быстро находит ответ, но на некоторых инстансах все же сильно задумывается). k-раскрашиваемость заведомо проще, чем подсчет хроматического числа, поэтому специализированное решение для раскрашиваемости должно бы работать получше; однако найти готовый код или хотя бы описание хорошего с практической точки зрения алгоритма мне не удалось.
Расскажите, пожалуйста, занимались ли вы этой задачей или чем-то похожим, что вы для этого использовали и какого результата добились? Приветствуются также любые советы, интересные ссылки и комментарии по существу.
Не в тему, но в свое время мне надо было посчитать хроматическое число для определенного большого графа и возник такой вопрос с ответами на mathoverflow: http://mathoverflow.net/questions/33812/lower-bounds-for-chromatic-number-of-a-graph .
Ой, а я уже читал это обсуждение, когда гуглил по теме. =)
Если бы я столкнулся с такой задачей, первое, что я попробовал бы, — скормить её CSP-солверу. На таких ограничениях оно должно довольно быстро работать.
Да, надо попробовать, спасибо!
Может, порекомендуешь какой-нибудь конкретный?
Я всегда использовал sat4j, т.к. он для java и легко добавляется в проект редактированием maven-конфига. Однако он далеко не самый эффективный (тем более для CSP). Быстрое гугление находит такой ранкинг солверов.