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
2
votes
1answer
14 views

Network density vs connectivity

I was reading this paper where they mention about undirected networks: "The total connectivity of a network is defined as $C=\frac{E}{N(N-1)}$ where E is the number of edges and N the total ...
1
vote
1answer
63 views

communities problem with union and find

I am trying to solve the following problem: Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry ...
1
vote
2answers
38 views

What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
1
vote
1answer
371 views

Finding all unique paths from a source to a sink in a specially-formed DAG

Let $G$ be a directed, acyclic graph of order $n$, such that: $G$ has exactly one source vertex $s$; $G$ has exactly two sink vertices $t_1, t_2$; The out-degree of any non-sink vertex in $G$ is ...
-1
votes
0answers
29 views

Strongly connected components in a directed graph

Let $G$ be an arbitrary directed graph. Does $G$ always have the same strongly connected components on $G$ as on $G^*$? Here, $G^*$ is the inverted graph of $G$ (i.e., $(u,v)\in E \rightarrow (v,u) \...
0
votes
0answers
5 views

How to define the stability (or convergence) of a ordering of a list of node

I have a problem which requires ordering nodes in a graph based on some given statistics. However, the given statistics of each node may be very hard to compute. Thus, I will use some sampling ...
2
votes
1answer
54 views

HamiltonianCycles in Random Graphs

Lets say we consider the Erdős-Renyi undirected random graph $G(n,p)$ with $V(G) = \{1,2,\cdots,n\}$ and $\displaystyle{P((u,v)\in E(G)) = p} \quad \forall u,v \in V $. Is there anything we can say ...
2
votes
0answers
109 views

Minimum feedback vertex set [closed]

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
3
votes
1answer
110 views
+50

Merging nodes of a DAG

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them. After each merge operation, ...
0
votes
1answer
28 views

Decomposition of a directed graph into Hamiltonian paths

I was wondering if anyone knew of an algorithm that when given a directed graph will split it up into separate Hamiltonian paths. I don't really mind about nodes that can't be added to a path but as ...
3
votes
0answers
19 views

Bounded treewidth implies bounded clique-width

We have a graph G of treewidth $\operatorname{tw}(G)\leq k$, for some $k\in\mathbb{N}$. I've seen a claim that that implies that the clique-width of the same graph is at most $k \cdot 2^k$. This ...
1
vote
1answer
25 views

Algorithm for commonalities across related objects

I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application. The problem is give the data below (two columns) ...
-1
votes
0answers
13 views

How to prove of disprove the following Control Flow Graph theory

See the attached image for some background on Control Flow Graph In a single-entry, single-exit control flow graph (CFG), a node u post-lead v if every path from v to the exit includes 𝑢. Let q be ...
0
votes
0answers
13 views

Breadth-first traversal: difference between generation and expansion

The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names. Some ground-rules: we're traversing in ...
13
votes
1answer
328 views

Steps that guarantee exiting a maze

Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
0
votes
1answer
38 views

Verifying connectivity of a graph in O(n^2)

I trying to solve the following problem in O(n^2): We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph ...
0
votes
0answers
27 views

Modifying relaxation for the Bellman-Ford algorithm [closed]

I'm using the Bellman-Ford algorithm to find the best path in my graph. However, instead of choosing the path with the lower value, I want to choose the path with the highest value. And instead of ...
0
votes
0answers
13 views

How to transform an arbitrary graph into a fixed vector representation?

Actuality I work in computer vision, specifically on a problem known as "scene graph modeling." This problem aims to convert an image $I$ in a graph $G=(V,E)$ where the nodes $V$ represent the objects ...
1
vote
1answer
27 views

Student Course Allocation Problem with Many Constraints [closed]

Problem statement In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students. $i$-th section has: A student capacity: $cap_i$. Two lecture timings. (Formally, each ...
3
votes
1answer
85 views

Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
3
votes
2answers
244 views

Algorithms for procedural generated mazes

For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important). There are many Maze generation algorithms, but they only work on a ...
1
vote
1answer
27 views

Connected but not adjacent vertex

Is there any specific terms or adjectives in graph theory to name this two situations? Two vertices are non-adjacent (disjoint? I have seen that the term "disjoint" is rather used for paths with non-...
1
vote
1answer
128 views

Merge Leaf labeled trees [closed]

I have a set of leaf-labeled trees. I want to concatenate them into a single leaf labelled tree in such a way that the height of the resulting tree is smallest possible. Can somebody please help me to ...
0
votes
0answers
20 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
4
votes
2answers
6k views

Subgraph isomorphism reduction from the Clique problem

I was trying to understand the Wikipedia proof for NP-completeness of subgraph isomorphism by reduction from the clique problem. It's really just one sentence: Let $H$ be the complete graph $K_k$; ...
0
votes
2answers
64 views

Constructing a directed graph for O(1) queries

This question appeared in an undergrad data structures final. The details are sound. I need help to design a data structure for a directed graph with the following properties: Initialization should ...
0
votes
1answer
218 views

How to deal with cost variation in a dynamic graph when applying Dijkstra

What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I ...
1
vote
1answer
283 views

Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...
0
votes
1answer
165 views

A path modification problem in directed graphs

We start with a given finite directed graph. It could represent transitive relations such as: data transfer paths in social networks, transportation connections, etc. Let us use the notation A->B ...
1
vote
1answer
43 views

Does the Bellman-Ford algorithm find all the negative cycles?

The Bellman-Ford algorithm "can detect and report the negative cycle", but does it guarantee to find them or it may find some? The algorithm really focuses on the shortest paths, so I'm unclear if it ...
0
votes
0answers
16 views

Learning the weights in a directed acyclic graph

I have a directed acyclic graph $G=(V,E)$ where each vertex $v$ is associated with a weight $w_v$ such that $$w_v=1+\sum\limits_{(v,v')\in E} w_{v'}$$ and $w_v=1$ in case $v$ is a leaf. I am trying ...
3
votes
1answer
83 views

Embedding trees of diameter four is NP-hard

Suppose that $T$ is a tree of diameter four and $G$ is a graph. Deciding, whether $T$ can be injectively mapped to $G$ is NP-hard (there is a simple reduction from the problem of finding an ...
0
votes
1answer
370 views

Predecessor-subgraph property

In the proof of the predecessor subgraph property (page 14 of the following notes) http://www.cs.sfu.ca/CourseCentral/307/binay/shortestpath.pdf $d[v_i] \geq d[v_{i-1}]+w(v_{i-1},v_{i})$ is assumed ...
4
votes
1answer
566 views

What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
0
votes
0answers
23 views

Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
1
vote
1answer
193 views

Hamilton Circuit

The Dirac's theorem states that: "For a Graph G with N vertices, if the degree of each vertex is atleast N/2 then, the Graph has a Hamilton Circuit." Can the same be said if a graph has a Hamilton ...
1
vote
1answer
17 views

Hamiltonian non intersecting path in plane

$N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we ...
3
votes
1answer
69 views

Can a cycle be represented by L1 metric?

Let G be a graph that forms a cycle on $n$ vertices, with non-negative weights on the edges. Can you give each vertex v a vector $\mathbb{R}^m$ (for some $m\in \mathbb N^+$) such that the L1 distance ...
4
votes
2answers
444 views

Reconstruct directed graph from list of ancestors for each node

I have a problem that I encountered that boils down to the following: Considered this directed graph I found on Google: I have the following information available to me ...
2
votes
1answer
23 views

optimal flow for index multiple source and destination in directed graph

I am facing the similar problem to max flow in multiple source-destination directed graph (which has a familiar solution of connecting all the sources to one source and the same for the destination, ...
3
votes
1answer
2k views

Existence of bipartite perfect matching

Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is ...
1
vote
1answer
62 views

Generating project network graph

I had a problem of generating project network graph (like there and there) from list of activities and their dependencies. Informal description: Every activity is represented as edge of directed ...
2
votes
0answers
40 views

Similar-path shortest paths

Consider a directed graph with an out-degree of 2 for every vertex, i.e. all vertices have exactly two outgoing edges. This means, considering $n$ as the number of vertices, that the number of edges ...
2
votes
1answer
168 views

smaller size approximation to minimum vertex cover

Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ...
0
votes
1answer
49 views

set cover to edge cover

I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I ...
2
votes
1answer
42 views

Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges. Is the following statement true? If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected....
0
votes
0answers
11 views

Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
0
votes
1answer
13 views

efficiently calculate nearest common ancestor in a family tree (each person has two parents)

I'm well aware of ways to efficiently calculate the lowest common ancestor in a tree of nodes which converge to a single root (ie, each node has only one parent). Just iterate back to root for each ...
2
votes
1answer
43 views

How to merge a lot of trees into one single graph?

I have a few different trees, which resemble what the AST that compilers often deal with. For example: tree 1 ( (a, b), (c, d) ) Imagine that each tree split represents the function "add", then ...
3
votes
1answer
79 views

Finding minimum spanning tree of a special form graph

I'm trying to find an efficient algorithm that will find me the minimum spanning tree of an undirected, weighted graph of this particular form: My idea was a recursive solution: Suppose the algorithm ...