2
$\begingroup$

Let $G = (V,E)$ be an $n$-vertex graph, let $R$ be a finite set (to be specific, let us assume that $R = [n]$), and let $W : V \rightarrow 2^R$. Let us call the pair $(G, W)$ a set-weighted graph.

Now let us consider the following problem, which I'll call the Smallest Set Path problem. The problem is given a set-weighted graph $(G,W)$ and two vertices $s$ and $t$ of $G$, find a path $P$ between $s$ and $t$ such that the union of the sets associated with the vertices of the path has the minimum possible cardinality, i.e. $\bigcup_{v \in P} W(v)$ is minimized.

My specific questions:

  1. Was the Smallest Set Path problem studied in the literature?
  2. Was the model of set-weighted graphs as described above considered in the literature in other contexts?
Improve this question
$\endgroup$
3
  • $\begingroup$ Why not post at cstheory.stackexchange.com? $\endgroup$
    – Rodrigo de Azevedo
    Commented Sep 6, 2020 at 23:31
  • 1
    $\begingroup$ I have not seen this problem studied before. Sets on vertices have been used in describing graph dimension or list-colouring or preference lists in stable matching problems, for example. In general, intersection graphs are graphs where each vertex is a set and an edge represents a non-empty intersection of the two vertices. Those sets are sometimes geometrical points, or intervals of real lines, or just discrete sets. $\endgroup$
    – JimN
    Commented Sep 8, 2020 at 6:24
  • 1
    $\begingroup$ without any structure in the graph paths or in the sets weights, essentially all paths woul have to be checked ... unless in a shortest path problem, where a path from s-t going through an intermediate u, it doesn't matter how s gets to u, just the value at u is important. But the unio nof all your sets along the way would be different for every s-to-u path, so essentially all paths would have to be considered. $\endgroup$
    – JimN
    Commented Sep 8, 2020 at 6:29

0

Reset to default

You must log in to answer this question.