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
0 answers
36 views

Special case of single vehicle routing

I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
5 votes
2 answers
88 views

Name and complexity of this problem on bipartite graphs

Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes. I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}_u$...
0 votes
0 answers
118 views

Wrong Solution for `Spanning tree with chosen leaves` problem

Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find the lightest spanning tree in which the nodes of $U$ ...
  • 1
0 votes
0 answers
36 views

Using an undirected graph to represent an ordered pair?

Set theory depends on a set membership function $\epsilon$ which is a class of ordered pairs. Is it possible to construct the ordered pair from an undirected graph of unordered pairs? Alternatively, ...
  • 175
2 votes
2 answers
330 views

Graph Injective-Homomorphism Problem

Graph Homomorphism is a well-known NP-complete problem. Given graph $G$ and $H$, $G$ is said to be homomorphic to $H$ if there is a mapping $f: V(G) \mapsto V(H)$ such that $(u,v) \in E(G) \implies (f(...
  • 129
1 vote
0 answers
32 views

What LaTeX library do you use for adding graphs to your papers?

the expression "graphs" in the title refers to graphs as they are thought in computer science: Let G = (V(G), E(G)) be a graph. It is a tuple with a set of vertices and edges.
  • 11
1 vote
1 answer
45 views

Variation of Assignment Problem to maximize amount of agents working

I'm looking at a problem similar to an assignment problem. There are both agents and tasks. Each agent has a list of tasks they are able to do, and cannot do any task not within that list (note that ...
0 votes
0 answers
35 views

Looking for an algorithm for multi-path funnel analysis

Suppose we have a dataset with each instance: {uid, action, TS}. The funnel algorithm (e.x https://clickhouse.com/docs/en/sql-reference/aggregate-functions/parametric-functions/#windowfunnel) looks at ...
0 votes
1 answer
138 views

Is there an edge whose removal will extend the shortest path? - graph problem

Given an undirected and unweighted graph $G = (V, E)$ and two of its vertices $s$ and $t$. My task is to find an algorithm that checks if there exists an edge belonging to $E$ such that its removal ...
  • 71
1 vote
1 answer
20 views

Dual of a graph where the faces are unclear

To get the dual of a planar graph, each of the faces becomes a vertex. And then, two vertices in the dual graph are connected if they share a common face. My question is about planar graphs that have ...
0 votes
1 answer
238 views

Performant way to find all leaf nodes in a undirected graph

I am trying to find a better way to find all leaf nodes in my undirected waypoint graph. This is how I define a leaf node: A leaf node is a node that is never part of a cycle and so has to meet one of ...
  • 137
0 votes
1 answer
83 views

Tweaking Floyd-Warshall Algorithm to detect cycles

Cheers, I am trying to solve the problem of minimum length cycle in a graph, and I came across a solution that suggested that I should tweak the Floyd-Warshall algorithm to solve that. It stated that ...
3 votes
1 answer
54 views

Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$? A ...
0 votes
1 answer
153 views

why use bellman-ford instead of Dijstra in RIP routing?

The RIP routing protocol was published in 1988 and uses Bellman-Ford algorithm to calculate shortest path. Also more recent version of RIP (RIPv2 and RIPng) use the same algorithm. The Djikstra ...
  • 103
2 votes
0 answers
38 views

How would I prove that the algorithm to find the k-cores graph, produces a maximum size of vertices?

I came across this simple algorithm for finding a k-core of a graph, but every paper I read gives this notion of being maximal without proof, and I'm wondering how I might prove it. So a k-core of a ...
1 vote
1 answer
39 views

Why Least Cost Airline Fare problem shows optimal substructure when given a certain intermediate stops?

In the Optimal Substructure Wikipedia, As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to ...
1 vote
0 answers
110 views

With fixed k>=4, can 3-coloring in a graph of vertex degree at most k be solved in polynomial time?

I couldn't think of a poly-time solution. Moreover, I think that there is a pretty simple Karp-reduction from 3-coloring problem, which is NP-complete. let's say that graph G is in 3-colloring. I'll ...
0 votes
0 answers
27 views

Why is necessary for finding strongly connected components to have a reverse graph?

I'm trying to learn SSC, but it is illogical to me why I need a reverse graph for it. I drew a graph and it's reverse: So, we have a road from vertice 6 to vertice 5, and we have a road from vertice ...
  • 1
2 votes
2 answers
43 views

Matching problem in bipartite network with more than one edge per vertex

I'm interested to know if there is an algorithm to find possible solutions for the matching problem, in a bipartite network where each vertex have maximum number of connections greater than one. For ...
  • 123
1 vote
2 answers
72 views

Repeated vertices in cycles (graph theory)

In graph theory, can a cycle contain repeated nodes/vertices not including the first and last ones? If so, can you please give an example?
-3 votes
1 answer
51 views

Can there be an infinite number of different cycles in a directed graph?

If not, then what is the maximum number of cycles in any graph?
2 votes
1 answer
180 views

Differences between DFS based cycle detection algorithms

I have seen several variants of DFS algorithms used to check existence of cycles in graphs. They all have the same structure : do a DFS in the graph. There is a cycle in the graph if and only if there ...
  • 131
1 vote
1 answer
63 views

an O(m+n) algorithm to decide whether a graph can be reduced to a single edge with two vertices

Given B and C operations. B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices. C-operation: When one edge ...
1 vote
1 answer
53 views

How to prove non-planar graph can't reduce to single line

Define two operations: B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices. C-operation: When one edge connects ...
2 votes
1 answer
21 views

Consequence of having a randomised algorithm for graph colouring, which shows Yes and No with probability $1$ and $p(n) \sim_{n} 1$

Suppose we have a randomized algorithm that takes a graph G and color k as inputs and provides yes if the graph is k-colorable and no with probability $p(n)$ if it's not k-colorable, where $n$ is the ...
6 votes
1 answer
410 views

What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?

I'm looking at Dijkstra's algorithm for single source shortest paths in a graph $G$ from a vertex $s$ from Introduction to Algorithms by Cormen et al. The $w$ parameter is the weight function such ...
2 votes
1 answer
29 views

First-order model checking is not fixed parameter tractable on general graphs

I read that the problem of first-order model checking is believed to be not fixed parameter tractable on general graphs. Why is this the case? Would be happy about some reference Thanks in advance!
0 votes
0 answers
22 views

Efficient way to partition graph maximum and minimum number of cycles

Is there an efficient way to find the minimum and maximum number of edge disjoint cycles an undirected graph can be partitioned into, given that every vertex has an even degree?
3 votes
1 answer
158 views

Is there an efficient algorithm to find GCD of all cycles' lengths in directed multigraph?

I have weighted connected directed graph with cycles which can have multiple edges and loops (edge from vertex back to itself). Weight of each edge is its length (always positive integer). There ...
  • 265
0 votes
0 answers
17 views

Common name for "insert unique root" operation?

I had a graph operation come up in a code review, and was wondering if there is a common name for it. Given a DAG with multiple roots, you can trivially create a graph with a single root by adding one ...
  • 819
-4 votes
1 answer
29 views

Which algorithm would be most suitable for finding a minimum subgraph that connects all vertices in a graph and has the smallest weight?

Which algorithm would be most suitable Kruskal, Prims or Steiner tree algorithm ?
  • 1
1 vote
1 answer
62 views

Find max of all trees resulting from single edge removal in generic tree in linear time

Given a generic tree with $n$ weighted nodes, there are $n-1$ edges. Removing any of the edges will partition the tree into two distinct trees, hence we can construct $2(n-1)$ possible trees in this ...
0 votes
0 answers
24 views

How to proof This for Maximum Independent Set Problem?

Show that the problem of finding a Maximum Independent Set doesn't have approximation with factor $\Omega(\frac{1}{n^{1-\epsilon}})$ unless P = NP.
2 votes
1 answer
81 views

a generalized job assignment problem

The following problem is from a past algorithms course exam and I'm using it to test my knowledge. There are m machines and n jobs. Each machine can doing a subset of jobs. Each machine i has a ...
1 vote
1 answer
33 views

First-order model checking on general graphs is intractable

I read that the first-order model checking problem is intractable on general graphs. How is this shown? Would be happy about some reference! Thanks in advance
2 votes
0 answers
31 views

The Roskind-Tarjan Algorithm

I am going through the paper https://pubsonline.informs.org/doi/abs/10.1287/moor.10.4.701 which is A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees and the authors are James Roskind and ...
0 votes
1 answer
347 views

Implementation of Kruskal's algorithm using priority queues

Is there a way to implement Kruskal's algorithm for finding the MST of an undirected graph using priority queues? The standard implementation uses the disjoint set data structure but I was curious if ...
1 vote
1 answer
39 views

Rank of a graph in matroid theory

I was going through the concept of graphs as matroids and I came upon the rank of a graph. Wikipedia lists it as $n - c$, $n = |V|$, $c =$ # of connected components. I do understand rank and nullity ...
0 votes
0 answers
28 views

Can a complex arrangement of diodes do computation?

If I have a bunch of diodes arranged in some complex, directed graph, can I get it to do computation? I mean will it add voltages and, for example, as I insert voltage sources in-between the diodes? ...
  • 123
2 votes
0 answers
39 views

Edmond's theorem for k-disjoint arborescences in digraphs

Recently while studying arborescences in graph theory, I came across Edmond's theorem for $k$ edge-disjoint arborescences in digraphs if a finite digraph is $k$ edge-connected from a vertex r for ...
1 vote
1 answer
44 views

Why DFS transversal without the duplicates is a valid cycle?

So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-...
2 votes
0 answers
40 views

Is there an algorithm for determining the identity of an individual, based on their genome and the genome of distant relatives?

I've been thinking recently about the Golden State Killer case, in which a crime was solved by comparing a killer's DNA sample with known samples in a public genetic database. The cousin of the killer ...
0 votes
0 answers
39 views

How to reposition an undirected weighted graph on a 2D grid where strongly connected nodes stay together?

I have an undirected fully-connected weighted graph of $n$ nodes, where $n=m\times m$. I want to visualize this graph on an $m$ x $m$ 2D grid. My goal is to place nodes connected with edges of higher ...
2 votes
1 answer
44 views

Make maze connected by removing internal walls

Recently I've stumbled upon a strange graph problem. Here is a brief description. Given $n\times m$ matrix with $2n + 1$ rows such that each row contains $2m + 1$ characters "+", "-&...
2 votes
1 answer
27 views

Using algorithm for weighted graphs when the weights are vectors

Consider the following example problem. Given a graph with edge weights, find a matching that maximizes the number of matched vertices, and subject to this, maximizes the total weight. This problem ...
2 votes
2 answers
95 views

How are a graph and a binary tree represented as data structures in CLRS' Introduction to Algorithms?

In CLRS' Introduction to Algorithms: (1) In 22.1 Representations of graphs The adjacency-list representation of a graph G = (V, E) consists of an array Adj of |V| lists, one for each vertex in V. For ...
  • 1
2 votes
0 answers
62 views

Find minimum difference between pairs of numbers chosen from array of ranges

I recently thought of this problem, and I think it's very interesting. We are given an array of $N$ numbers, but we don't know the numbers themselves, only a possible integer range for each number. ...
0 votes
0 answers
70 views

Is this greedy algorithm optimal?

Let $T=(V,E)$ be a tree and let $k$ be a natural number. The problem is to find the largest set of vertices $S \subseteq V$ such that $(*)$ every path in $T$ consists of at most $k$ vertices from $S$. ...
  • 13
0 votes
0 answers
28 views

Updating Shortest Path Weight from One Destination to Another

Let $G=(V,E)$ be a directed graph with possibly negative edge weights. Given a destination $t$. Suppose that we have already known $d_v$, the shortest path weight from $v$ to $t$. If I'd like to ...
  • 121
1 vote
2 answers
33 views

Generating combinations that fulfill certain restrictions for graphs

I am working with graphs, let's say I have 4 nodes, named A, B, C, D, each node has to be connected a certain number of times to the other nodes. A: 3, B: 3, C: 2, D: 2 This means that A and B are ...

1 2 3
4
5
92