0
votes
0answers
14 views

Find a kernel in a directed graph.

It's a question from a sample exam I'm trying to solve but with no success yet. Let $G(V, E)$ be a directed graph. set $A \subseteq V$ is a kernel if: i. $\forall u,v\in A \implies (u, v), ...
-1
votes
0answers
42 views

Count suggestions to be send

A site currently has N registered users. As in any social network two users can be friends. We wants the world to be as connected as possible, so we want to suggest friendship to some pairs of users. ...
-1
votes
1answer
39 views

Friends meeting at point

N friends live in different houses spread across the city.There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same ...
1
vote
3answers
24 views

Find an odd-length cycle in an undirected graph.

I have an exam next week and I found a question that I have difficults to solve: Given the following: Input: Simple undirected graph $G(V, E)$. Output: Find an odd-length cycle in $G$ or ...
2
votes
1answer
41 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
2
votes
1answer
38 views

Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
3
votes
0answers
17 views

Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e $, where $a_e>0$. For a fixed $t$ we can define ...
1
vote
0answers
23 views

Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
0
votes
0answers
57 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
0
votes
2answers
29 views

In Dijkstra algorithm, it takes the source, what about the sink?

I'm studying the Dijkstra algorithm, but in my book, the algorithm takes as input only the graph and the source. Why it doesn't ask for the destination vertex? How can it work? Thanks a lot.
0
votes
0answers
31 views

Smart Travelling Agent Problem

Smart travel agent, Mr. X's is to show a group of tourists a distant city. As in all countries, certain pairs of cities are connected by two-way roads. Each pair of neighboring cities has a bus ...
0
votes
0answers
35 views

What is exactly a DFS tree?

Here's a question: Claim: Every time we run the DFS algorithm on the following graph, The DFS tree will be lanyard (?) True \ False, Explanation: I Googled but I'm not pretty ...
0
votes
1answer
24 views

Find Maximum-Matching in a tree $T(V, E)$ in $O(V)$

It's a question from a previous exam that I'm trying to solve with no success. Suggest a Dynamic-Programming algorithm for the following problem: Input: indirected tree $T(V, E)$. ...
2
votes
0answers
76 views

Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
1
vote
1answer
36 views

how do i find the shortest path/route/tour that visits every vertex at lest once

