# Tag Info

## New answers tagged graphs

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 ...
• 23.4k

### 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 ...
• 23.4k

### 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 ...
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 ...
• 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 ...
• 1,106

### 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 ...
• 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 ...
• 34.1k

### 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)
• 10.8k
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 ...
• 188

### 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: ...
• 1,106

### 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 ...

### 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 ...
• 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 {...
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....

### 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 ...

### 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 ...
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 ...
• 7,090

### 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, ...
• 7,090

### 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. ...
• 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 ...
• 23.4k
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 ...
• 13.3k
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 "...
• 93

### 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 ...
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 ...
• 1,403

### 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 ...
• 34.1k
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 ...