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
29 views

Undirected unweighted sub-graph enumeration with threshold on node value

I have an undirected, unweighted graph $G=(V,E)$, and a function $f:V\to [0,1]$ where $[0,1]$ denotes the interval of real numbers from $0$ to $1$ inclusive. Given an input threshold $t\in [0,1]$, I ...
user avatar
2 votes
1 answer
513 views

Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?

The problem concerns finding shortest paths in graph from a single source to a single destination. So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
user avatar
1 vote
0 answers
28 views

Split Bipartite Graph

I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
user avatar
  • 143
0 votes
1 answer
73 views

Finding a Hamiltonian Cycle in a directed graph - graph problem

$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like ...
user avatar
  • 29
0 votes
1 answer
39 views

Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

Complete graph with n vertices. Walk from vertex u to vertex v of length k. I don't understand how the number of walks between the two of length k is $n^{k-1}$ I've tried this formula on an example ...
user avatar
0 votes
0 answers
10 views

Approach for flattening a 3-d cube given cuts

Take a cube. Cut seven of its edges. Consider a graph whose vertices are the centers of the faces of the cube. If two faces share a common edge, then the graph also has an edge connecting the two ...
user avatar
-1 votes
0 answers
17 views

How to make this directed graph DFS algorithm search an undirected graph DFS still using adjacency list? [closed]

for example if I pass 5 to the below program, it will print the nodes from the edges in green (see image below), but it won't print the ones in red ...
user avatar
0 votes
0 answers
31 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 ...
user avatar
4 votes
1 answer
74 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$...
user avatar
0 votes
0 answers
35 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$ ...
user avatar
  • 1
0 votes
0 answers
23 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, ...
user avatar
  • 175
-1 votes
0 answers
14 views

Obtaining min cost perfect matchings from arbitrary matchings [closed]

Let $G = (V, E)$ be an $n$-vertex complete bipartite graph with vertex bipartition $(L, R)$ with $|L| = |R|$, and an integral cost function $c : E → N$ on the edges. For a perfect matching $M ⊆ E$, ...
user avatar
2 votes
2 answers
311 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(...
user avatar
  • 129
-2 votes
0 answers
12 views

For given machine assume some strings and evaluate those string will be accepted or not then find out the generalized language

For given machine assume some strings and evaluate those string will be accepted or not then find out the generalized language.
user avatar
1 vote
0 answers
29 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.
user avatar
  • 11
1 vote
1 answer
29 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 ...
user avatar
0 votes
0 answers
18 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 ...
user avatar
0 votes
1 answer
81 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 ...
user avatar
  • 29
-1 votes
0 answers
8 views

lightest path from s to t that goes through vertex v even number of times [duplicate]

Given a directed simple graph G=(V,E) and two vertices s,t and a vertex v∈V−{s,t}, we would like to find the lightest path from s to t, that passes through v even number of times. for every edge there'...
user avatar
1 vote
1 answer
19 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 ...
user avatar
0 votes
1 answer
44 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 ...
user avatar
  • 137
0 votes
1 answer
33 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 ...
user avatar
3 votes
1 answer
41 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 ...
user avatar
0 votes
1 answer
103 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 ...
user avatar
  • 103
2 votes
0 answers
29 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 ...
user avatar
1 vote
1 answer
35 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 ...
user avatar
1 vote
0 answers
68 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 ...
user avatar
0 votes
0 answers
24 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 ...
user avatar
  • 1
2 votes
2 answers
30 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 ...
user avatar
  • 123
1 vote
2 answers
33 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?
user avatar
-3 votes
1 answer
36 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?
user avatar
2 votes
1 answer
37 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 ...
user avatar
  • 131
1 vote
1 answer
54 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 ...
user avatar
1 vote
1 answer
52 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 ...
user avatar
2 votes
1 answer
20 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 ...
user avatar
6 votes
1 answer
363 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 ...
user avatar
2 votes
1 answer
21 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!
user avatar
0 votes
0 answers
18 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?
user avatar
3 votes
1 answer
111 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 ...
user avatar
  • 245
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 ...
user avatar
  • 799
-3 votes
1 answer
27 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 ?
user avatar
  • 1
1 vote
1 answer
53 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 ...
user avatar
0 votes
0 answers
22 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.
user avatar
2 votes
1 answer
22 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 ...
user avatar
1 vote
1 answer
30 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
user avatar
2 votes
0 answers
25 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 ...
user avatar
0 votes
1 answer
52 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 ...
user avatar
1 vote
1 answer
23 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 ...
user avatar
0 votes
0 answers
27 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? ...
user avatar
  • 125
2 votes
0 answers
18 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 ...
user avatar

1
2 3 4 5
90