Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
4,086
questions
0
votes
0answers
4 views
Optimal online algorithm to guess the tree
I have a tree on $n$ vertices. Your goal is to find the adjacency list for it.
$n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the ...
0
votes
0answers
20 views
Edge-disjoint clique cover
Informally, we want to partition the edges of a graph into a few cliques. Given $G=(V, E)$, we want to find subsets $V_1,\dots, V_k\subset V$ such that $E = E[V_1]\dot\cup \dots \dot\cup E[V_k]$, ...
2
votes
0answers
9 views
SMA*+: Usefulness of culling heuristics
The paper on SMA*+ proposes a very interesting idea of having a culling heuristics different from the full path cost estimation (so called $f$-cost).
In the benchmark they use a culling heuristics ...
2
votes
0answers
6 views
SMA*+: f-cost estimation of re-generated nodes
I was reading the paper on SMA*+, which is very interesting as it implements most improvements I thought of when reading the paper on SMA*. But I have 3 questions that I think are related to my ...
0
votes
0answers
16 views
An algorithm to find differences between routing paths
I need to come up with an algorithm that finds differences in the sequence of each product's routing (or sequence of processes).
There are several processes aligned together and each process's been ...
1
vote
1answer
25 views
MST for a graph that does not have distinct weights
We all know that:
Every graph has an MST. The MST need not be unique, but it is unique if all the edge weights of the graph are distinct.
But if the weights of the edges in a connected graph are ...
-2
votes
0answers
13 views
Prove that in any tree T, any two longest paths cross each other [duplicate]
I can prove that if it is a connected graph. but how can I prove that in case of a tree?
Can someone give me explanation
0
votes
0answers
12 views
Partition in a tree shaped distributed network
We are given a synchronic undirected tree shaped network, with $n$ indexed nodes.
We know that there is at least one node with at least $\log_k n$ neighbors, $k>1000$, and $k$ is given.
We need to ...
-1
votes
0answers
22 views
3-hitting set iterative compression
I have a question which I tried to solve without success. I need to prove that if 3-Hitting Set can be solved in time $2^kn^{O(1)}$,then 4-Hitting Set can be solved in time $3^kn^{O(1)}$. There is a ...
1
vote
0answers
8 views
Subtype Check with Type DAG
Trying to understand how compiler/static-type-checker checks for subtyping, I run into 2 problems.
1. Reachability in DAG
Since both Python/C++ support multiple inheriatnce, the types can be ...
0
votes
0answers
40 views
Claw-free graph - linear kernel
I'm having a hard time solving the problem below:
In Claw-free problem, we are given a graph $G$ and $k$, and the objective is to decide whether there exists a subset $S \subseteq V (G)$ of size at ...
1
vote
0answers
17 views
Time to form a complete graph from n vertices given that only k vertices can be used at a time [closed]
I know this problem is related to the greedy algorithm and max edges incomplete graph but can't come up with a solution.
Problem
You are given two numbers n and k:
n >= k
n is the total # of ...
1
vote
0answers
29 views
Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?
I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me):
Vector-representation based models. One naive approach would be to represent G by flattening ...
0
votes
1answer
28 views
All longest paths in a tree cross each other at a single vertex
How to prove that in any tree, all longest paths cross one another in one vertex?
2
votes
0answers
21 views
Finishing at rest at a target in 2d space
I asked a similar question here, except I forgot to specify that the final velocity must be 0.
I have 2 points in 2D space, start = $s$ and target = $t$, and a starting velocity $v_0$.
At each time ...
3
votes
1answer
39 views
What is a guarenteed amount of colors, depending on the graph's arboricity
Let $G=(V,E)$ and denote $d=d(G)$ its maximal degree and $a=a(G)$ its arboricity. My question is: what is the smallest amount of colors $f(a)$, such that a $f(a)$-coloring is guarenteed to exist?
For ...
1
vote
1answer
17 views
Vector pathing via acceleration with velocity
I'm trying to solve a scenario where I need to find the smallest number of time steps to reach a location in 2d space, where I can manipulate the velocity with an acceleration at each time step where ...
1
vote
0answers
31 views
minimising Longest-Path in DAG
Assume we have weighted DAG (directed-acycle-graph), source s and target t.
Define the number of edges as $E$.
Given $0<\alpha<1$:
Choose $\alpha*E$ edges to cut their weight by half so that the ...
0
votes
1answer
35 views
an algorithm to find the shortest path between two vertices whose weight is divided by 3?
I am trying to think of an algorithm such that giving a graph $G(V,E)$, and a weight function $w\colon E \to \mathbb{N}_+$ (which means giving every edge in the graph a positive weight), and a source ...
3
votes
2answers
187 views
Is this graph Hamiltonian?
My case is a directed graph with $n$ nodes with $(n-1)^2+1$ edges. I have done the following till now.
We know that the maximum number of edges for a directed graph $K_n$ on $n$ nodes is $n(n-1)$ ...
0
votes
1answer
27 views
What Is the Currently-Known Simplest NOR-node Directed Cyclic Graph That Produces Pi?
Any directed graph (including a directed cyclic graph or DCG) has a complexity measure. We know that NOR is a universal logic gate, in the sense that a DCG whose nodes are n-input NOR gates can ...
0
votes
1answer
59 views
Prove Edited Algorithm of Bellman–Ford?
Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that.
I am stuck on this question for a week and hope to get some ...
0
votes
1answer
30 views
Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three [duplicate]
Question: Find an algorithm which returns the weight of a lightest path between all paths with a weight divided by three in a graph with natural weights of the edges.
My instructor has given me a hint ...
4
votes
1answer
46 views
How compiler optimizations create irreducible control flow graph?
I've been looking through research papers and the internet and found many claims that "compiler optimizations can cause irreducible control flow". However, I was not able to find a single ...
0
votes
0answers
39 views
identify nodes with paths of unique length from source
Let us consider a Directed Acyclic Graph $G(V,E)$ such that all edges have unit weight. Let $s$ be a source node, $s\in V$ and a set of destination nodes, $D\in V\backslash s$. My problem is to find a ...
-1
votes
0answers
14 views
Fastest type of centrality to compute
I should calculate the centrality (any type) of an unweighted graph.
The graph contains 1500000 nodes and Brandes' algorithm for Betweenness centrality is too slow.
I have also looked for ...
0
votes
0answers
29 views
Disconnect giant component in random graphs by edge deletion
From a complete random graph (ER graph) after deleting an edge randomly with some probability (p) in each step how many edge deletion occurs to make the graph disconnected or break the giant component?...
2
votes
1answer
42 views
How to find long trails in a multidigraph
I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I ...
3
votes
1answer
37 views
Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?
Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges.
In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+...
2
votes
0answers
31 views
Min Cost Max Flow algorithms for providing multiple solutions
Minimum Cost Maximum Flow algorithms have been known to provide an optimal flow routing for network flow problems in satisfactory runtime. Some of the algorithms for solving a min-cost max-flow ...
2
votes
0answers
53 views
A simple graph $G$ with even clique number, find a subset $A$ of the vertices, subgraph induced by $A,V-A$ have equal clique number
Given a simple graph $G=(V,E)$ s.t. $2\mid \omega(G)$,
Show that $\exists S\subseteq V\text{ s.t. } f_G(S)=f_G(V\setminus S)$
where $f_G(A)$ is the clique number of the sub-graph of $G$ induced by ...
-4
votes
0answers
36 views
Prove that a graph $G =(V, E)$ verifying $|E|>\frac{(|V|-1)(|V|-2)}{2}$ is connected
Prove that a graph $G =(V, E)$ verifying $|E|>\frac{(|V|-1)(|V|-2)}{2}$ is connected.
2
votes
0answers
32 views
Sub-graph Selection Algorithm Problem (Dynamic Programming or NP)
We have an algorithm problem in hand, can you please write your ideas about this, thank you!
There are N many nodes with K different colors. Some of the nodes have direct connection between each other ...
2
votes
1answer
19 views
1/2 Approximation to MAX-DICUT by rounding a linear program
Consider a graph $G=(V, A, w)$, where each arc $(u,v)\in A$ has a non negative weight $w_{u,v} \in \mathbb{R}^+$, partition $V$ into $U$ and $W$, $W=V-U$ such that $\sum_{(i,j)\in A} w_{i,j}z_{i,j}$ ...
-1
votes
0answers
22 views
Shortest representation of moves in a maze with blocks
The maze has HxW seats. Here are the possible steps you can take to go to the exit: N: move one cell Up,
S: move one cell Down,
W: move one cell Left,
E: move one cell Right, and M(i): go to the i-th ...
1
vote
1answer
20 views
Property testing of a complete multipartite graph
Propose and prove an $\epsilon$-test for the following property in the dense graph model: $G=(V,E)$ is a complete multipartite graph. That is, there exists a partition $V=V_1\cup\ldots\cup V_\ell$ ...
2
votes
2answers
56 views
Graph with $\Theta(2^n)$ minimum $(s, t)$-cuts
Is there any graph with $\Theta(2^n)$ minimum $(s, t)$-cuts?
Given an undirected graph $G = (V, E)$ and two distinct vertices $s$ and $t$ of $G$. A minimum $(s, t)$-cut is a $(S, T)$ cut of G which ...
3
votes
1answer
32 views
Applications of the splittance of a graph/ Turning graphs into splitgraphs
Let $G=(V,E)$ be a graph. For $C\subseteq V$ let $G[C]$ be the subgraph of $G$ induced by $C$.
A split Graph is defined as follow:
$G$ is a split graph if there exists a subset $C\subseteq V$ so that ...
1
vote
0answers
60 views
Can the Global Minimum Cut problem for a directed graph be solved using the minimum s-t-Cut
I am using the following definition of the Global Minimum Cut problem:
Given a graph $G = (V,E)$, a Cut of $G$ is a partition of $V$ into two subsets $(A,B)$.
A cut-edge of $C$ is an edge $(u,v) \in E$...
1
vote
1answer
28 views
Find minimal spanning tree of graph with edge values from 1 to 5 integers
How can I find the minimal spanning tree of graph with edge values from 1 to 5 integers (no need to be unique) most effectively? I know I can use Kruskal algorithm, but how can I modify the algorithm ...
0
votes
1answer
18 views
proving that if graph has perfect elimination order than the graph is perfect
I need help with this problem:
Let say that G has a perfect elimination order, than I have to prove that G is perfect.
Can someone help me with that?
I've tried to solve it with induction but I did ...
2
votes
2answers
95 views
DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?
Summary
I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.)
Normally, when attempting to add an edge to ...
1
vote
1answer
21 views
CVRP and removing edges from a graph
I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances.
I know that, in general, the complexity of ...
1
vote
1answer
25 views
What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic?
How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
In the post linked above, the user "plop" gives a great response where they claim, in particular, ...
2
votes
2answers
120 views
determine Eulerian or Hamiltonian
I am a beginner in graph theory and just found this question in a book after completing few topics and I was wondering how you approach this questions.
For eulerian, I can say that the graph has ...
2
votes
1answer
23 views
Representing abstract syntax tree as a graph
Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code?
The goal and application ...
2
votes
2answers
126 views
Edge exchange property of two Minimum Spanning Trees
Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T'
Then I want to prove ...
2
votes
2answers
73 views
How many vertices should be disconnected to make a graph acyclic?
Given an undirected graph with some cycles:
we can "disconnect" the red vertex by adding a separate vertex to each of the edges adjacent to it:
In this case, disconnecting a single vertex ...
0
votes
0answers
22 views
Is there a good analogy between spectral representation of a signal and graph theory?
I am working on some time series problems where the Fourier representation of the signal in the frequency domain is also important. I am wondering if there is any connection between time series ...
1
vote
2answers
61 views
Linear program for min-length pair of edge-disjoint paths problem
Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, ...
