Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,666
questions
6
votes
1
answer
2k
views
Tarjan's Strongly Connected Component algorithm
I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net):
On line 33 why is ...
- 111
11
votes
1
answer
1k
views
Average length of s-t (simple) paths in a directed graph
Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating ...
- 245
6
votes
1
answer
934
views
Independent set where two vertices need to have distance >= c
An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices.
I am interested in the generalization $c$-IS where two nodes in $V' \subseteq V(G)$ need to have ...
- 783
19
votes
3
answers
69k
views
Difference between cross edges and forward edges in a DFT
In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal).
There are some leftover edges connecting some of the other nodes. What is the difference ...
- 1,123
1
vote
0
answers
103
views
Node-weighted CSP in Prim's algorithm?
I'm looking for an algorithm which would find a minimal spanning tree given certain constraints (CSP) about importance of some nodes, e.g. consider a graph with next distance matrix:
$$
\left[ \begin{...
- 153
0
votes
1
answer
362
views
Is this graph a hamiltonian graph?
I (will, at the end) have a connected, undirected graph with N nodes and 2N-3 edges. You can consider the graph as it is built onto an existing initial graph , which has 3 nodes and 3 edges, ...
- 185
2
votes
1
answer
162
views
complexity of finding the hampath of length $k$ in a graph with $n$ vertexes where $k < n$
A simple question:
What would be the complexity of finding whether a hampath of length $k$ exists in a graph with $n$ vertexes where $k < n$?
Would this be in NP-complete or just NP?
- 21
10
votes
1
answer
250
views
Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?
A graph $G$ is chordal if it doesn't have induced cycles of length $4$ or more. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ ...
- 22.3k
9
votes
1
answer
5k
views
All paths of less than a given length in a directed graph between couple of nodes
Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, ...
- 93
6
votes
0
answers
93
views
Decomposition of graphs that uses centers
Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (...
- 2,269
3
votes
1
answer
2k
views
Existence of bipartite perfect matching
Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is ...
- 478
0
votes
1
answer
573
views
Non-trivial runs of Prim's algorithm
What does it mean when we say that a run of Prim's algorithm is trivial? What are example graphs for either case, that is with and without trivial runs?
- 65
5
votes
3
answers
946
views
Find a vertex that is equidistant to a set of vertices?
I need help with the following problem:
Input: An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$.
Question:
Find a vertex $v$ of $V$ such that the distance ...
- 553
2
votes
1
answer
3k
views
How to analyze the Steiner tree problem?
I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps.
1) Look up what the Steiner tree problem is.
2) Find a ...
- 553
4
votes
3
answers
5k
views
How many minimal spanning trees are there when all edge costs are distinct?
Suppose all costs on edges are distinct. How many minimal spanning trees are possible?
I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal'...
- 4,189
2
votes
1
answer
3k
views
DFS miniumum spanning tree
Just a quick question,
If i were to alter the general DFS algorithm to do this:
...
- 145
7
votes
1
answer
4k
views
Lowest common ancestor similar algorithm for a graph
I'm working on a type system and hit upon a problem that seems similar to lowest common ancestor. Given two types, I need to find the smallest sequence of conversions which will result in the same ...
- 1,538
4
votes
1
answer
432
views
Assignment problem with no cost
I have a problem that I was able to conceptualize as following:
Problem
We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of ...
- 41
6
votes
1
answer
237
views
Is induced subgraph isomorphism easy on an infinite subclass?
Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem
Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?
is ...
- 3,481
3
votes
1
answer
1k
views
Prove finding a near clique is NP-complete
An undirected graph is a near clique if adding an additional edge would make it a clique. Formally, a graph $G = (V,E)$ contains a near clique of size $k$ where $k$ is a positive integer in $G$ if ...
- 369
4
votes
0
answers
147
views
Decidability over finite graphs of small degree [closed]
Suppose $\sigma$ is a vocabulary of First Order logic consisting of one binary relation $E$ and let $\phi$ be a $\sigma$ sentence (FO formula with no free variables). Is it decidable whether there is ...
- 191
3
votes
1
answer
902
views
Height of a full binary tree
A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:
I ...
- 33
2
votes
0
answers
72
views
Complexity of computing the first bits of a minimal permuted adjacency matrix
Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix
$$A(G)=\left(\matrix{
A_{1,1} & A_{1,2} & \dots & A_{1,n}\\
A_{2,1} & A_{2,2} & \dots & A_{2,n}\\
&&...
- 2,269
0
votes
0
answers
68
views
The name of "finding the path of a graph that is a variant of hamiltonian path" [duplicate]
Suppose that there is some graph, with $n$ vertexes. We wish to find the hamiltonian path, but we make the graph being searched a little different. There is a person A that travels each (undirected) ...
- 101
6
votes
1
answer
4k
views
What is the maximum number of shortest paths between any pair of vertices in a chordal graph?
A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
- 22.3k
3
votes
1
answer
374
views
How do we know to what community a vertex belongs to in the Girvan-Newman algorithm?
So I've been doing some reading on community detection in graphs as I'm planning on working on my thesis for it. I've been reviewing papers regarding the same and came across the Girvan-Newman ...
- 314
3
votes
2
answers
2k
views
Acyclic Tournament Digraphs and Hamiltonian Paths
I am studying MIT OCW lecture notes but they do not have solutions for the following problem.
Directed Acyclic Tournaments
In a round-robin tournament, every two distinct players play against each ...
- 31
1
vote
1
answer
60
views
$st$-path with fewest leaving edges
Given an undirected unweighted multigraph $G=(V,E)$ and $s,t \in V$ find a simple $st$-path $P$ s.t. the number of edges leaving $P$ (i.e. the edges with exaclty one endpoint in $P$ ) is minimized.
...
- 783
5
votes
2
answers
24k
views
Number of cycles in a graph?
Can the number of cycles in a graph (undirected/directed) be exponential in the number of edges/vertices?
I'm looking for a polynomial algorithm for finding all cycles in a graph and was wondering if ...
- 277
19
votes
1
answer
461
views
Number of Hamiltonian cycles on a Sierpiński graph
I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
- 291
7
votes
1
answer
6k
views
How to find the maximum independent set of a directed graph?
I'm trying to solve this problem.
Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$...
- 255
0
votes
2
answers
4k
views
Longest path in undirected tree [duplicate]
Given an undirected tree (with no specific root), how to find the longest path, i.e. 2 vertices that are the farthest apart from each other? There are no lengths associated with the edges (each edge ...
- 109
4
votes
4
answers
2k
views
Find node that splits tree in half
Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the ...
user2102697
6
votes
2
answers
16k
views
What is the complexity of this matrix transposition?
I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically I ...
- 213
8
votes
1
answer
11k
views
How to find a local minimum of a complete binary tree?
How to find a local minimum of a complete binary tree?
Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a real number $x_v$. ...
- 269
31
votes
2
answers
41k
views
Is Dijkstra's algorithm just BFS with a priority queue?
According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.
- 755
1
vote
2
answers
120
views
Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete
I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete.
Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in ...
- 25
1
vote
1
answer
139
views
Prove that 2-Colourability is in L from Undir-Reachability is in L
Let Undir-Reachability be the following problem:
given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G?
I need to prove that the 2-Colourability is in ...
- 25
2
votes
0
answers
238
views
Travelling salesman problem with detours
I am interested if there exists a following version of the travelling salesman problem:
INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair ...
- 337
4
votes
1
answer
149
views
Bipartite graph question
Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v_{min}$ and $v_{max}$ (where $v_{min} \le v_{...
- 243
24
votes
4
answers
13k
views
The purpose of grey node in graph depth-first search
In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (...
- 333
9
votes
4
answers
3k
views
Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop
The Floyd-Warshall algorithm is defined as follows:
...
- 333
20
votes
2
answers
1k
views
Are link-cut trees ever used in practice, for max flow computation or other applications?
Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-...
- 301
1
vote
1
answer
451
views
Dfs algorithm and cycles question
Is it true or false that for running a dfs on an undirected graph G with a simple cycle than this cycle will have exactly one back edge?
Looks to me likes its true ,is it?
Nusha
1
vote
1
answer
150
views
Path on an edge-colored DAG using exactly $k$ colors
I have the following problem:
Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$,
does there exist a path from $s$ to $t$ using exactly $k$ ...
user547616
4
votes
1
answer
5k
views
What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?
Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$.
What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ with ...
- 1,615
5
votes
2
answers
3k
views
Uniform-cost Search Problem
Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem?
Definitions: Uniform-...
- 51
3
votes
1
answer
2k
views
Finding all cliques of a graph
Given a graph with $n \leq 50 $ vertices. Count all $k$-cliques of this graph, where $k = 1, \ldots , n$.
I need the most efficient algorithm.
- 39
-1
votes
3
answers
424
views
BFS in K shortest paths
Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes?
If so where can it be useful?
- 39
3
votes
0
answers
140
views
Maximal value of directed graph with constraints
What is an algorithm to calculate the maximum "score" possible in a directed graph, with the constraint that edges with the same value can only be traversed once? For example, in the graph ...
- 131