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
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
1answer
18 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
76 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 ...
1
vote
0answers
26 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
98 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
87 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, ...
0
votes
1answer
104 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
18 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
28 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
34 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 ...
3
votes
1answer
45 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
30 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
45 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 ...
2
votes
0answers
23 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 ...
1
vote
1answer
62 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 ...
4
votes
1answer
258 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
64 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
38 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
58 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
28 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
41 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
86 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
1answer
57 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 ...
3
votes
1answer
161 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
23 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
23 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
111 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
158 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
14 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
21 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
270 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
56 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 ...
2
votes
1answer
48 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
77 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
76 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
70 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 ...
3
votes
1answer
54 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
18 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, ...
0
votes
1answer
65 views

Algorithm for seeing if there exists a min s-t cut (A,B) in a flow network with node u in A and node v in B

We are given a flow network and two nodes $u$ and $v$. We want to create an algorithm that tells us whether or not there is a minimum s-t cut so that $u$ belongs to the same side of the cut as the ...
-1
votes
1answer
34 views

Reduction from $VC$ to $CD$

We define the vertex cover as the problem of finding for a graph $G$, a cover of size $k$. A cover is a set of vertices such that every vertex has an edge to this set. We define CD (cycles destructor),...
1
vote
0answers
23 views

Finding the two edge-disjoint paths, minimizing the sum of their lengths

Given an undirected graph and a start and end node, I am trying to find two edge-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, ...
1
vote
1answer
80 views

Finding the two node-disjoint paths, minimizing the sum of their lengths

Given an undirected graph and a start and end node, I am trying to find two node-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, ...
2
votes
1answer
24 views

Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?

Intro The job shop problem is a classic scheduling theory problem. Given $N$ jobs and $M$ machines, a typical goal of the JSP is to minimise the makespan (starting time of the last operation + its ...
0
votes
1answer
49 views

Exit quickly from a maze with a local view of the maze

How to efficiently exit from a maze where you know the initial position of the player (1,1), the exit (49,49)? You don't know the maze configuration but you know where your player is, and which ...
2
votes
1answer
40 views

Augmenting paths of two matchings

Given a graph $G(V, E)$ and two matchings $M \subset E$ and $M' \subseteq E$ with $|M'| > |M|$, how can one prove that $M\oplus M'$ ($\oplus$ denotes the symmetric difference) must contain at ...
0
votes
0answers
12 views

Could you explain this variant of the Preflow Push Algorithm to me?

I am having trouble to understand the FIFO-rule for the Preflow Push Algorithm. In class I learnt the the following version of the FIFO-rule: The active nodes are stored in a queue. Newly active ...
2
votes
2answers
143 views

Maximum weight perfect matching in general graphs

Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows $$ \...
1
vote
1answer
113 views

Single-source shortest path problem with diameter

Given that a graph G has only positive integer weights and its diameter D which is the greatest of the shortest paths among all pairs of vertices in G. For a single-source shortest path problem and ...

1 2 3
4
5
83