Tata Institute of Fundamental Research
Distance Preserving Minors in Interval Graphs
Project Seminar
Speaker:
Kshitij Gajjar
Date:
Saturday, 9 Jan 2016, 10:00 to 11:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: We consider undirected, connected graphs with nonnegative weights on the edges. Additionally, a special subset of vertices called terminals is provided as input. A graph $H$ is said to be a distance preserving minor of $G$ if: (i) $H$ is a minor of $G$, and (ii) the distance between each pair of terminals is exactly the same in $G$ and $H$. Note that the edge weights can be reassigned in $H$ (as long as they are nonnegative). Given a family of graphs $\mathcal{F}$, let $f(k,\mathcal{F})$ be the minimum integer such that every graph in $\mathcal{F}$ with $k$ terminals admits a distance preserving minor with at most $f(k,\mathcal{F})$ vertices.
In this work, we explore interval graphs. Given an interval graph $G$ on $k$ terminals, we describe a method of producing a distance preserving minor of $G$ having at most $k^2$ vertices. Thus, $f(k,\mathcal{I})\le k^2$, where $\mathcal{I}$ is the family of all interval graphs. We also show that there are interval graphs on which our method does not perform optimally. In particular, there exists an interval graph which admits a distance preserving minor of size $O(k\log k)$, but our method produces a distance preserving minor of size $\Omega(k^2)$ for it. Thus, the problem of finding an optimal distance preserving minor for interval graphs remains open.
| Speaker: | Kshitij Gajjar |
| Date: | Saturday, 9 Jan 2016, 10:00 to 11:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: We consider undirected, connected graphs with nonnegative weights on the edges. Additionally, a special subset of vertices called terminals is provided as input. A graph $H$ is said to be a distance preserving minor of $G$ if: (i) $H$ is a minor of $G$, and (ii) the distance between each pair of terminals is exactly the same in $G$ and $H$. Note that the edge weights can be reassigned in $H$ (as long as they are nonnegative). Given a family of graphs $\mathcal{F}$, let $f(k,\mathcal{F})$ be the minimum integer such that every graph in $\mathcal{F}$ with $k$ terminals admits a distance preserving minor with at most $f(k,\mathcal{F})$ vertices.
In this work, we explore interval graphs. Given an interval graph $G$ on $k$ terminals, we describe a method of producing a distance preserving minor of $G$ having at most $k^2$ vertices. Thus, $f(k,\mathcal{I})\le k^2$, where $\mathcal{I}$ is the family of all interval graphs. We also show that there are interval graphs on which our method does not perform optimally. In particular, there exists an interval graph which admits a distance preserving minor of size $O(k\log k)$, but our method produces a distance preserving minor of size $\Omega(k^2)$ for it. Thus, the problem of finding an optimal distance preserving minor for interval graphs remains open.
In this work, we explore interval graphs. Given an interval graph $G$ on $k$ terminals, we describe a method of producing a distance preserving minor of $G$ having at most $k^2$ vertices. Thus, $f(k,\mathcal{I})\le k^2$, where $\mathcal{I}$ is the family of all interval graphs. We also show that there are interval graphs on which our method does not perform optimally. In particular, there exists an interval graph which admits a distance preserving minor of size $O(k\log k)$, but our method produces a distance preserving minor of size $\Omega(k^2)$ for it. Thus, the problem of finding an optimal distance preserving minor for interval graphs remains open.