6
$\begingroup$

I am trying to find references on algorithms for graphs of bounded 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 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.

$\endgroup$
  • $\begingroup$ 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 arxiv.org/abs/1304.5591 $\endgroup$ – David Eppstein May 30 '16 at 22:15
  • $\begingroup$ 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. $\endgroup$ – Denis May 30 '16 at 22:36
  • $\begingroup$ See this paper by Vempala on embedding into 2-d grid. ieeexplore.ieee.org/xpl/… $\endgroup$ – Chandra Chekuri May 31 '16 at 1:16
  • 1
    $\begingroup$ 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 arxiv.org/abs/1503.05110 $\endgroup$ – Olf May 31 '16 at 12:10
  • $\begingroup$ @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. $\endgroup$ – Denis Jun 1 '16 at 15:11
2
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.