Some rainbow problems in graphs have complexity equivalent to satisfiability problems.

Olivier Hudry Antoine Lobstein

Published in: Int. Trans. Oper. Res. (2022)

Keyphrases

satisfiability problem
np complete
decision problems
pspace complete
description logics
sat instances
mazurkiewicz traces
search algorithm
upper bound
optimal policy
orders of magnitude
phase transition
random sat