<p>It sounds like what you want are <a href="https://arxiv.org/abs/1204.6484" rel="nofollow noreferrer">universal factor graphs</a>. Such graphs exist for <a href="https://drops.dagstuhl.de/opus/volltexte/2014/4702/pdf/19.pdf" rel="nofollow noreferrer">every NP-hard boolean CSP</a> and in many cases are <a href="https://eccc.weizmann.ac.il/report/2019/151/" rel="nofollow noreferrer">optimally inapproximable</a>.</p>

CC BY-SA 4.0
2020-11-26T06:52:59.470Z
2020-11-26T06:52:59.470Z
Whosyourjay
<p>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?</p>

CC BY-SA 4.0
2020-11-25T12:21:08.857Z
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.
Laakeri
CC BY-SA 4.0
2020-11-25T12:37:44.203Z
Though this paper seems to not help much if you are interested in something practical because it relies on the grid-minor theorem.
Laakeri
CC BY-SA 4.0
2021-04-05T15:48:43.090Z
@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.
Omar Shehab
<graph-theory><sat><phase-transition><random-k-sat><max2sat>
Generating hard satisfiability problems with given constraint graph
Omar Shehab
# Generating hard satisfiability problems with given constraint graph

(Asked by: username_0 on 2020-11-25)

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?

**Tags:** graph-theory, sat, phase-transition, random-k-sat, max2sat

> **Comments:**
> **username_1**: 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.  
> **username_1**: Though this paper seems to not help much if you are interested in something practical because it relies on the grid-minor theorem.  
> **username_0**: @username_1, 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.  

---

## 1 answers

### Answer by username_2 on 2020-11-26. Score: 2

It sounds like what you want are [universal factor graphs](https://arxiv.org/abs/1204.6484). Such graphs exist for [every NP-hard boolean CSP](https://drops.dagstuhl.de/opus/volltexte/2014/4702/pdf/19.pdf) and in many cases are [optimally inapproximable](https://eccc.weizmann.ac.il/report/2019/151/).


---