I have a non-directed non-weighted graph and i want to find the shortest path/route/tour (i don't know which is the correct definition) that visits every vertex at least once. Is there an algorithm ...
2
votes
2answers
29 views

Forming a simple polygon from the extrusion of a polygonal chain

Let's say I have a set of vertices connected by edges to form a polygonal chain. Each vertex may be shared by a number of edges to form various sub-chains. An example is shown below. Each edge has ...
0
votes
1answer
24 views

Find all “critical nodes” in a graph

Say there is a graph in which every node is connected to every other by some path. How would i find the particular nodes, which if removed would lead to some of the nodes NOT being connected to all ...
1
vote
0answers
34 views

Using red/blue algorithm on graph with zero cycle

I have a graph where I am trying to find minimum spanning tree using the red rule, blue rule approach. Now the graph is a directed graph and it has a zero cost cycle near the terminal point. In fact ...
2
votes
1answer
108 views

Counting triplets with red edges in each pair

Given a tree having N vertices and N-1 edges where each edges is having one of either red(r) or black(b) color. I need to find how many triplets(a,b,c) of vertices are there, such that on the path ...
0
votes
1answer
46 views

Bipartite graph set cover

I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is an undirected bipartite graph G with the two vertex sets V1, V2. ...
0
votes
1answer
36 views

Find $k$ non-disrupting paths from $s$ to $t$

Given the bidirectional graph $G = (V, E)$ where $V$ = set of Vertices, $E$ = set of Edges; given source node $s$ and destination node $t$. Let $A_i$ ($i = 1, 2,\ldots l$) be the subset of vertices ...
1
vote
0answers
34 views

Dijkstra Algorithm proof

I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and ...
0
votes
0answers
21 views

Algorithm to check if a graph has exactly one perfect matching

What is an algorithm to check if a general graph has exactly 1 perfect matching? Or an algorithm to check whether a graph has more than 1 perfect matching?
0
votes
0answers
38 views

Check if there's a cycle in an undirected graph

I'm trying to find an algorithms that checks if there's a cycle in a given undirected graph G=(V,E). But I didn't succeed. Can anyone give me such an algorithm?
0
votes
1answer
18 views

Minimum k-spanning tree including a given node

Given a Graph (V, E), it is very easy to find the minimum spanning tree using Kruskal's Algorithm. A k-minimum spanning tree is restricted to k nodes, and finding it is actually NP-hard. However, ...
2
votes
2answers
67 views

Shortest path between wikipedia articles

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the ...
1
vote
0answers
56 views

3-pass counting triangles algorithm

Hei guys, I need some hints on Counting subgraphs in data streams. Consider this 3-pass counting triangles algorithm: 1st Pass: count the number of edges |E| in the stream 2nd Pass: sample ...
4
votes
1answer
112 views

Bipartite graph matching like problem.

Let $A=\{a_1,a_2, ..., a_n \}$ and $B=\{b_1,...,b_m\}$ be finite sets. Also $A_1,...,A_k\subset A$ are covering of $A$ and $B_1,...,B_t\subset B$ are covering of $B$. Let $V$ be a set of pairs of ...
2
votes
1answer
31 views

Maximum number of induced $P_3$ in a $P_4$-free graph

Say I have a graph $G$ on $n$ vertices that is $P_4$-free (it has no induced paths of length 4). These are known as cographs. Note that $G$ might not be connected. I'd like to list the induced $P_3$ ...
1
vote
0answers
35 views

O(m) all-pairs shortest paths algorithm for directed acylical graph

An exercise I'm working on asks me to devise an $O(m)$ algorithm for the all-pairs shortest paths of the graph $G = (V, A)$, where $(v_i, v_j) \in A$ implies $i < j$. I'm wondering whether this is ...
0
votes
0answers
24 views

Computer program for decomposing a graph into subgraphs?

Obviously there are programs out there that can find perfect matchings. I am interested in finding out if there is a program that can, for instance, tell when graphs like the cube graph $Q_n$, has ...
1
vote
1answer
51 views

Dijkstra's Algorithm- Two equal weights, one leads to a shorter path. What to do?

I am confused about this situation that happened to me as I was trying to solve a shortest path problem using Dijkstra's Algorithm. '$s$' is the starting point and '$t$' is finish. When I reach to ...
0
votes
0answers
25 views

Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
0
votes
2answers
71 views

Prove choosing $\lceil\frac{V}{2}\rceil$ vertices accounts for at least $\frac{3}{4}$ of edges

Give a polynomial-time algorithm that finds $\lceil\frac{V}{2}\rceil$ vertices that collectively account for at least $\frac{3}{4}$ of the edges in an arbitrary undirected graph. The algorithm I have ...
2
votes
2answers
41 views

Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes ...
0
votes
0answers
37 views

Keller 6 graph and maximum clique

Based on the DIMACS maximum clique benchmark, http://iridia.ulb.ac.be/~fmascia/maximum_clique/, the Keller 6 graph contains a clique of size 59. The clique number however is at least 59 (as can be ...
0
votes
1answer
27 views

Optimal Algorithm for Pursuit-Evasion Scenario

Consider a "game" in which there are two players, A and B. A's goal is to avoid B, while B's goal is to capture A. A and B take turns making single steps over edges from one node to another on a ...
0
votes
2answers
48 views

Wolf cabbage and goat using dijkstra.

A farmer has to cross a river with a wolf, a goat and a cabbage. He has a boat, but in the boat he can take just one thing. He cannot let the goat alone with the wolf or the goat with the cabbage. ...
1
vote
1answer
28 views

Collapse paths in a directed graph algorithm

Let's say there are 4 people: A, B, C and D. A owes B \$100, B owes C \$75, C owes A \$10, C owes D \$85, and D owes B \$1. That can be reduced to: A owes B \$26, A owes D \$64, and C owes D \$20. ...
1
vote
1answer
42 views

Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
1answer
54 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
1
vote
1answer
58 views

Given a collection of ordered sets, find minimal order-preserving superset

Say I have some collection of ordered sets $C = \{S_i\}$. Is there an efficient way to determine the minimal ordered set $S^*$ such that each of the original $S_i \subseteq S^*$, with order ...
0
votes
0answers
84 views

Function acting on a graph

I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows: Given a graph $G= \langle V_G, E_G ...
1
vote
2answers
132 views

Shortest path between three nodes in a graph

I know Dijkstra's algorithm to find the shortest way between 2 nodes, but is there a way to find the shortest path between 3 nodes among $n$ nodes? Here are the details: I have $n$ nodes, some of ...
0
votes
1answer
36 views

Understanding graph layering approximation algorithms

I've been trying to understand the Graph Layering Approximation Algorithms for both Set Cover and Feedback Vertex Set problems. I am using Vijay V. Vazirani's "Approximation Algorithms" book. So let ...
1
vote
1answer
33 views

Algorithm for determining what order to perform a set of tasks in

Consider a set of $n$ items. Each item has a date $d$ by which it must be completed. Each item also has a priority level of $p$ and takes a time $t$ to complete. Is there an algorithm for determining ...
0
votes
1answer
40 views

Max flow min cut algorithm

I am trying to work this max-flow, min-cut out for my finals, but Im really not sure I have got it, I would appreciate some assistance! I understand the theorm, I comes from ford-fulkerson, where the ...
0
votes
2answers
59 views

What is the difference between maximal flow and maximum flow?

I have tried a lot on internet, but I am unable to get a good answer on the difference between maximal and maximum flow in case of network flow. Anybody has an idea? with example would be really ...
1
vote
0answers
29 views

Can cuts of size 2 be detected in linear time in an undirected, unweighted graph?

I'm having trouble finding any literature on the specific subject of 2-edge cut detection. It's not hard to come up with an algorithm that finds all 2-edge cuts in quadratic time, but it's not clear ...
0
votes
1answer
90 views

P, NP-Complete and NP-Hard Problems

I have confusion over P, NP-Complete and NP-Hard problems. I understand a polynomial time algorithm is one which can be solved for a an input string of length n. But why would a problem not be in ...