Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

Filter by
Sorted by
Tagged with
1
vote
2answers
12 views

How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?

In Dijkstra's original paper, he talks about two problems related to graphs. The second one is the problem of finding the shortest path between two nodes, which is what is most commonly meant by ...
0
votes
0answers
7 views

How to Draw the planar embedding of a graph?

I am very interested to know how to Draw the planar embedding of a graph,I found this question from a friend, I cannot, find the planar embedding because it is a petersen graph and is not planar but ...
1
vote
1answer
18 views

How many colors will be used in the following bipartite graph

I decided to create an algorithm to find the colors that is used to color a bipartite graph, the algorithm proceeds as follows: Rename the vertices in a some order $v_1,v_2,\ldots,v_n$. Do a single ...
2
votes
0answers
18 views

Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $Aut(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
1
vote
2answers
18 views

Finding the perfect matching

This the following graph where I want to find the perfect matching and a maximum matching I converted this to an bipartite graph, and found that the perfect matching exists and also found an maximum ...
-1
votes
0answers
12 views

Connected component- feature regions extraction

I'm trying to extract the connected component from a graph, in the following way: ...
0
votes
1answer
62 views

Counting strongly connected components in a directed graph in $NL$

Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$ I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
3
votes
0answers
23 views

Online cycle detection but not quite: the Featherstitch problem

Featherstitch (Frost et al., 2007) is an approach for representing data consistency requirements for disk storage. This question concerns a graph-theoretic problem (§4.1 in the paper) that its ...
3
votes
1answer
49 views

Minimum number of groups such that every element in graph is included?

Problem Description Note: I originally posted this question on Stack Overflow but was referred to this community instead. I have a graph containing selectors and elements. An element can have multiple ...
0
votes
1answer
35 views

Decide if the edges of a mixed graph can be directed in order to be an Eulerian Graph

I'm very stuck with this problem. Given $G = (V, E, A)$ a mixed graph where every edge in $E$ is directed and every edge in $A$ is undirected. Thinking as a max-flow problem, decide if it's possible ...
0
votes
0answers
16 views

Check if any path starting from a vertex in set A and reaching a vertex in set B is long at least k in $\Theta(G)$

I am trying to verify whether it exists a path from $a \in A$ to $b \in B$ whose length is $\ge k$ in $\Theta(G)$. This is what I have done: ...
1
vote
0answers
26 views

How good a center of a BFS tree is?

Consider a graph $G=(V,E)$, and a BFS tree $T$ starting from an arbitrary node $v\in V$. Now consider finding the center node $u_T$ of $T$, i.e., the vertex with the lowest eccentricity in $T$, which ...
0
votes
0answers
9 views

SMA*+: What if a removed node gets re-generated via another predecessor?

One last question came to me while reading the paper on SMA*+ about setting the $f$-cost of nodes being re-generated. Well, first, it looks like the part of the algorithm where we set the predecessor ...
1
vote
0answers
58 views

Find two paths in a Graph which are disjunct in

Assuming we have two trains that start in one source edge. I want to find an algorithm that finds two paths for these trains so that they won't meet in an edge at any given time. So we have the train ...
2
votes
1answer
27 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
26 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
17 views

SMA*+: Usefulness of culling heuristics

The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost). In the benchmark they use a culling heuristic equal ...
2
votes
0answers
15 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
18 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
34 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 ...
0
votes
0answers
17 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
34 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
11 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
60 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
1answer
74 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
30 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
23 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
44 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
35 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
193 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
61 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
49 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
42 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
31 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
43 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
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
59 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
33 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
2 3 4 5
82