Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

4,326 questions
Filter by
Sorted by
Tagged with
16 views

Do the Prim’s algorithm and the Kruskal’s algorithm always obtain the same minimum spanning tree (MST) on a given input graph? [duplicate]

Do the Prim’s algorithm and the Kruskal’s algorithm always obtain the same minimum spanning tree (MST) on a given input graph? I have tried drawing a bunch of graphs with non-unique edges and ...
1k views

Find shortest path between two vertices that uses at most one negative edge

Given a directed graph $G = \langle V,E \rangle$ with $n$ vertices and $m$ edges and a weight function $w:E \rightarrow \mathbb{R}$, together with two vertices $s$ and $t$ in $V$: Describe an ...
79 views

modify dfs to find longest path

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
97 views

How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...
22 views

Maximal edge weight clique of given size

Let $G$ be an undirected fully connected weighted graph with $N=|V|$ vertices. Given $M<N$ we wish to choose $M$ vertices such that the sum of weights between the chosen vertices is maximal, i.e. ...
66 views

46 views

Shortest path as a linear program

I just encountered this formulation of the shortest $s$-$t$ path problem as a linear program in a homework. I don't understand exactly the meaning of the variables and restrictions. Here, $G = (V, E)$ ...
80 views

Prove finding a spanning tree with no more than 50 leaves is NP-hard

This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard? I think it is and I'm trying to ...
39 views

Find all combinations of adjacent records matching a graph template

I have a graph theory or combinatorics problem that probably has a solution, but I haven't been able to find it. The problem can be simple: in the second figure below, choose one yellow block from ...
1k views

Does the Minimum Spanning Tree include the TWO lowest cost edges?

Wikipedia's Minimum Spanning Tree reads: Minimum-cost edge If the minimum cost edge e of a graph is unique, then this edge is included in any MST. Proof: if e was not included in the MST, removing ...
58 views

Graph coloring problem with violations

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where Let $k$ be the number of colors Let $B$ be the set of edges violating coloring, i.e., B := \{(u,...
29 views

Pure Directed Graph

How can a directed graph be efficiently represented in a purely functional language like Haskell? Could someone suggest relevant materials on this topic? (functional pearls perhaps?) Thanks.
55 views

Cost of finding optimal elimination order in a planar tensor network?

Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order? For example, take the following ...
22 views

Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
49 views

Is the MCP language really np hard?

I have a graph $G=\left(V , E\right)$ and source $s$ and target $t$. I also have a weight function $w: V\rightarrow \mathbb{R^+}^k$, meaning a vertex given $k$ non negative weights. There is an upper ...
44 views

Finding the shortest path with this algorithm

This is a homework question. We want to find the shortest $s$-$t$ path in an undirected weighted graph $G = (V, E)$ with capacities $c_e$ for each edge and positive weights. Let $S'$ be the set of all ...
12 views

Is it possible to use a random seed in the form of an integer to uniformly sample items from an array in sublinear time?

For example, given an array of reservation IDs: ...
69 views

Restore planar graph from vertex degrees

Suppose you are given a list of vertices (with known positions) and their respective degrees, find any set of non-intersecting edges that satisfies the vertex degrees. Or, in other words, connect the ...
26 views

Given the hypercube Q3 of 8 vertices, what is x + 10y where x is the minimum vertex cover set size and y is the maximum independent set size?

Sorry for the shoddy formatting in the title, here's something clearer: Given the hypercube Q3 of 8 vertices, what is x + 10y where x is the minimum vertex cover set size and y is the maximum ...
44 views

How to solve min cost perfect matching problems?

I'm trying to design an algorithm for the following generalized assignment problem. We converted the problem to a weighted bipartite graph constituted of two sets $A$ and $B$ where $|A| \ne |B|$. Any ...
58 views

Why are there here at most $\vartriangle \cdot E$ paths?

I ran across this proof from the following paper: Finding and Counting Given Length Cycles But I do not understand the third line. There are at most $\vartriangle \cdot E$ such paths and they can ...
61 views

Find nodes at k distance from given source node in an undirected cyclic graph if k<=1e9

I have encountered this problem many times. In an undirected graph, you need to get all the nodes/one node that is k distance away from the given source node (...
15 views

Algorithms for generating graphs with different global and local topology

I want to generate different kinds of graphs with different topological properties. I am interested in modeling the global structure as well as the local structure. That is, I not only want to ...
21 views

Minimise vertex loss converting DCG to DAG

I have a DCG that I want to lay out with the parents on the left and children to the right. I want to maximise the number of all children present to the right of all parents whilst minimising the ...
25 views

On a coloring that uses $2\cdot a\left( G \right)$ colors

Denote $G=\left( V, E \right)$ arboricity by $a\left( G \right)$. I'm trying to understand why $G$ is $2\cdot a \left( G \right)$-colorable. I came across this post. Both the OP and the answer say ...
66 views

Eulerian Path and Circuit Algorithm - How does it work?

I have found several versions of algorithms the find a Eulerian path/circuit in a graph, but I'm having trouble understanding why they work. For example http://www.graph-magics.com/articles/euler.php ...
20 views

Covering Salesman Problem (CSP) polynomial reduction to the TSP

I am facing one problem that consists in polynomially reducing the Coverging Salesmen Problem (CSP) to the Traveling Salesman Problem (TSP). So, let me first define the CSP. The CSP, I am working on, ...
60 views

Maximum matching with social distancing

Let $G = (X\cup Y, E)$ be a bipartite graph. Suppose $X$ contains people, $Y$ contains seats in a theatre, and each edge $(x,y)$ has a weight representing how much person $x$ is willing to pay for ...
21 views

Finding the minimized absolute difference of shortest paths of two different starting vertices

I am relatively new to algorithms and I hoped you can help me with the following question. The question can be summarized as follows: Given two different starting vertices, A and B, and a destination ...
176 views

True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)

Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph. True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
27 views

Determining the number of reachable vertices from every vertex in a directed acyclic graph

Let $G = (V, E)$ be a directed acyclic graph, which is quite sparse (in the examples I have in mind, $|E| \approx 10|V|$ or so). For each vertex $v \in V$, let $f(v)$ be the number of vertices ...
39 views