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,028
questions
1
vote
1answer
10 views
Select fixed-size connected induced subgraphs in a graph
I have a connected graph with $nk$ vertices, and would like to select $n$ disjoint induced subgraphs with $k$ vertices such that each subgraph is connected, selecting one out of all possible solutions ...
2
votes
1answer
27 views
Given graph G and vertices v and w can you non-deterministically walk the “least Hamiltonian path” from v to w, if it exists?
My understanding of non-deterministic algorithms is that they're "as lucky as you want".
...you can think of the algorithm as being able to make a guess at any point it wants, and a space ...
-1
votes
0answers
12 views
Is this a binomial distribution histogram? [closed]
I want to know if this can be considered a binomial distribution histogram, and if it Could have come from an Erdos-Renyi model
1
vote
0answers
26 views
Does this algorithm (least Hamiltonian path, checking vertex count, and no duplicates) decide Hamiltonian paths? If so, what is its space complexity?
Let G be a graph
Suppose G has N vertices
Let H be the ...
2
votes
0answers
46 views
Find minimum cycler in a graph
A graph G has n vertices and m edges
The Minimum Cycler of G is a set S of edges of minimum total weight such that every cycle in G contains at least one edge in S.
Devise an algorithm that finds the ...
1
vote
0answers
18 views
Representation of connected components in the $O(|E|)$ time/space variant of Karger's algorithm
I'm trying to understand the various optimizations given in the original 1992 paper on Karger's algorithm. Specifically, looking at section "3.1 Unweighted Graphs", I don't understand what ...
1
vote
0answers
15 views
How to prove the existence of the spectral expander with the given parameteres?
I need to prove the existence of the $(1944, 144, 0.5)$ spectral expander. I tried to construct it using tensor product of the following graphs:
$$
(1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (24, 16, 0....
0
votes
0answers
68 views
Check if graph is regular given adjacency matrix
I have the following problem:
Write a function
whose input is an adjacency matrix A of a graph G. The function returns true
if G is a regular graph and false otherwise.
I understand that a graph is ...
0
votes
0answers
12 views
How to Plot Logistic Regression using Seaborn? [closed]
I am trying to plot logistic regression model but seaborn regplot does not worked. What should I do?
1
vote
0answers
23 views
Creating Map of Unknown Space without being able to see obstacles
I'm trying to create a program where I have a user walking around a random space that contains obstacles, but I can't see where the obstacles are. The point is that as a user walks around, based on ...
1
vote
2answers
82 views
Find every edge for which every s,t-path in a DAG goes through that edge
Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-...
2
votes
1answer
53 views
A connected acyclic graph has $n-1$ edges
Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third:
$G$ is connected
$G$ is acyclic
$G$ has $n-1$ edges
Proving $1, 2 \implies 3$
A connected, ...
-3
votes
0answers
25 views
Algorithm to find a new spanning tree of G
Here is a problem that I recently encountered and I am having trouble with coming up with an algorithm,.
Suppose you are given an undirected weighted graph G and a minimum spanning tree T of G. Now an ...
0
votes
1answer
44 views
Kernelization algorithm for the following problem
We are given an undirected graph $ G $ and a positive parameter
$ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not ...
1
vote
1answer
16 views
Prune and search Algorithm for Generating a Bottleneck Spanning Tree
I'm trying to wrap my head around a prune-and-search algorithm for returning a bottleneck spanning tree, currently I'm selecting the median weight of all the edges, then divide the original graph G ...
1
vote
1answer
23 views
Number of paths starting from a given edge using adjacency matrix
I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that ...
-1
votes
1answer
30 views
UCS and Dijkstra's algorithm do both of them give the minimal cost between two vertices?
i tried both algorithm to find the shortest path with minimal cost between two vertices,but most of the time Dijkstra gives a different path and the cost is smaller than the cost for the path UCS ...
1
vote
1answer
27 views
Expected behavior of an algorithm to minimize rankings
Suppose $n$ students have preferences over $n$ different notebooks. Their preferences can be represented with a square matrix of size $n$ where each column is a different permutation of the vector $[1:...
5
votes
1answer
29 views
Minimal Path Covering
Consider a connected undirected graph $G = \langle V, E\rangle$, we say that a subset $C$ of vertices is a Path-Cover if the following holds. For every finite path $p$, it holds that $p$ traverses all ...
1
vote
1answer
31 views
Bounds on graph partitioning
I am trying to find some generic upper bounds on the "standard" graph partitioning problem. Say I have a graph with $|V|$ vertices and $|E|$ edges I want to partition it into two equal $N/...
0
votes
1answer
17 views
Decidability of directed strongly connected graphs
Consider the problem of determining if a directed graph is strongly connected.
How to phrase it as a language and prove that it's decidable.
My Thoughts :
To think of decidability given a graph I ...
0
votes
0answers
28 views
Show that Delaunay triangulation contains Gabriel graph on a set of euclidean points
Let $P \in \mathbb{R} \times \mathbb{R}$ be a set of points on a euclidean plane.
A Delaunay triangulation of $P$ is a graph $DT(P) = (P, E_{D})$ such that $\forall p, q, r \in P$, the edges $(p, q), (...
2
votes
0answers
20 views
Is this a variant of “Path Covering”?
According to 1, "a path cover of a directed graph G is a set of disjoint paths in G which together contain all the vertices of G".
In my research, I met a similar problem. There, you can add ...
0
votes
0answers
8 views
Good library for Graph Embedding Algorithms
I am working on a project related to virtual network embedding. As the problem is NP-hard, heuristic algorithms are most important for my use case. Looking for good libraries where I can find the ...
1
vote
1answer
55 views
How do Kruskal's and Prim's algorithms compare to each other?
I understand that both of them are used to find minimal spanning trees, and I've seen their implementations, but I don't understand how both of them compare to each other, and how they differ in ...
3
votes
1answer
125 views
FPT algorithm for 1-BDD
Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at
most $k$ vertices such that the degree of any vertex in $G[V \setminus D]$ is at most one.
Is ...
0
votes
1answer
30 views
Stack without duplicates
I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during ...
1
vote
2answers
34 views
Bipartite Graph to solve the wolf river crossing problem
I have just started studying about bipartite graphs and there is an example that bipartite graph can be use to solve the wolf, cabbage, and the sheep river crossing problem, as a kid i had fun solving ...
1
vote
2answers
53 views
Is the inverse of MST cut property true? Why?
If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?
1
vote
1answer
24 views
Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases
I am trying to design a parallel scheduling algorithm based on a constraint graph $G=(V,E)$ in which each node represents a task and each edge $e=(v_1, v_2)$ signifies, that tasks $v_1$ and $v_2$ can ...
1
vote
1answer
34 views
looking for counterexample for my algorithm for maximum independent set in Bipartite Graph
We wish to find the maximum independent set in a bipartite graph. My intuition led me to the following algorithm. (Assume that the bipartite graph is connected and has at least 3 vertices, if not run ...
2
votes
2answers
75 views
Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \{0, \ldots, n - 1\}$ and $E=\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\}$, with edge weights $w_e : E \to \mathbb{N}$ and vertex weights $...
1
vote
0answers
27 views
Separating a Graph into 2 sets with crossing edges only
I'm trying to think of an algorithm that checks the existence of partition $(V_1,V_2)$ in undirected $G$ where all the edges are crossing edges between $V_1$ and $V_2$. For example, if $e=(a,b)$ then $...
1
vote
1answer
50 views
Variant of assignment problem
This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to ...
4
votes
1answer
154 views
Changing a matrix to become an ancestry matrix
An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some ...
1
vote
0answers
17 views
Understanding Suurballe's algorithm
I have been looking at the Suurballe node-disjoint algorithm, which is illustrated here:
http://www.macfreek.nl/memory/Disjoint_Path_Finding
What I am a bit unsure about here is "Step 4". So ...
0
votes
1answer
15 views
Finding max flow in a undirected graph
According to this we can do so by replacing every edge in the undirected graph with two edges backwards and forwards with the same capacity. But I'm having a hard time seeing how this prevents ...
2
votes
2answers
93 views
Proving NP-hardness of Hamiltonian Cycle problem variant
I need to prove that determining whether a graph has a relaxed-Hamiltonian cycle (definition given ahead) is NP-hard.
A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex ...
6
votes
1answer
153 views
Shared Elements Algorithm
I have a problem that I am working on an algorithm for:
I have $k$ sets of distinct positive integers (each set is distinct, not necessarily across sets)
$S=\{A_1,A_2,A_3,...,A_k\}$ where $\forall A_i\...
1
vote
0answers
10 views
How are randomized restarts in local search 4 times likely to give bad local minima?
I am reading section 9.3.3 Dealing with local optima in Algorithms by Dasgupta et al. and the authors mention that in randomized restarts, it is four times likely to end up with a bad solution. They, ...
2
votes
1answer
19 views
Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?)
I was playing around with graph theory and I noticed that a directed integer graph with unique vertices $V$ and edges $E$ such that each vertex only points to vertices with a higher value can be used ...
1
vote
1answer
229 views
Solving two party problem
There are two parties A and B going on.
Some people are going to party A, some are going to party B.
We are given instructions of the form
different 1 3, meaning ...
5
votes
1answer
44 views
Maximum-weight set of cliques of size 3 with no common vertices in undirected graph
I'm looking for an algorithm/insight into a problem that's an extension of the Maximum Weight Matching problem. The maximum weight matching problem looks for the max-weight set of edges that contain 0 ...
2
votes
2answers
51 views
algorithm for connectivity by path of given length
Given an unweighted, undirected graph $G=(V,E)$ without loops or multiedges, and vertices $v,w$, one can use breadth-first search to check if $v$, $w$ are connected, and in particular the algorithm ...
0
votes
0answers
15 views
A more rigorous proof on a Bellman-Ford's corollary
The following corollary can be found at page 653 of "Introduction to algorithms (3rd edition)"
Corollary 24.3
Let $G = (V, E)$ be a weighted, directed graph with source vertex $s$
and a ...
1
vote
2answers
35 views
Problem to understand a Bellman Ford algorithm exercise
I am trying to understand the following exercise from Introduction to algorithm (3rd edtion).
Exercise 24.1-3 (page 654)
Given a weighted, directed graph $G=(V, E)$ with no negative-weight cycles, ...
2
votes
0answers
70 views
Number of planar graphs with linear edges, given a fixed embedding
Suppose we are given a set of $n$ points on the plane. How many different planar graphs can we form on those $n$ vertices, assuming that each edge must form a straight line between the two vertices ...
2
votes
1answer
35 views
Fast algorithm for finding the size of each connected component in a graph of 2D points
I've been thinking about this for a while now. Given a graph $G$ of 2-dimensional points (we draw the edges based on a "threshold" distance), find $s_1, s_2, \dots, s_k$, the sizes of all ...
4
votes
1answer
46 views
Number of planar graphs, given an embedding
I want to find an upper bound on the number of planar graphs with $n$ vertices, assuming that we are given some embedding for those vertices beforehand. In particular, Im interested in either showing ...
2
votes
0answers
15 views
How to use butterfly network for data copy?
I know butterfly networks (and benes as well) allow routing a packet from any input to any output node. Congestion is $\sqrt{n}$ but with bene it can be $1$.
Now assume that in a butterfly network, ...
