minimum storage representation
this post is about the well-known graph-theoretic problem "Minimum Storage Representation"
Given a graph (V,E) determine a minimal graph (V, E*) such that there is a (directed) path from i to j in G iff there is a (directed) path from i to j in G*.
Basically, we have to find a minimum storage representation of the graph, which still allows us to answer reachability queries. Of course, there is a certain trade-off between minimum query time and minimum storage representation, but we do not care about it now.
In case if we impose a restriction that E* \subseteq E then the problem is named as Minimum Equivalent Graph (MEG) if a graph is undirected or Minimum Equivalent Digraph (MED) if graph is directed. MED has the number GT33 in Garey, Johnson
It is well-known that a decission version of the MEG(MED) problem (given graph G and the number k, if there exist a representation of the size \leq k) is NP-complete. By reduction of Directed Hamiltionian Circuit.
What happens in case if we relax a restriction that E* \subset E? In that case the problem is named a transitive reduction of G. For each acyclic graphs MEG = transitive reduction and for each acyclic graph there exists only one MEG.
Aho, Garey and Ullman (Aho Garey Ullman The transitive reduction of a directed graph, SIAM. J. Computing, 1(1972)) have shown that transitive reduction of each graph can be computed in polynomial time (in O(|V||E|))
GRAPH ENCODABILITY Given directed graphs (V,A) and (V',A') is the an encoding of the first graph into the second one: a one to one function V->V', such tht for each edge \in A, there exists a dirfected path in A'
This problem is solvable in PTIME for undirected graphs. The problem is solvable for directed graphs in PTIME if the first graph (which must be encoded) is fixed. In general case, the problem is NP-hard for for directed graphs. In case if egdes are weighted then even undirected version of the problem is NP-hard (A. Rosenberg, Data Encoding and Their Costs, Acta Informatica 1978, referenced by Johnson, The NP-completeness column, J. of Algorithms, 1982)
Given a graph (V,E) determine a minimal graph (V, E*) such that there is a (directed) path from i to j in G iff there is a (directed) path from i to j in G*.
Basically, we have to find a minimum storage representation of the graph, which still allows us to answer reachability queries. Of course, there is a certain trade-off between minimum query time and minimum storage representation, but we do not care about it now.
In case if we impose a restriction that E* \subseteq E then the problem is named as Minimum Equivalent Graph (MEG) if a graph is undirected or Minimum Equivalent Digraph (MED) if graph is directed. MED has the number GT33 in Garey, Johnson
It is well-known that a decission version of the MEG(MED) problem (given graph G and the number k, if there exist a representation of the size \leq k) is NP-complete. By reduction of Directed Hamiltionian Circuit.
What happens in case if we relax a restriction that E* \subset E? In that case the problem is named a transitive reduction of G. For each acyclic graphs MEG = transitive reduction and for each acyclic graph there exists only one MEG.
Aho, Garey and Ullman (Aho Garey Ullman The transitive reduction of a directed graph, SIAM. J. Computing, 1(1972)) have shown that transitive reduction of each graph can be computed in polynomial time (in O(|V||E|))
GRAPH ENCODABILITY Given directed graphs (V,A) and (V',A') is the an encoding of the first graph into the second one: a one to one function V->V', such tht for each edge \in A, there exists a dirfected path in A'
This problem is solvable in PTIME for undirected graphs. The problem is solvable for directed graphs in PTIME if the first graph (which must be encoded) is fixed. In general case, the problem is NP-hard for for directed graphs. In case if egdes are weighted then even undirected version of the problem is NP-hard (A. Rosenberg, Data Encoding and Their Costs, Acta Informatica 1978, referenced by Johnson, The NP-completeness column, J. of Algorithms, 1982)
posted by alopatenko at 2:38 PM
<< Home