Consider a directed graph where the edges are labelled with integer values. In such a graph a path $a \rightarrow b \rightarrow c \rightarrow d$ is valid if the values of the labels of the edges followed strictly increase along the path. I would like to be able to compute standard graph properties taking into account this extra restriction. Have such graphs been considered in the theory literature before?

EDIT: (This should be a comment but it is too long.) There is a simple reduction that follows by replacing each node $A$ by a bipartite graph with indegree($A$) incoming nodes and outdegree($A$) outgoing nodes. We can then connect the relevant incoming nodes to the outgoing nodes that respect the precedence constraints. This would increase the total number of edges by an additive term which is something like the sum of the square of the degrees of the nodes, where $n$ is the number of nodes in the original. Alternatively one can choose a more compact encoding where the nodes in the first half of the bipartite graph are connected in a line and so are the nodes in the second half and the nodes across from the first half to the second just point to the first node with a valid outgoing edge. This reduces the additive expansion factor to something like $n$ times the average degree of the nodes.

Unfortunately, neither reduction preserves crucial properties of the graph. As an example of the problem, if I want to find out if there is a simple path of length $k$ in the original graph, we can't simply look for simple paths in the transformed graphs. The reason is that a simple path in the transformed graph may correspond to a cycle in the original graph. This means that any graph algorithm will have to be modified to take into account which nodes are in fact the same. In particular any algorithm that relies simply on a matrix representation of the graph (or its eigendecomposition) will not work any more.

  • 3
    $\begingroup$ how about the following gadget reduction to a directed graph. replace a vertex of degree $d$ with a $d$-clique and direct edges in the clique in the direction of increasing edge labels. $\endgroup$ – Sasho Nikolov Aug 9 '12 at 22:39
  • $\begingroup$ A problem with this (or similar) gadget reductions is that you can no longer tell the difference between $a \rightarrow b \rightarrow c$ and $a \rightarrow b \rightarrow a$. This is a problem if you want to use the reduction as a black box. $\endgroup$ – Raphael Aug 10 '12 at 11:16
  • $\begingroup$ fair enough. as usual, some context for the problem or at least what actually you do want to compute might help, even for thinking of appropriate references. $\endgroup$ – Sasho Nikolov Aug 11 '12 at 9:57
  • $\begingroup$ I found something relevant in "Centrality metric for dynamic networks" by Lerman, Ghosh and Kang where they consider much the same graph model (arxiv.org/abs/1006.0526). $\endgroup$ – Raphael Aug 13 '12 at 18:04

Your Answer

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

Browse other questions tagged or ask your own question.