Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

Filter by
Sorted by
Tagged with
0
votes
1answer
43 views

Boolean formula for graph 3COL

For a given undirected graph $G=(V,E)$ I'm trying to construct a boolean polynomially computable formula $\varphi$ with the following property: $\varphi$ is satisfiable $\iff$ vertices of $G$ can be ...
1
vote
0answers
28 views

Social Networking Disease Transmission

You are given an undirected graph (social network) in which each edge $e = (v, v')$ has an interval $I_e = [l_e, u_e]$ on it. The meaning is that you know that $v$ and $v'$ met at some point during ...
1
vote
1answer
32 views

Shortest path with forced intermediate nodes

I have a directed graph with roughly 2000 nodes, and roughly 4000 edges. I have created an application so the people that use it can easily see the path drawn on a map, if they e.g. want to find the ...
3
votes
1answer
35 views

Using the chromatic number to compute an optimal coloring

Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to ...
5
votes
1answer
144 views

Is classical algorithms a dead research field?

I'm starting my masters in CS soon, and I have to decide on a general research topic. In my undergraduate studies, I've enjoyed courses regarding data structures and algorithms the most. I'm also an ...
1
vote
1answer
21 views

Lower bound for worst case running time for k-clique problem

A naive algorithm for determining whether a graph with $|V|$ vertices has a clique of size $k$ is to list all $k$-subsets of $V$, and check each one to see whether it forms a clique. Why is the ...
1
vote
1answer
54 views

Removing and adding edges from spanning tree

Let $T_1$ and $T_2$ be two spanning trees. If $a$ is an edge in $T_1$ that is not in $T_2$, and $b$ is an edge in $T_2$ that is no in $T_1$. I want to prove that $T_1 - \{ a\} + \{ b\}$ is a spanning ...
0
votes
0answers
114 views

Approximating the number of triangles using $\ell_0$ sampling

How do you solve the following question, from this assignment? Question 2. Consider a stream that consists of the $m$ (distinct) edges of a graph on $n$ nodes. Let $T$ be the number of triangles in ...
0
votes
0answers
33 views

Traversal algorithm for an optimal item collecting route in the game "Eternal Return: Black Survival"

I am currently trying to implement a algorithm for the game "Eternal Return: Black Survival" as a kind of exercise in Rust. Since the game may not be familiar to many, here is a quick ...
0
votes
0answers
25 views

Algorithm for bipartite graph matching decision problem

Suppose I have a list of sets $$ L=\{A_1,A_2,\ldots ,A_n\} $$ And want and algorithm that solves the following decision problem Is it possible to select one element from each set such that no two ...
0
votes
1answer
108 views

Shortest walk with alternating colors in a directed graph

Let $G$ be a directed graph such that every edge is colored (red, yellow or green). I want to compute the shortest walk (possibly with repeated vertices) with the restriction that the colors are ...
0
votes
1answer
107 views

Time-varying edge cost Minimum Spaning Tree

I am having a hard time wrapping my head around the time-varying edge cost of this question : Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
1
vote
1answer
38 views

Squaring the weights of an undirected graph and minimum spanning trees

This is from question 3(a) from http://www.cs.cmu.edu/afs/cs/academic/class/15210-s14/www/exams/exam2-practice-sol.pdf, which is: consider an undirected graph $G$ with unique positive weights. Suppose ...
1
vote
1answer
50 views

Similarity measures for (geometric) triangulations

In a project I am working on, we are looking at multiple different (optimal with respect to some cost measure) triangulations of a fixed pointset $S$. I would like to cluster similar triangulations. ...
1
vote
1answer
36 views

Optimal set of shortest paths from one node to all others in a network graph

Let's say I have a country with a set of cities, which I represent on the network graph below as a set of nodes. Furthermore, the weighed edge between pairs of nodes, represent the distance by road ...
2
votes
1answer
290 views

What is the difference between Euler and Eulerian graph?

A Graph is Eulerian iff $\exists$ an Eulerian Cycle or all the vertices of Graph have even degree. What is an Euler graph? Wiki has a definition for the Eulerian graph but not for the Euler graph.
2
votes
1answer
31 views

Do graphs with a bounded number of incident edges have a polynomial-time subgraph-isomorphism algorithm?

It is well known that the subgraph isomorphism problem is NP-complete. And so a polynomial-time algorithm for solving it would mean P = NP. Thus I'm interested in whether a bounded version of the ...
4
votes
0answers
57 views

Finding the smallest distance between a point and a set of points

I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this ...
1
vote
1answer
30 views

Meaning of source here

In graph theory, a source of a directed graph $D = (V(D), E(D))$ is a vertex of it whose in-degree is zero. The book CLRS makes these statements: Given a graph $G = (V, E)$ and a distinguished source ...
1
vote
0answers
16 views

If we have a graph with 2 nodes, the flow added to one edge will be added as extra capacity to be second edge

If we have the following subgraph of a graph where I will just show 2 nodes please, where the capacity is 7 and 2 respectively: Now, if we have received flow at node 1 of value 5, then we will have: ...
2
votes
1answer
67 views

Unusual MST variant on bipartite graph

On math.se, Sybren Zwetsloot has asked for help with an unusual optimal subtree problem. Here's my understanding of what he's asking: We have a weighted bipartite graph on two sets $N$ and $B$, call ...
1
vote
1answer
74 views

Why we need topological ordering for finding shortest paths

This question is just for discussing algorithms please and not for proposing algorithms. I saw very similar post to mine, but still the answer explains definitions online for topological ordering. ...
3
votes
1answer
46 views

Comparing different versions of Steiner Connected Component Subgraph problem

Problem 1 Let $G(V,E)$ be a directed graph. Let $T \subseteq V$ be a subset of vertices called terminals. Find a subgraph $H$ of $G$, such that $T \subseteq V(H)$, $H$ is a strongly connected ...
1
vote
1answer
89 views

Input size in graph algorithms

I know from the book by Neapolitan that for any algorithm input size is defined as the number of bits to encode the input. In graph algorithms, the input size is defined as $|V(G)| + |E(G)|$ for the ...
1
vote
0answers
36 views

Terminology for multiply visiting walks of directed graphs

In phrasing an information model for consumption-optimized RDF-like data (full context at 1 for the curious), I'm looking for any established term for X as used here: Given is a directed rooted graph....
1
vote
1answer
44 views

Detecting odd cycle using mod operator and breadth first search algorithm

If we want to detect and odd cycle if an undirected graph $G=<V,E>$. Suppose we run BFS algorithm from CLRS book as follows, Q: Now my question is suppose we have the following graphs: The ...
0
votes
0answers
23 views

Prove that $d[v_r] \le d[v_1] +1 ~and~ d[v_i] \le d[v_{i+1}], i=1,2, \cdots, r-1$ on queue $Q$ based on BFS algorithm

Given the following lemma first: Lemma 1: Let $G=<V,E>$ be a directed or undirected graph, and let $s \in V$ be an arbitrary vertex. Then, for any edge $(u,v) \in E$, $$\lambda(s,v) \le \lambda(...
1
vote
0answers
40 views

Describing the matrix product $BB^T$ of the incidence matrix of a directed graph $G=\left< V,E \right>$

I would like to discuss a solution with you below please. Describing the matrix product $BB^T$ of the incidence matrix of a directed graph $G=\left< V,E \right>$. Question: The incidence matrix ...
-1
votes
1answer
39 views

K-Path-Problem is in $P$ or $NPC$

Given an undirected graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of at least length $k$ exists between these two vertices? How can we solve this problem? I think ...
1
vote
0answers
62 views

Square of a directed graph $G=\left< V, E\right>$

I have this question from CLRS book please. Question: The square of a directed graph $G=\left< V, E\right>$ is the graph $G=\left< V, E^2\right>$ such that $(u,w) \in E^2 $ iff for some ...
2
votes
1answer
188 views

Topological sort with minimum maximal distance in array

I have a DAG that admits many possible topological sorts. I want to construct one that has the minimum maximum distance between a node and its neighbours in an array storing the nodes in sorted order. ...
2
votes
0answers
25 views

Efficient concurrent recalculation of a dynamic subset of nodes & their dependencies in a directed acyclic graph

I'm dealing with a directed acyclic graph representing calculation steps. Imagine it as something like a big excel spreadsheet, where each cell is a node in the graph. A node (cell) can have an ...
1
vote
1answer
26 views

Finding maximum clique given, for each edge, union of all cliques containing it

For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U_{e}$ of the edges of all cliques that contain $e$. Can we determine, in polynomial time, for a given edge $e_{0}\in E$, the size of ...
0
votes
1answer
57 views

A question about euclidean graph

I have an Euclidean graph $G$, but i should changes the weight of some edge of $G$ to $+\infty$. My problem is, after this change, $G$ remain Euclidean graph or not?
3
votes
2answers
88 views

Check if there is a subset of coordinates where each coordinate in the subset is diagonal to each other

Problem Statement Given a list of XY coordinates of length N ( e.g. [(1,2),(3,4)] ) check if there is a subset of coordinates of length S where each coordinate of ...
2
votes
1answer
56 views

Graph cycle basis and odd cycle transversal

I have a graph $G$ and an its fundamental cycle basis $B$. The question: is an odd cycle transversal of $B$ an odd cycle transversal of $G$?
0
votes
0answers
42 views

Longest path in a tree [duplicate]

Given an undirected weighted tree with $n$ vertices, how can I design an algorithm that is $O(n^2)$ and other that is $O(n)$ for finding the longest path between two nodes in the tree (without ...
0
votes
0answers
23 views

Number of possible boolean functions in a DAG of lookup tables?

A K-input lookup table (K-LUT) can represent any function with K boolean inputs and a single boolean output. The number of possible functions represented by this LUT is $2^{2^K}$ according to this ...
0
votes
0answers
13 views

Mechanism of improved version of Howard's algorithm

For Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems , could anyone advise how the following Howard's algorithm works to compute minimum mean cycle path ?
2
votes
1answer
55 views

Are recursion and a stack equivalent in terms of inplementing DFS?

It is well known that DFS can be implemented either with recursion or a stack, and that both approaches are equivalent, but how far can we take that statement? Consider the following LeetCode problem: ...
0
votes
1answer
21 views

A proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any MST

I cant proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any Minimum Spanning Tree. please help.
1
vote
1answer
69 views

Why is Independent Set "at least" and Vertex Cover "at most" k

The decision version of the Independent Set and Vertex Cover problems are phrased as: Given a graph G and a number k, does G contain an independent set of size at least k? Given a graph G and a ...
0
votes
1answer
26 views

Does the A* algorithm visit every node in an undirected graph when no path to the goal node exists?

When no path to the goalnode exists, does the A*-Algorithm a) visit and b) expand every node in an undirected graph? I have a monotone heuristic. Thanks
2
votes
2answers
349 views

Can you use Dijkstra's algorithm to find the maximum cost path?

Suppose you have a DAG and the edges are positively weighted, and you want to find the maximum cost path from any node with no in degree to any node with no out degree. Is it possible to negate all ...
0
votes
0answers
21 views

Important cuts bound

Important $(X,Y)-cut$ is defined as follows: S is an important $(X,Y)-cut$ if it is inclusion-wise minimal and there is no $(X,Y)-cut$ $S'$ with $|S′|<=|S|$ such that $R′⊃R$ where R,R' are the sets ...
3
votes
1answer
271 views

Maximum number of distinct nodes that can be visited on a single walk

Given a directed graph which may contain cycles, how can I find the maximum number of distinct nodes that can be visited on a single walk? I have done some research and the most similar-sounding ...
2
votes
1answer
47 views

important separators

Given a graph G and an important (X,Y)-separator S, why is it true that for every edge e in S the set of S\e is an important (X,Y)-separator in G\e Important (X,Y) cut is defined as follows: S is an ...
2
votes
1answer
31 views

Building a game tree from a board game

Currently I want to come up with a program able to solve a specific type of board game, where we have a car moving across a randomly generated board, can't move backwards, a gas gauge and a food gauge....
1
vote
0answers
41 views

What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?

For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
2
votes
1answer
163 views

Longest path between two nodes of a graph

I have a graph $G$ (NOT directed). $SP$ is one of the shortest paths between $a$ and $b$ ($a$ and $b$ are nodes of $G$). $e$ is the edge of $SP$ between the nodes $j$ and $k$ ($j$ is before $k$ if we ...

1 2 3
4
5
87