Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graphs]

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

2
votes
2answers
91 views

Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
1
vote
0answers
33 views

How to traverse on only a cycle in a graph?

I'm attempting ch23 in CLRS on MSTs, here's a question: Given a graph G and a minimum spanning tree T , suppose that we decrease the weight of one of the edges not in T . Give an algorithm for ...
1
vote
1answer
50 views

Karp hardness of directed monochromatic triangle problem

Monochromatic problem is a classic NP-complete problem. Does the complexity stay NP-complete if we use directed graph? DIRECTED MONOCHROMATIC TRIANGLE problem: Input: A digraph $G(V,A)$ ...
1
vote
1answer
98 views

MST Of An Almost Tree

A graph $G = (V,E)$ is called an almost tree if it is connected and has most $n + c$ edges where $n = |V|$ and $c$ is a small constant number. How would I go about designing an algorithm for a given ...
1
vote
2answers
43 views

Given a sorted dictionary of words, find order of precedence of letters

This question is found at: https://www.geeksforgeeks.org/given-sorted-dictionary-find-precedence-characters/ Given a sorted dictionary (array of words) of an alien language, find order of characters ...
1
vote
1answer
41 views

Is every graph with minimum degree $n/2$ connected?

Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected. Decide whether the above claim is true or false, and ...
0
votes
1answer
58 views

Visit all vertices of a graph

