Hot answers tagged

3

This paper seems closely related. The authors study the same problem you define with the exception that edge costs are uniform and do not depend on the distance of the endpoints. This version of the problem is NP-hard. The paper provides references to variants of the problem, some involving costs and lengths. Perhaps you can see if one of the NP-hardness ...


3

The Bentley-Ottmann algorithm can be used to find all intersections between edges, and then you can add a node at each such intersection.


3

This is the Hamiltonian path problem on partial grid graphs (i.e., graphs which are arbitrary subgraphs of grids) which is known to be NP-complete. Thus, no polynomial algorithm exists unless P = NP. A good bet here would be to try heuristics and (exact) algorithms designed for Hamiltonian path. In particular, if you model the problem as an instance of ...


2

Any primitive operation that can be done with edge list, also can be done in adjacency list, but the main difference between them is time complexity of the primitive operations, for example, when you want find all adjacent vertices to some vertex $v$ the time complexity is $\Theta(|E|)$ but the same operation on adjacency list is $\Theta(deg(v))$ where $...


2

Create an undirected weighted graph $G=(V,E)$ where $V=\{C_1,C_2,M_1, \dots, M_n\}$. For each $i=1,\dots,n$ add the edge $(C_1, M_i)$ of weight $a_i$ and the edge $(C_2, M_i)$ of weight $b_i$. For each pair of distinct indices $i,j=1,\dots,n$ add the edge $(M_i, M_j)$ of weight $d_{i,j}$. You are looking for a $C_1$-$C_2$-cut of minimum weight, namely a ...


2

Your problem is solved in Kahn and Kim, Entropy and sorting.


2

More generally, this area is known as geometric deep learning, i.e., it encompasses learning not only on graph but on other non-Euclidean domains. A good broad start is the survey of Bronstein et al. [1], after which I can recommend basically any material by Bronstein like his many excellent presentations (also available on Youtube - just do a search). For ...


2

I think what you're looking for, like I was, is the Minimum Spanning Tree. Here is an article about it.


2

An arc is said to be a bridge if its removal increases the number of connected components of the graph. Further, an arc is a strong bridge if its removal increases the number of strongly connected components. In your case, you are likely interested in finding all strong bridges in a digraph. A simple $O(n+m)$-time algorithm, where $n$ is the number of ...


2

1 is wrong. The problem is NP-Complete by an easy reduction $f$ from the clique problem. Let $\langle G,k \rangle$ with $G=(V,E)$ be an instance of (the decision version of) clique. If $k$ is odd then the reduction is the identity function, i.e., $f(\langle G,k \rangle)=\langle G,k \rangle$. Otherwise create a new graph $G=(V', E')$ with $V' = V \cup \{v\}$...


2

Regarding the first part. Answer 1 is incorrect. Consider the graph $G = (\{1,2,3,4,5,6\}, \{(1,2), (1,3), (2,3), (3,4), (4, 5), (4,6) \})$. The maximum degree of $G$ is $3$ but the degree of $x_{(3,4)}$ in $\widetilde{G}$ is $4$. Answer 2 is correct. Consider an edge $e=(u,v)$ of $G$. The number edges distinct from $e$ that are incident to $u$ (resp. $v$) ...


2

Let's check these in reverse order. Question B: your reasoning looks good as it demonstrates that both (1) and (2) are not strong enough. The choice (4) is a possible bound, but it's not as tight as it can be. Your example is extremal in a sense that you can't make the degrees any larger, meaning that your bound is, as the question asks, "closest ...


2

The statement is false. Take a look at the following graph: In one BFS run, you will get the following tree: That has a distance of $1$ between $u$ and $v$, while in a different run, you could get another tree: Which has a distance of $3$ between $u$ and $v$


2

To see whether a "reduction is correct and well-defined", first look at the definition: what is a reduction? In this case, you require a so-called Karp reduction or a polynomial-time reduction from Edge-Coloring to Vertex-Coloring. In particular, it must hold that (i) the process runs in polynomial time and (ii) an instance $G$ of Edge-Coloring has ...


1

Run BFS and traverse only edges with weight $1$, now if the graph isn't connected, then add edges with weight $2$ to traversed graph until your graph form a tree. The running time is $\Theta(E+V)$. Note that you can also use Dijkstra that in this case has linear running time...


1

