All Questions
Tagged with graph-theory algorithms
342 questions
186
votes
3
answers
96k
views
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...
- 343
47
votes
15
answers
29k
views
What are the applications of hypergraphs?
Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...
44
votes
4
answers
5k
views
Why is "P vs. NP" necessarily relevant?
I want to start out by giving two examples:
Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a planar $...
- 25.5k
33
votes
3
answers
3k
views
Can assignment solve stable marriage?
This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy.
Recall the set up of the stable marriage problem. We have $n$ men and $n$ ...
- 156k
30
votes
1
answer
3k
views
An edge partitioning problem on cubic graphs
Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
- 1,164
26
votes
2
answers
486
views
A small unavoidable collection of subgraphs
What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...
- 271
24
votes
4
answers
36k
views
Finding a cycle of fixed length
Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph?
All I know is that Alon, Yuster and Zwick use a technique called "color-coding",
which has a ...
- 1,250
24
votes
2
answers
2k
views
Can one measure the infeasibility of four color proofs?
Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
- 11.1k
19
votes
3
answers
2k
views
A generalization of the triangle counting problem for simple weighted graphs
One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-...
- 3,463
17
votes
9
answers
3k
views
Where on the internet I can find a database of graphs?
I am studying graph algorithms.
I need a database of graphs on which I can test my algorithms.
Where can I find a reliable database of graphs of all kinds?
Thanks!
16
votes
4
answers
2k
views
Checking if two graphs have the same universal cover
It's possible I just haven't thought hard enough about this, but I've been working at it off and on for a day or two and getting nowhere.
You can define a notion of "covering graph" in graph theory, ...
- 12.6k
15
votes
6
answers
9k
views
Good algorithm for finding the diameter of a (sparse) graph?
My question on Stack Overflow was recently tagged "math". Despite a bounty, it never received a satisfactory answer, so I thought I would ask it here:
I have a large, connected, sparse graph in ...
- 4,994
14
votes
1
answer
2k
views
Reasons for difficulty of Graph Isomorphism and why Johnson graphs are important?
In http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ it is mentioned:
'In discussing Johnson graphs, Babai said they were a source of “unspeakable ...
user76479
13
votes
4
answers
25k
views
What is a good algorithm to measure similarity between two dynamic graphs?
I am using graphs to represent structure present in a scene. The vertices represent the objects in the scene and the edges represent the relationship between two nodes(touching, overlapping, none). ...
- 281
12
votes
1
answer
603
views
Travelling salesman: can the furthest-neighbour algorithm beat the nearest-neighbour?
This is a problem that has bugged me for quite some time, and I have not been able to find any documentation about it online. It is well known that the NN algorithm can yield the worst possible route -...
user82330
12
votes
0
answers
530
views
Finding the diameter of an unknown tree: Is BFS optimal?
I'm interested on the following nice problem that is somewhat standard in CS, but I was surprised on the lack of references on the optimal algorithm to this problem.
Ana and Banana plays the ...
- 63
12
votes
0
answers
1k
views
Shortest path in Cayley graphs
The standard way to find the shortest path between 2 vertices, $v_1$ and $v_2$, of an undirected graph is BFS (breadth first search) which takes time $O(|E|)$ and space $O(|V|)$ (where $E$ is the set ...
- 121
12
votes
0
answers
349
views
Matroids with prescribed independent sets
Let $A$ be a finite set. Let $B$ be a family of subsets of $A$. We are interested in a matroid with a minimum rank such that every element of $B$ is independent. The answer is obvious - a uniform ...
- 1,791
11
votes
2
answers
3k
views
Algorithm for embedding a graph with metric constraints
Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide ...
- 7,857
10
votes
3
answers
1k
views
Is there a website or a survey collecting all NP-complete problems on graph theory?
I wonder whether there is a website or a survey collecting all known NP-complete or NP-hard problems on graph theory?
- 557
10
votes
4
answers
662
views
Deciding homomorphic images of De Bruijn graphs
The De Bruijn graph $B_n$ of
dimension $n$ (on the two-letter alphabet) is defined as the directed graph on
$2^n$ vertices and $2^{n+1}$ edges, where for every $w = w_0 \dots w_n \in
2^{n+1}$ we put ...
- 105
10
votes
1
answer
3k
views
Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?
This is inspired by a recent question.
Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the ...
- 48.9k
10
votes
3
answers
4k
views
Lagrange four-squares theorem: efficient algorithm with units modulo a prime?
I'm looking at algorithms to construct short paths in a particular Cayley graph defined in terms of quadratic residues. This has led me to consider a variant on Lagrange's four-squares theorem.
The ...
- 1,444
10
votes
1
answer
411
views
Network flows with capacities on pairs of edges
Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...
- 37.7k
10
votes
2
answers
595
views
Transfinite algorithms
The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
- 32.1k
10
votes
1
answer
910
views
Finding Two Rainbow Spanning Trees
Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.
Is the following problem NP-...
- 1,288
9
votes
3
answers
2k
views
Are regular graphs the hardest instance for graph isomorphism?
Regular graphs are the graphs in which the degree of each vertex is the same. The Weisfeiler-Lehman algorithm fails to distinguish between the given two non-isomorphic regular graphs.
Is there a ...
- 313
9
votes
4
answers
4k
views
Efficient way of determining isomorphism
Suppose you are given two isomorphic graphs $G$ and $H$. Is there an efficient way of defining an isomorphism $\phi:V(G)
\to V(H)$ if we already know they are isomorphic? Or is it just a guess and ...
- 151
9
votes
4
answers
2k
views
Algorithms on graphs of bounded degeneracy/arboricity
I know that many graph problems can be solved very quickly on graphs of bounded degeneracy or arboricity. (It doesn't matter which one is bounded, since they're at most a factor of 2 apart.)
From ...
- 2,416
9
votes
2
answers
12k
views
Reporting all faces in a planar graph
Hi, I was looking to traverse a planar graph and report all the faces in the graph (vertices in either clockwise or counterclockwise order). I have build a random planar graph generator that creates a ...
- 93
9
votes
3
answers
2k
views
Embedding planar graphs into the grid
I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...
- 903
9
votes
1
answer
453
views
On the use of Weisfeiler-Leman refinement in Babai's GI proof
This question is for those familiar with the methods behind Babai's recent proof that graph isomorphism can be decided in quasipolynomial time. I am a newcomer to the GI problem, so I apologize if my ...
- 997
9
votes
1
answer
356
views
Diameter of the modified bubble-sort graph
The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...
- 406
8
votes
1
answer
1k
views
When the Lovász theta-function saturates its upper bound
The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, $...
user3409
8
votes
3
answers
389
views
A simplified Art Gallery Problem in a matrix
Let's take a $m \times n$ matrix as an area with $m \times n$ blocks (likes a 2D-version of the world in Minecraft). We have to put some lamps in this matrix to illuminate the whole matrix. Here is ...
- 549
8
votes
2
answers
355
views
Isomorphism problem on the class of induced subgraphs of a hypercube
A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.
Now it feels to me that this class of graphs is "too ...
- 3,463
8
votes
1
answer
630
views
Change in the average geodesic distance of a graph when flipping a single edge
Is there a way to determine how the average geodesic distance between nodes of a graph will change just by flipping (1) a single edge without having to traverse the whole graph like in the Djikstra ...
- 923
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...
- 32.1k
7
votes
7
answers
3k
views
Efficient Hamiltonian cycle algorithms for graph classes
Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an ...
- 6,962
7
votes
4
answers
11k
views
Non-isomorphic graphs of given order.
It is well discussed in many graph theory texts that it is somewhat hard to distinguish non-isomorphic graphs with large order. But as to the construction of all the non-isomorphic graphs of any given ...
- 2,855
7
votes
2
answers
827
views
Graph minor check
Are there any good algebraic/algorithmic tools available to check if a given graph $H$ is a minor of $G$ from the adjacency matrix of $G$?
- 13.9k
7
votes
1
answer
339
views
Choosing two-colorable subgraph in a triangulation
Consider a planar graph $G$ which is a triangulation.
Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$?
It is known that it is not always ...
- 71
7
votes
1
answer
760
views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
- 123
7
votes
4
answers
449
views
How can I produce 'canonical' forms for rooted bipartite graphs?
The graphs I'm interested in are bipartite graphs with a specified root vertex. Because there's a root, all the vertices are 'graded' by their distance from the root. Because the graph is bipartite, ...
- 7,800
7
votes
1
answer
805
views
Counting Eulerian Orientation in a 4-regular undirected graph
We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...
7
votes
1
answer
469
views
Counting spanning trees of a planar graph
I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a ...
- 3,499
7
votes
1
answer
974
views
Algorithm to count the number of perfect matchings in non planar graph
I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing ...
- 763
7
votes
2
answers
533
views
Recovering a Weighted Graph from Shortest Path Distances
I am interested in the following problem (A) and its related formulation (B).
(A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), \...
- 168
7
votes
1
answer
222
views
Bound on queries to a tree with unusual probabilities
Consider a tree $\mathcal{T}(r) = (V,E)$ rooted at $r \in V$. Let $\kappa_r: V \longrightarrow [0,1]$ such that $\sum_{v \in V} \kappa_r(v)^2 = 1$. Furthermore, for any given vertex $v \neq r$, $\...
- 209
7
votes
0
answers
186
views
How quickly can we test if a graph is distance-regular?
A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ ...
- 37.7k