Friday, August 19, 2005

hypergraphs, strongly connected components

In a hypergraph constructed in a way mentioned before, we seem to be finding hyper-articulation points (or hyper-articulation edges). The decomposition algorithm seems to remove some hyperedges. The resultant components are somehow, hyper-strongly connected.
Assume we do a DFS on the associated directed bipartite graph, also giving each vertex its [BEGIN,END] times as usual. BEGIN meaning the first time when it is found, and END meaning the time when it is blackened, from grey.

Let V -> u -> W be a hyperedge, with u being the "dummy" node corresponding to the hyperedge. Also, let v \in V and w \in W be two representatiove elements of the sets V and W.

fact: END(u) > END(w) for all w \in W /*this is anyway true */

((END(v) > END(u)) and () for all v \in V, then node u is not part of any zero-weight cycle. /*the usual cycle condition*/

This can be stated as the following: no B-arc of the hypergraph is a backward edge in a DFS

Now, if the node u corresponding to a hyperedge E has the following property: for every vertex v such that v->u is a B-hyperedge(beginning part of a hyperedge), END(u) >
Preprocessing step: How do we we obtain zero-contributions from some edges? i.e., when we have a equation like q1 + q2 + q3 = 0, we immediately write it as q1 = q2 = q3 = 0. What does this mean? So a preprocessing step could remove vertices which have all incoming or all outgoing edges (actually hyperedge components) to it. Then we remove those edges completely (remember, we have to remove the hyperedge completely) from the graph. This is called a preprocessing step, as this can be done fastly and is something we have to do.
Can we do index set splitting fastly for unitary graphs?
The main
there does not seem much point in reversing the directions of edges ala Tarjan's Strongly Connected Components algorithm. This is because, we are interested in solving Bq=0. This trivially means that -Bq=0 !!!!
So the information in the DFS info of B is contained in the DFS info of -B. Or is it? Since we have to satisfy both Bq = 0 and -Bq=0, what does the undirected hypergraph give us? Maybe nothing: We are losing lot of information by looking at the undirected hypergraph.

brings us back to the question: we should look at either Bq=0 OR -Bq=0. What additional information is present in looking at both (not the undirected hypergraph ofcourse)?
There are three types of nodes in the graph: the v's the w's and the e's (which are actually the edges of the hypergraph, but can be recast as vertices of the new graph).
Observation: every edge has to pass through the switch box of the E vertices.
We are looking for a cycle in this graph that passes through atleast one v in V and atleast one w in \W.
or, we are looking to remove edges that donot participate any cycle (what does this mean)?
Look at Cormen book for quite good notes on Shortest paths: chapters 24, 25: I am not sure what algorithm should we use for the hypergraph. Once a hypergraph has been constructed, or even the equivalent bipartite graph, the edge weights can be thought of as unit (+1). So, we may be able to do away with a Dijkstra's algorithm????

No comments: