<p>As you mentioned that "My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too", you can have a look at the thesis by Morgan Chopin -- "Optimization problems with propagation in graphs: Parameterized complexity and approximation" (<a href="https://tel.archives-ouvertes.fr/tel-00933769" rel="nofollow">https://tel.archives-ouvertes.fr/tel-00933769</a>). 
Here, author shows some results with "bandwidth" for "Firefighter" problem and "Target Set Selection" problem which can be thought of as a discretized version of "Influence Maximization".</p>

CC BY-SA 3.0
2016-05-31T17:59:04.387Z
2016-05-31T17:59:04.387Z
jayesh
<p>I am trying to find references on algorithms for graphs of bounded <a href="https://en.wikipedia.org/wiki/Graph_bandwidth" rel="nofollow">bandwidth</a>, in the same way as it is done with treewidth for instance.
I could only find research related to  computing the bandwidth, or properties of this measure, but not using it as assumption for better algorithms.</p>

<p>Also, I am very interested in a generalization of bandwidth in higher dimensions. For instance <a href="http://www.sciencedirect.com/science/article/pii/S0020019010000943" rel="nofollow">this paper</a> studies 2-dimensional bandwidth, but considering only the $L^1$ and $L^\infty$ norms on $\mathbb N\times \mathbb N$, whereas I am more interested in the euclidean norm $L^2$. It seems natural to consider graphs of $n$-dimensional bandwidth for euclidean norm. Formally, the $n$-dimensional bandwidth of a graph $G=(V,E)$ is defined as :
$$\min_{\alpha} ~\max_{(x,y)\in E}||\alpha(x)-\alpha(y)||_2$$
where $\alpha$ ranges over injective functions $V\to \mathbb N^n$.</p>

<p>This is pretty natural, for instance graphs coming from discretizations of real-life systems following differential equations would likely have bounded bandwidth. Indeed, if an edge takes you to the state of the system at the next time instant, it can not be too far from your current state if the time step is small enough and the system evolves continuously. It seems that this special structure could be used to design better algorithms (in particular for solving games on these graphs), but I could not find anything on this kind of graphs.</p>

CC BY-SA 3.0
2016-05-30T22:15:03.860Z
Are you also interested in results where bandwidth provably doesn't help (e.g. something remains NP-complete even for bounded bandwidth)? Because I have one of those at http://arxiv.org/abs/1304.5591
David Eppstein
CC BY-SA 3.0
2016-05-30T22:36:00.683Z
Yes I am interested in algorithmic problems on graphs of bounded bandwidth, whether it helps or not. My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too. Thanks for this reference.
Denis
CC BY-SA 3.0
2016-05-31T01:16:28.293Z
See this paper by Vempala on embedding into 2-d grid. http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=743489&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D743489
Chandra Chekuri
CC BY-SA 3.0
2016-05-31T12:10:48.070Z
You can look at "structural parameterization" where the parameter bandwidth is sometimes used. However, treewidth never exceeds the bandwidth of a graph, therefore all problems FPT w.r.t. treewidth are also for param bandwidth (see section 2 of the PhD. Thesis of Bart Jansen). 

Also, in the following paper, it is shown that Graph Motif is NP-hard on graphs with bandwidth 4 https://arxiv.org/abs/1503.05110
Olf
CC BY-SA 3.0
2016-06-01T15:11:54.357Z
@Florian: thanks for the reference. The relationship with treewidth is only true in one dimension, that's why I would be interested in bounding bandwidth in higher dimension.
Denis
<reference-request><graph-theory><graph-algorithms><gt.game-theory>
On bandwidth of graphs
Denis
# On bandwidth of graphs

(Asked by: username_0 on 2016-05-30)

I am trying to find references on algorithms for graphs of bounded [bandwidth](https://en.wikipedia.org/wiki/Graph_bandwidth), in the same way as it is done with treewidth for instance.
I could only find research related to computing the bandwidth, or properties of this measure, but not using it as assumption for better algorithms.

Also, I am very interested in a generalization of bandwidth in higher dimensions. For instance [this paper](http://www.sciencedirect.com/science/article/pii/S0020019010000943) studies 2-dimensional bandwidth, but considering only the $L^1$ and $L^\infty$ norms on $\mathbb N\times \mathbb N$, whereas I am more interested in the euclidean norm $L^2$. It seems natural to consider graphs of $n$-dimensional bandwidth for euclidean norm. Formally, the $n$-dimensional bandwidth of a graph $G=(V,E)$ is defined as :
$$\min\_{\alpha} ~\max\_{(x,y)\in E}||\alpha(x)-\alpha(y)||\_2$$
where $\alpha$ ranges over injective functions $V\to \mathbb N^n$.

This is pretty natural, for instance graphs coming from discretizations of real-life systems following differential equations would likely have bounded bandwidth. Indeed, if an edge takes you to the state of the system at the next time instant, it can not be too far from your current state if the time step is small enough and the system evolves continuously. It seems that this special structure could be used to design better algorithms (in particular for solving games on these graphs), but I could not find anything on this kind of graphs.

**Tags:** reference-request, graph-theory, graph-algorithms, gt.game-theory
> **Comments:**
> **username_1**: Are you also interested in results where bandwidth provably doesn't help (e.g. something remains NP-complete even for bounded bandwidth)? Because I have one of those at http://arxiv.org/abs/1304.5591  
> **username_0**: Yes I am interested in algorithmic problems on graphs of bounded bandwidth, whether it helps or not. My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too. Thanks for this reference.  
> **username_2**: See this paper by Vempala on embedding into 2-d grid. http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=743489&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D743489  
> **username_3**: You can look at "structural parameterization" where the parameter bandwidth is sometimes used. However, treewidth never exceeds the bandwidth of a graph, therefore all problems FPT w.r.t. treewidth are also for param bandwidth (see section 2 of the PhD. Thesis of Bart Jansen).   Also, in the following paper, it is shown that Graph Motif is NP-hard on graphs with bandwidth 4 https://arxiv.org/abs/1503.05110  
> **username_0**: @Florian: thanks for the reference. The relationship with treewidth is only true in one dimension, that's why I would be interested in bounding bandwidth in higher dimension.  

---

## 1 answers

### Answer by username_4 on 2016-05-31. Score: 2

As you mentioned that "My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too", you can have a look at the thesis by Morgan Chopin -- "Optimization problems with propagation in graphs: Parameterized complexity and approximation" (<https://tel.archives-ouvertes.fr/tel-00933769>).
Here, author shows some results with "bandwidth" for "Firefighter" problem and "Target Set Selection" problem which can be thought of as a discretized version of "Influence Maximization".


---