I need to find the fastest route passing in all vertices Each vertex is a class. I can choose the number of classes for semester. Some classes have prerequisites (A and B need to be done one semester ...
1
vote
1answer
143 views

Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number ...
1
vote
1answer
50 views

Minimum and maximum of sum of inverse degree of a graph

Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find ...
5
votes
1answer
160 views

Shortest path when allowed to reverse an edge

We're given an unweighted directed graph with vertices $V$ and edges $E$. We're trying to find the shortest path from $s$ to $t$ but we're allowed to travel along up to one edge in the ...
0
votes
1answer
24 views

Is any State Space Tree always Binary Tree?

A backtracking algorithm generates, explicitly or implicitly, a state-space tree. Introduction to the design & analysis of algorithms / Anany Levitin I wonder that whether the saying ...
1
vote
1answer
24 views

On uniform randomness of the weight of the remaining edges of a graph after deleting some of them

Suppose we have a graph $G(V,E,W)$, where $V$ and $E$ are the set of vertices and edges and $W$ is non-negative weight on the edges. Let $w(e)$ be the weight of edge $e$ and $N(e)$ be the neighboring ...
1
vote
1answer
30 views

Manber's graph-partitioning implementation

I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File. Generally speaking ...
0
votes
1answer
84 views

Time Complexity of the Kruskal Algorithm after sorting

In case I have sorted edges already, What is the best time complexity of Kruskal Algorithm?
1
vote
1answer
38 views

Karp hardness of a vector system allocation

Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies ...
1
vote
1answer
32 views

Karp hardness of a guarding set in digraph

Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following. A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set ...
1
vote
1answer
43 views

how to find a node that is known to everyone but doesn't know anyone?

Problem I am trying to solve is this: There are n nodes, and for every pair of node $X$ and $Y$, the relation "$X \space knows \space Y$" is either $T$ or $F$. It is possible that "$X \space knows \...
3
votes
2answers
101 views

Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?

I came across this problem in Tim Roughgarden's course on Coursera: In this problem you are given as input a graph $T=(V,E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A ...
0
votes
1answer
21 views

is the alignment between two sequences of points with 'no cross line' constraint an NP problem?

Given two sequences of points(i.e. ordered points), connect the points in seq_A with the points in seq_B according to some rules. A point could be connected to 0, 1, or many points in the other ...
2
votes
0answers
59 views

Edmond's Blossom algorithm (Maximum Matching) explanation

I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here. Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
2
votes
1answer
50 views

Digraph vertices: classification by counting outgoing walks

I'm reproducing a question I posted on MSE (yet with no answer both there and by myself). Given a (finite) directed graph $G = (V, E)$. For each vertex $v \in V$ and a natural number $n$, let $W_v(n)$...
2
votes
1answer
48 views

Optimal assignment of +-1 values to vertices in a graph

Let $(V, E)$ be a simple connected undirected graph, $f: V \to \{-1, +1\}$, and $g: E \to \{-1, +1\}$. The function $g$ is completely defined by $f$, while $f$ is something we get to choose. The only ...
1
vote
0answers
26 views

Calculate maximum sum of nodes property with limit on distance being traversed between nodes in a given graph

Given is an undirected weighted graph with N nodes, with each node having a property/Value. Aim is to find the bestpath which maximizes the sum of the nodes property which can be visited given a ...
1
vote
1answer
28 views

Proof of value discovery in complete graphs

I have an assignment There are n > 2 finite processors, two registers for each processor. Register s_i is not readable by the processor p_i but any other processor can read it. Register r_i is ...
2
votes
0answers
45 views

generalized translation operator on graph [closed]

David IShuman in " vertix-frequency analysis on graph" claims that,"we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting and When we apply ...
1
vote
0answers
69 views

How to handle negative edge weights in distance vector routing protocol with a digraph?

In a Distance Vector routing protocol each node implements a Bellman-Ford inspired algorithm that shares it's routing table (Distance Vector) with each of it's incoming links (upstream neighbors). ...
4
votes
0answers
28 views

Finding the “most modular” subset of graph vertices, i.e. that minimize disagreement inside and outside

Let $G = (V, E)$ be a graph. I want to find the subset of vertices of $G$ that minimizes a certain modularity cost. In our setting, the modularity cost of a subset $X$ is defined as the number of ...
4
votes
0answers
45 views

Inferring ranking functions in a general code graph with partial information

Let me define the notion of call graph: A program consists on a set of functions $f,g,h,\ldots$ where each function $n$ is as a mapping $n: D^l \to D^m$. Here $D$ is the datatype representing ...
4
votes
1answer
50 views

Vertex cover with covering radius 2

Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices? A vertex included in this vertex cover variant will cover every edge incident to it and every edge ...
-1
votes
2answers
41 views

Graph Coloring Problem

Can solutions to the graph coloring problem be used in the prison system to keep known enemies apart with the goal of reducing violence?
3
votes
1answer
34 views

How would I algorithmically “stretch” polygons on a plane by re-scaling the distances between interior points?

I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it. On a Euclidean plane, I have a polygon A, a set of points A* ...
2
votes
1answer
35 views

Algorithm and Formalism for Most Remote Vertices

In the graph below, N and M are most remote, and H is also an extremum. Has the problem of finding the most remote vertices been formalized? Could you point me to publications or references on the ...
1
vote
0answers
16 views

Given a simple graph G, what's the quickest known way to sample one of it's spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle. We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
0
votes
1answer
153 views

Babyface vs Heel

So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. ...
3
votes
1answer
69 views

Karp hardness of searching for a matching split

UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC ...
3
votes
1answer
36 views

Karp hardness of searching for a matching erosion

First, read the previous question: Karp hardness of searching for a matching cut As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
1
vote
3answers
69 views

Optimizing coin splitting - Is this algorithm as fast as I think?

In a recent exam, I've been asked to solve the following problem: The problem Two players play the following game: Given a sequence of coin values $v_1,\ldots,v_n (n \vert 2)$ the players ...
0
votes
1answer
71 views

DFS on reversed graph

I was watching a lecture on determining the strongly connected components of a graph using Kosaraju's algorithm and the lecturer claimed one can easily walk the edges in reverse fashion. While I see ...
4
votes
2answers
87 views

Karp hardness of searching for a matching cut

Follow-up question in the series: Karp hardness of searching for a matching erosion Karp hardness of searching for a matching split Maximum Matching Cut problem Input: An undirected graph $G(...
3
votes
1answer
91 views

Detect non existence of a cycle in a graph using Datalog : SMTLIB Format for Z3

I want to detect the non existence of a cycle in a graph using Datalog (which is a declarative logic programming language). The proposed solution was: ...
2
votes
1answer
348 views

Find shortest path that visits all nodes in a given set of nodes

Suppose I have a graph $G$ and a set of target nodes $S = \{A_1, ..., A_n\}$. I'm attempting to find the shortest path that visits each target node, in order, without visiting the same node twice. ...
3
votes
1answer
128 views

What is the best way to merge cycles to minimise total weight?

Suppose I have a vertex-disjoint set $S$ of simple cycles in a weighted undirected graph. So no vertex $v$ is contained in more than one cycle. A cycle $c$ is a closed path with no repeated vertices: $...
2
votes
1answer
141 views

Finding paths with minimum intersections

Given a graph and a set of origin-destination $\langle o_i,d_i\rangle$ pairs. The goal is computing a set of paths such that every pair has a path and number of common vertices between paths is ...
3
votes
2answers
96 views

Is there a solution for this maze problem in polynomial time?

Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now ...
0
votes
1answer
12 views

Generating graph with complex structure

I want to generate a bunch of graphs of about 100 nodes, where each node is a categorial variable. I want the graphs to satisfy complex properties, like, "if a node of type A is connected to a node ...
1
vote
2answers
146 views

Algorithm for generating all unlabeled trees with n nodes?

How can one generate all unlabeled trees with $\le n$ nodes? That is, generate and store the adjacency matrices of those graphs? (not just count them) Visualization of all unlabeled trees with $\le6$...
1
vote
1answer
30 views

How to test if my implementation of tree/graph data structures are correct?

I've recently implemented RB tree, B-Tree and vEB tree. I was wondering however if there's any rule of thumb for testing if my implementation are actually correct. Is there any reference that can ...
3
votes
1answer
272 views

Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?

Several questions (1, 2) have been asked about this topic already but I am trying to be more specific. In Tarjan's SCC algorithm, the calculation of lowlink when encountering a vertex which is ...
2
votes
1answer
321 views

What's the Big O runtime of a DFS word search through a matrix?

The problem is to try and find a word in a 2D matrix of characters: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent ...
2
votes
1answer
30 views

DFS timestamps, how important are they in pathfinding?

I am writing a work on pathfinding algorithms and DFS is a part of it. And the book Introduction to Algorithms and many another websites mention timestamps. And they say timestamps could be used for ...