For every edge $(u,v)$ with weight $2$, create a new node $w_{u,v}$. Discard the edge $(u,v)$, and instead of it add two edges $(u,w_{u,v})$ and $(w_{u,v},v)$ with weight $1$. Now you can use a standard unweighted pathfinding algorithm, such as BFS.


1

Suppose that no symbol has frequency $0$ (otherwise the claim is false). Consider the tree $T$ built by the standard greedy algorithm to construct the Huffman code. This algorithm maintains a forest $F$ where each node $v$ is associated with a frequency $f_v$. Initially $F$ contains a collection of isolated vertices, one per input symbol (with the ...


1

Yes use induction. You will assume that $G_\pi$ is a forest, and you want to prove that $G_{\pi'}$ is also a forest, where $\pi'$ is $\pi$ after one step of the DFS algorithm. The key point, is that a forest is a graph without cycles. So basically, you want to show that no new cycles where created in the last step. To prove this, you will want to have a ...


1

I think one of an important parts of reduction for languages like Clique and Subset-sum is the integer we have given next to the input. That is $k$ for Clique which tells us which size of the clique we are looking for and $d$ in Subset-sum that tells us the sum of a collection of numbers. I have drawn little pictures for you to see how this works. For ...


1

The reduction from $Clique \leq_P SubsetSum$ is incorrect. Take a graph $G$ with four vertices $(v_1, ..., v_4)$, edges $(v_1, v_2), (v_3, v_4$) and let $d = 4$. Then $A = \{1,1,1,1\}$ (assuming $A$ is a multiset). Clearly there is a subset in $A$ whose sum is 4 but there is no clique of size 4 in $G$. As for the reduction $SubsetSum \leq_P Clique$, your ...


1

Yes, there is a linear time algorithm. After removing $e=(n_1,n_2)$ we run DFS twice as follow First, run DFS from $n_1$ and check, $n_2$ reachable from $n_1$ or not. Second, run DFS from $n_2$ and check whether $n_1$ reachable from $n_2$ or not. If after running DFS twice, $n_1$ reachable from $n_2$ and $n_2$ reachable from $n_1$ we conclude that removing ...


1

Consider the following graph: A possible DFS starting from $a$ visits the vertices in this order: $\langle a, b, c, d \rangle$ producing the cross-edge $(c,b)$. A possible DFS starting from $b$ visits the vertices in this order: $\langle b, a, c, d \rangle$ producing the cross-edge $(d,c)$. A possible DFS starting from $c$ visits the vertices in this order: ...


1

Because you run BFS from $w$, The BFS produce a shortest path tree $\mathcal{T}$ that contain shortest path from $w$ to other vertices. On the other hand the claim say that: any tree $\mathcal{T}$ that produced by BFS, the distance between $u,v$ is $x$, clearly it's not true, because the BFS guarantee the distance between $w$ and $\forall v\in V\setminus w$ ...


1

A clique $C$ on $k$ vertices has $\binom{k}{2}$ edges, i.e., all unordered pairs $\{a,b\}$ such that $a$ and $b$ are distinct vertices in $C$. The number of such pairs is $\frac{k (k-1)}{2} = \binom{k}{2}$. You can count these by focusing on the number of ordered pairs first. To make an ordered pair $(a,b)$ you have $k$ choices for $a$ and $k-1$ choice for $...


1

Use BFS to find a shortest path $v\rightsquigarrow u$, and then $u\rightarrow v \rightsquigarrow u$ is the cycle you want. Try to prove for yourself and see why this works!


1

Yuval describes a boolean CNF formula that is satisfiable iff the graph is not connected, using $|V|$ variables; and a boolean CNF formula that is satisfiable iff the graph is connected, using $|V|^2$ variables. I describe here a boolean CNF formula that is satisfiable iff the graph is connected, using $O(|V| \lg |V| + |E|)$ variables. If $|V|$ is large ...


1

Let $\ell_x$ be the left sub tree at node $x$, Let $r_x$ be the right sub tree at node $x$. So the size of $\ell_x$ is $\mid\ell_x\mid$, and size of $r_x$ is $\mid r_x\mid$. Let $T(n)$ be number of nodes our procedure visited during in-order traversal. So when you recurs on the left sub tree at node $x$, the size of problem is $T(n-1-\mid r_x\mid)$, because ...


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