Questions tagged [graphs]

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

Filter by
Sorted by
Tagged with
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
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, ...

1
2 3 4 5
81