6

Deciding if a topological ordering with working set of size $\le k$ exists is NP-complete, even in bipartite graphs. We can reduce pathwidth computation to this problem. Let $G$ be a undirected graph, whose pathwidth we want to compute. Now create an directed graph $H$, with vertex $v'$ for each vertex $v$ of $G$. For each edge $(u, v)$ of $G$, create a ...


6

The measure you are trying to minimize is called (directed) bandwidth. Finding a minimum directed bandwidth ordering is NP-hard.


4

One connection could be the following: Given a graph $G$, construct the graph $G'$ in which every connected component of $G$ is a node, and two nodes in $G'$ have a (directed) edge if there is an edge between any two nodes in the connected components they represent in $G$. Sometimes this graph $G'$ is known as the "supergraph" of $G$. Now, its not ...


4

You can color a pair of arcs $(a_1,a_2)$ by the same color, if and only if all the paths from the source to the sink, passing through the arc $a_1$, also pass through the arc $a_2$. Let's consider the set $P$ of all paths from the source to the sink in the graph $G=(V,A)$. Let's denote the subset $P(a) \subset P$ of all paths, passing through the arc $a$. ...


3

There is a simple randomized linear-time algorithm (one-sided error). It is based on HEKTO's idea, using the equivalent relation. The algorithm chooses weight $w_a$ for each arc $a$. Then, the algorithm computes the weighted sum of paths $W(a) = \sum_{p \in P(a)} \prod_{a' \in p} w_{a'}$ for each each arc $a$. All $W$ values can be computed by using two ...


3

I present a refinement on HEKTO's algorithm that I think works and should be more efficient: it runs in $O^*(\min(n^3,m^2))$ time. Theory Let $P(a)$ denote the set of paths that start at $s$, go through the arc $a$, and end at $e$. Lemma 1. $a_1,a_2$ can be given the same color iff $P(a_1)=P(a_2)$. Let $G^*$ be the dual graph of $G$, i.e., each arc of $G$ ...


3

It sounds to me like the greedy algorithm should work, I'm not able to come up with any counter-examples, however, I haven't had time to try to prove the claim either. Terminology Definition. Let $s$ be the start and $t$ be the end vertices (source and sink, respectively). Let $a$ and $b$ be vertices where there is a path from $a$ to $b$ (from now on $a &...


2

By using this algorithm the expected time complexity would not be O(V+E) as we have to visit an edge multiple times. queue.add(s) while(the queue is not empty) for every adjacent vertex v of u if( dist[v] > dist[u] + weight(u,v) ) dist[v] = dist[u] + weight(u,v) add v to the queue But by using the topological sorting, we get the order ...


2

This answer is an improvement for my (already accepted) original answer, which describes an exact, but potentially very slow algorithm. This improvement was inspired by the @pcpthm answer, however I don't employ any randomization here, so this algorithm also produces the exact coloring. For each arc $a \in A$ let's consider a set of arcs $R(a) \subset A$, ...


1

The topological order is not guaranteed to be a solution. Indeed the topological order clearly has length $n$ while there are instances in which it is not possible to stack all boxes. As an example consider $n=2$ boxes that do not fit into one another (e.g., with sizes $(1,1,2)$ and $(1,2,1)$). You need to find the longest path in the original graph. You can ...


1

Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph. Now to prove that the above algorithm returns a topological sorting, we can use some lemmas about DFS $-$ namely the Parenthesis Theorem as well as the White Path Theorem. I will ...


1

A source is a vertex with in-degree zero. An order of the vertices is a topological order if deleting the vertices in that order deletes only sources. Hence, you can verify that an order is topological by deleting one and one vertex, and never deleting a vertex with an in-edge. Your answer is correct, the topological orders are B,{A,D},C,{E,F}, where you can ...


1

You can answer your own question by checking whether, for each edge $(u,v)$ of the graph, $u$ appears before $v$ in each of the three candidate topological orders that you listed.


1

Assume the graph is a directed acyclic graph throughout. The algorithm is correct In the first recursion, the algorithm finds a node $u$ that has no incoming edges. In the second recursion, the algorithm checks whether $p(u)=n$, where for each node $v$, $p(v)$ is 1 plus the length of the longest path starting from that node. There is a path that reaches all ...


1

Unfortunately, there is no "fast" way to count them generally as this problem is #P-Complete. This means that it is basically as hard as every counting version of NP-problems, and is likely not solvable in polynomial time. For small examples such as this one you can come up with some ad-hoc counting technique however. In this case would try listing all ...


1

Approach 1 For example, consider the two orders: 1, 2, 3, 4, 5 and 2, 4, 1, 5, 3. According to your approach, we will get a cycle 1->2->3->4->1. We then remove 3->4 and 4->1, and obtain a graph: ______ / \ 1->2->4->5->3 \______/ Now 5->3 and 1->2 respectively violate the first and the second orders, so we ...


Only top voted, non community-wiki answers of a minimum length are eligible