New answers tagged

0 votes
Accepted

weighted graph separation algorithm proof

Your algorithm is incorrect. Let $G$ be a cycle on $4$ vertices where edge weights alternate between $2$ and $4$ and consider $k=5$. The graph obtained from $G$ by keeping all and only the edges with ...
user avatar
  • 23.4k
0 votes

Converting a Directed Acyclic Graph to a Directed Tree

If the undirected version $G'$ of the DAG $G=(V, E)$ is not connected, then there is no polytree that contains all vertices in $V$ and only a subset of the edges in $E$. If $G'$ is connected, then you ...
user avatar
  • 23.4k
0 votes

Calculate shortest cycle that contains node $s$

In an undirected graph $G$, remove vertex $v$ and find the shortest path between all pairs of vertices in $N(v)$; i.e. Find $d(a,b):=$shortest path between $a,b\in N(v)$ in graph $G'=G-\{v\}$. Result ...
user avatar
1 vote
Accepted

Calculate shortest cycle that contains node $s$

To answer the question "why is the linked algorithm correct?", first of all notice that it works for directed graphs. We want to show that the shortest cycle containing $s$ consists of a ...
user avatar
  • 23.4k
1 vote
Accepted

Efficient algorithm to count number of intersections of n sets

Assuming you really need the number for all pairs of sets and hearing that we are thinking of users in communities you could use the following algorithm which relies on the idea that the the average ...
user avatar
  • 1,106
0 votes

Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?

Let a sequence of $n$ elements. If all pairs of consecutive elements are equal, then by transitivity all elements are equal. By contradiction, if they are not all equal, then there is certainly a pair ...
user avatar
  • 3,910
1 vote
Accepted

safe edge theorem proof clarification

Although correct, that statement, "$w(T') = w(T) - w(x,y) + w(u,v) \le w(T)$" alone is indeed confusing, since it leaves the impression that $w(T')$ might be smaller than $w(T)$. Well, the ...
user avatar
  • 34.1k
0 votes

Recursively deleting spanning forest from graph, how many iterations maximum to get to the empty graph?

This was an irrelevant answer that I had to replace manually (since I cannot delete from my current device)
user avatar
  • 10.8k
3 votes
Accepted

Are Control Flow Graphs(CFG) planar?

If this is wrong, can we always write a program whose CFG is planar without loss of function? Yes, we can. Suppose we have an arbitrary CFG $G$, which is a finite graph. It is known that any finite ...
user avatar
2 votes

Are Control Flow Graphs(CFG) planar?

First: If we use your definition of a CFG, they still can be non-planar. Consider the following (silly) piece of code: ...
user avatar
  • 1,106
0 votes

What is the correct complexity of All paths from Source to Target DFS solution?

For directed graph :- Suppose there are 7 vertices {0,1,2,3,4,5,6} and consider the worst case where every vertex is connected to every other vertex => No of edges required to reach from x to y ...
user avatar
2 votes

Name and complexity of this problem on bipartite graphs

I don't know a prior result on this particular problem. However, I can show this problem is NP-hard by reducing the hitting set problem. Suppose we are given an instance of the hitting set problem as ...
user avatar
  • 826
1 vote

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Induction on the order of G . True for |G| = 1. Assume for |G| = n let prove it for |G| = n +1. Choose a vertex v of minimum degree . Consider H = G - N[v]. Clearly a(G)> = 1 + a(H) > = 1 + sum {...
user avatar
1 vote

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

There are several non-probabilisitc proofs : 1/ using greedy algorithm deleting minimum degree : See : https://www.sciencedirect.com/science/article/pii/S0166218X13001339 https://onlinelibrary.wiley....
user avatar
0 votes

Optimality of DSATUR on interval graphs

Yes. DSATUR produces an optimal coloring for interval graphs. My idea is as follows (Please identify any potential issues). We know that a) In DSATUR, once a new vertex has been colored then we should ...
user avatar
0 votes

Better results for minimum vertex cover algorithms

I proposed a better approximation algorithm for vertex cover problem (a 1.999999-approximation algorithm by solving a well-known SDP model and a randomized procedure). It is not published, yet. But, I ...
user avatar
2 votes
Accepted

Transitive Closure of a graph

Using Kosaraju's algorithm, you can compute the strongly connected components (SCC) of $G$ in linear time. The metagraph (or graph of the SCC) is well known to be a DAG. You can then compute the ...
user avatar
  • 7,090
2 votes

Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book

I'm not sure what the problem is, but I will still try to answer. The predecessor of $v$ in a path from $u$ to $v$ is the last vertex seen before $v$. Since there exists a path from $u$ to $v$ then, ...
user avatar
  • 7,090
0 votes

Find a simple path from S to T in a directed graph so that the product of its weights is maximum

$$ \max \prod_{i}p_i\iff \max \sum_{i}\log p_i,\,p_i>0 $$ So it's nearly equal to ask "single source longest path", which is NP-hard in most graphs. There is a Polynomial solution on DAG. ...
user avatar
  • 93
1 vote
Accepted

Find a simple path from S to T in a directed graph so that the product of its weights is maximum

The problem is NP-hard by a reduction from the Hamiltonian-path problem. If all edge weights are set to some constant $c>1$ and $P$ is a simple path from $s$ to $t$ that maximizes the product of ...
user avatar
  • 23.4k
2 votes
Accepted

Are the clusters in a cluster graph complete graphs?

You are reading it correctly. Those are two different uses of the word "cluster graph". In graph theory, and usually in computer science, when you refer to a cluster graph it is of the ...
user avatar
  • 13.3k
3 votes
Accepted

Difference between cost and the heuristic function in A* search

Necessary heuristic function is needed for 2nd image, I can't tell why it's so in that image. But for the common A star algorithm, heuristic is an "Oracle" that guide algorithm to make "...
user avatar
  • 93
0 votes

Question about Complete partially Directed Acyclic Graph

This answer includes some clarification and an answer. The figure in the question is from here. Some clarifications regarding the terms: Two DAGs are equivalent iff they have the same skeletons and ...
user avatar
3 votes
Accepted

Topological sort of minimum costs to finish interdependent tasks

I am assuming here that you are allowed to start tasks in parallel if there is no dependency between them, otherwise I think that no matter what order you do, the total time needed to finish the ...
user avatar
  • 1,403
3 votes

Topological sort of minimum costs to finish interdependent tasks

This problem is basically to find the longest path in a directed acyclic graph (DAG). Let $cost[t]$ be the number of days it takes to do task $t$. Let $m[t]$ be the minimum number of days to finish ...
user avatar
  • 34.1k
2 votes
Accepted

FPT algorithm for dominating set

See the FPT algorithm in Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. Since the proof applies for $k$-degenerate graphs, it also applies for graphs whose ...
user avatar

Top 50 recent answers are included