4 questions posted in separate pictures i need all of them asap in word file A c

Question

4 questions posted in separate pictures

i need all of them asap in word file

A cohort k spies resident in a certain country needs escape routes in case of emergency. They will be traveling using the railway system which we can think of as a directed graph G = (V, E), V being the cities. Each spy i has starting city s_i elementof V and needs to reach a consulate of any friendly nation; these consulates are in a known set of cities T subsetorequalto V order to move undetected, the spies agree that at most c of them should ever pass through any one city. Give an efficient algorithm that computes paths for each of the spies (or detects that the requirements cannot be met).

Explanation / Answer

A

Here's what I know about the girth problem in undirected unweighted graphs. First of all, if the girth is even, you can determine it in O(n2)O(n2) time- this is an old result of Itai and Rodeh (A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4):413–423, 1978.). The idea there is: for each vertex in the graph, start a BFS until the first cycle is closed (then stop and move on to the next vertex); return the shortest cycle found. If the girth is even the shortest cycle found will be the shortest cycle. In particular if your graph is bipartite this will always compute the girth. If the girth gg is odd, however, you'll find a cycle of length gg or g+1g+1, so you may be off by 11.

Now, the real problem with odd girth is that inevitably your algorithm would have to be able to detect if the graph has a triangle. The best algorithms for that use matrix multiplication: O(O( min{n2.38,m1.41)n2.38,m1.41) time for graphs on nn nodes and mm edges. Itai and Rodeh also showed that any algorithm that can find a triangle in dense graphs can also compute the girth, so we have an O(n2.38)O(n2.38) time girth algorithm. However, the runtime for the girth in sparse graphs is not as good as that for finding triangles. The best we know in general is O(mn)O(mn). In particular, what seems to be the hardest is to find a o(n2)o(n2) time algorithm for graphs with m=O(n)m=O(n).

If you happen to care about approximation algorithms, Liam Roditty and I have a recent paper in SODA'12 on that: Liam Roditty, V. Vassilevska Williams: Subquadratic time approximation algorithms for the girth. SODA 2012: 833-845. There we show that a 22-approximation can be found in subquadratic time, and some other results concerning additive approximations and extensions. Generally speaking, because of a theorem of Bondy and Simonovits, when you have densish graphs, say on n1+1/kn1+1/k edges, they already contain short even cycles, say roughly 2k2k. So the denser the graph is, the easier it is to find a good approximation to the girth. When the graph is very sparse, the girth can be essentially arbitrarily large.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.