## Iterative Depth First Search for cycle detection on directed graphs

I found this pseudocode on Wikipedia, and looks very elegant and intuitive:

L ← Empty list that will contain the sorted nodes while exists nodes without a permanent mark do     select an unmarked node n     visit(n)  function visit(node n)     if n has a permanent mark then         return     if n has a temporary mark then         stop   (not a DAG)      mark n with a temporary mark      for each node m with an edge from n to m do         visit(m)      remove temporary mark from n     mark n with a permanent mark     add n to head of L 

I am trying to write an iterative version for this using 3 marks (UNVISITED, VISITED, PROCESSED), but the lack of tail recursion really bothers me.

How should I approach this?

## Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG

We are given directed weighted graph with possibly some cycles with $$N$$ nodes and $$M$$ edges. Let’s observe all the shortest paths from $$1$$ to $$N$$ in this graph, finding the single-source-shortest paths from $$1$$ in the normal graph and the single-source-shortest path from $$N$$ in the inverse graph we can check for each edge whether it belongs to some shortest path or not.

If we take all the edges that belong on some shortest path and build a separate graph we will get a directed acyclic graph. How can we prove that this graph will never have a cycle? I haven’t written many proofs on graphs before, so I solved the problem, however I’m not sure why this will always hold.

## performance of directed mapped vs two-way set associative

Suppose you have two processors that have different setups of cache. The first has a cache that can store up to 8 words using direct mapped with a two-word block size. The second has a cache that can store up to 8 words in total with two-way set associative with one-word block size. Both of these caches are initially empty.

I have to find scenarios with at least one cache hit with only five consecutive memory caches for each type of the cache above.

1. Where the first cache performs better than the second
2. Where the second cache memory performs better than the first

I didn’t understand how many blocks, I can use. I know how to do for one word blocks. Not sure how to do this.

## Is there a term for these “descendancy” subgraphs of directed acyclic graphs?

Consider a directed acyclic graph $$G$$ with vertex set $$V$$. Choose a vertex $$v$$, and let $$H$$ be the subgraph containing $$v$$ and all other vertices in $$G$$ that are reachable from $$v$$ (along with the associated directed edges).

(In other words, if we choose $$v \in V$$, then we are interested in the subset consisting of $$v$$ and all of its descendants).

Is there an accepted term for this particular subset of vertices (or the subgraph)? It seems to be a fairly elementary concept so I expected to find a commonly used phrase for this, but my search is coming up empty so far. Thanks for any answers or leads!

## Linear space reduction from Directed Hamiltonian Path Problem to 3SAT

Is there a reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every graph $$G$$ with $$n$$ vertices to a formula $$\varphi$$ with at most $$O(n)$$ clauses?

Since Cook Levin Theorem shows a reduction that proves 3SAT is NPC, almost all of the literature deals only with reductions from 3SAT, and only rarely one can find in the literature reductions to 3SAT.

After searching the web I found this and other cites that have the other direction of reduction (from 3SAT to dHamPath).

## Determine whether there exists a path in a directed acyclical graph that reaches all nodes without revisiting a node

For this I came up with a DFS recursion.

Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cant keep recursing.

The element with the highest post number or the last element you visit should be the first element in your topological ordering.

Now do another DFS recursion that executes on every node called DFS_find:

DFS_find(Node): if (node has no neighbors): return 1; otherwise: return 1 + the maximum of DFS_find(Node) for all neighboring nodes

Execute DFS_find(Node) on the first node in your topological ordering. If it returns a number equal to the number of vertices, then a directed path that crosses every node once, exists. Otherwise it does not.

How can I prove whether or not this algorithm is correct?

I think this may be a little less time efficient than the classical way to just do a topological sort and then check if each consecutive pair has an edge between them.

## Minimum number of edges to remove to disconnect two node sets $A$ and $B$ in a directed graph

We have directed graph $$G$$ (not necessarily a DAG), two disjoint sets $$A$$, $$B$$, of vertices.
I need to plan an algorithm returning the minimum number of edges that need to be removed, such that there will be no path from any node in $$A$$, to any node in $$B$$ and vice versa.

I had the idea using max flow min-cut to find the minimum number of edges needing to be removed such that there won’t be a path from $$A$$ to $$B$$, and then using the algorithm again on $$B$$ (so there won’t be a path to $$A$$).
The problem is that the sum of these minimum number of edges isn’t necessarily the “global” minimum.

Does there even exist such an algorithm running in polynomial time?

## How can Conflict Directed Backjumping be built?

I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach?

In AIMA,chapter 6 describes Forward Checking can support conflict set with no extra work. So, we do not need to code CBJ if we already build Forward Checking and Backtracking algorithm.

## Find a longest path with k vertices in a directed graph

Assume a directed acyclic graph G=(V,E), the goal is to find a path (with k vertices) so that the sum of edge weights is the maximum.

## Partition into paths in a Directed Acyclic Graphs

I have a directed acyclic graph $$G=(V,A)$$, I want to cover the vertices of $$G$$ with a minimum number of paths such that each vertex $$v_i$$ is covered by $$b_i$$ different paths.

When $$b_i=1$$ for all the vertices, the problem can be solved in polynomial time. But I am searching for the complexity of the problem when $$b_i>1$$ for at least one vertex $$v_i$$, do you know about any results that may help me?