Is there a systematic way to tune the hardness of a set of satisfiability problems (say 3-SAT or MAX2SAT) where the constraint graphs are always embeddable into a fixed given graph?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ In the paper "When is the evaluation of conjunctive queries tractable?" of Grohe et al. (STOC '01) it is proved that if C is a class of graphs with unbounded treewidth, then one can embed arbitrarily hard CSP problems to graphs in C. (and conversely, of course, if C has bounded treewidth then CSP in C can be solved in polytime). I have not read the paper completely, but it sounds something highly related to your question, so I think you should check if it answers to your question. $\endgroup$– LaakeriNov 25, 2020 at 12:21
-
1$\begingroup$ Though this paper seems to not help much if you are interested in something practical because it relies on the grid-minor theorem. $\endgroup$– LaakeriNov 25, 2020 at 12:37
-
$\begingroup$ @Laakeri, it seems my setup is exactly opposite to the setup in grid-minor theorem. In the grid-minor theorem, the larger graph is arbitrary and the graph to be embedded is a grid. In my case, the larger graph has constrained topology (e.g. a grid) but the graph to be embedded could be arbitrary. $\endgroup$– Omar ShehabApr 5, 2021 at 15:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It sounds like what you want are universal factor graphs. Such graphs exist for every NP-hard boolean CSP and in many cases are optimally inapproximable.
