Questions tagged [graphs]

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

4,342 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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.
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 ...
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 ...
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 ...
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: ...
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 ...
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. ...
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 ...
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 ...
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....
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 ...
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(...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
57 views

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?
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 ...
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$?
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 ...
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 ...
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 ?
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: ...
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.
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 ...
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
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 ...
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 ...
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 ...
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 ...
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....
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 ...