<p>I'm writing a survey about nowhere-dense graphs. I would like to list some of the main open problems in the field. In particular I would like to list problems of the following form. </p>

<ul>
<li>The problem has been shown to be efficiently solvable (meaning in polynomial time, FPT time, XP time, depending on the context) on the "largest" proper sub-classes (such as bounded expansion, excluded minor, etc) but it is not known to be solvable efficiently (poly time, FPT time, XP time, depending on the context) on general nowhere-dense classes of graphs. </li>
</ul>

<p>Until now, every problem I found that can be solved efficiently on the "largest" proper subclasses has been shown later to be solvable efficiently for nowhere dense graphs. But I'm sure that I'm missing some references. </p>

CC BY-SA 4.0
2020-03-08T14:10:04.437Z
FYI: Since FO model checking is FPT for nowhere dense graphs, an open problem you're searching cannot be FO definable (or it uses a different parametrization).
Daniel
CC BY-SA 4.0
2020-03-09T10:56:15.067Z
@Daniel yes, I'm interested in problems that are not FO expressible. There has been work considering problems that are expressible in slight generalizations of FO logic which have been shown to be efficiently solvable on certain nowhere dense classes of graphs, and then later shown to be solvable efficiently on any nowhere dense class of graphs. I'm interested in problems where the first part has been shown (for classes of bounded expansion, minor-free classes or above) but not the second part. As long as the problem has been cited somewhere.
Springberg
<parameterized-complexity><open-problem><graph-classes>
Open Problems About Nowhere-Dense Classes of Graphs
Springberg
# Open Problems About Nowhere-Dense Classes of Graphs

(Asked by: username_0 on 2020-03-07)

I'm writing a survey about nowhere-dense graphs. I would like to list some of the main open problems in the field. In particular I would like to list problems of the following form.

* The problem has been shown to be efficiently solvable (meaning in polynomial time, FPT time, XP time, depending on the context) on the "largest" proper sub-classes (such as bounded expansion, excluded minor, etc) but it is not known to be solvable efficiently (poly time, FPT time, XP time, depending on the context) on general nowhere-dense classes of graphs.

Until now, every problem I found that can be solved efficiently on the "largest" proper subclasses has been shown later to be solvable efficiently for nowhere dense graphs. But I'm sure that I'm missing some references.

**Tags:** parameterized-complexity, open-problem, graph-classes

> **Comments:**
> **username_1**: FYI: Since FO model checking is FPT for nowhere dense graphs, an open problem you're searching cannot be FO definable (or it uses a different parametrization).  
> **username_0**: @username_1 yes, I'm interested in problems that are not FO expressible. There has been work considering problems that are expressible in slight generalizations of FO logic which have been shown to be efficiently solvable on certain nowhere dense classes of graphs, and then later shown to be solvable efficiently on any nowhere dense class of graphs. I'm interested in problems where the first part has been shown (for classes of bounded expansion, minor-free classes or above) but not the second part. As long as the problem has been cited somewhere.  

---

## 0 answers

