All Questions
Tagged with graph-theory algorithms
37 questions
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
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 ...
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
5
votes
3
answers
411
views
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
- 1,444
1
vote
0
answers
185
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is ...
- 25.4k
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!
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
1
vote
0
answers
122
views
Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency matrices?
In short, I found an algorithm for GI and the only hard instances
I found so far are non-isomorphic strongly regular graphs with
large automorphism groups.
Q1 What are hard instances for the ...
- 25.4k
0
votes
1
answer
181
views
Bound on queries to a tree with unusual probabilties -- follow-up
This question follows up on Bound on queries to a tree with unusual probabilities, where @fedja was able to disprove my conjecture under only constraints (1-4) below. I restate the relevant facts here ...
- 209
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
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
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
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
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
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
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
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
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
6
votes
2
answers
4k
views
Find all faces in a graph from list of edges
I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...
- 63
6
votes
1
answer
392
views
Is it possible to decide in polynomial time if a poset is a subposet of another which is given ?
I am reading some theory on partial orders and I wonder something which perhaps has a simple answer : Given two partial orders $G_1,G_2$ (by their hasse diagrams), is it possible to know in polynomial-...
user22579
5
votes
2
answers
533
views
Diffie Hellman cryptography based on graph isomorphism?
We got a cryptographic algorithm and computer implementation
based on graph isomorphism.
An isomorphism between two graphs is a bijection between their vertices that pre
serves the edges.
For a graph $...
- 25.4k
4
votes
2
answers
207
views
Fast uniform generation of random graphs with given degree sequences - any implementation?
The paper below presents a linear-time algorithm for uniform generation of random graphs with given degree sequences [1].
This is very interesting in practice, but I found no implementation. However, ...
- 1,444
4
votes
1
answer
672
views
Algorithm to generate free unlabelled trees uniformly at random
I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of ...
3
votes
1
answer
215
views
Construction of planar embedding
I'm reading the following paper on universality considerations in VLSI circuits
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
In Theorem 2 On the second page it states there exists ...
- 903
3
votes
2
answers
404
views
A natural problem on "cartesian union" of set families (hypergraphs). Are there NP-complete problems related to the notion of cartesian product?
I'm curious whether the problem below is NP-complete.
I provide two simple definitions and one example at first.
Definition 1.
Let $\langle \cal S_i\rangle\substack{i\in I}$ and $\langle \cal S_j \...
- 41
3
votes
1
answer
315
views
Directed Hypercube Minimal Cuts
If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices $U,...
- 424
2
votes
1
answer
522
views
algorithmic almost equitable partitioning
Let $G$ be a graph -- possibly infinite, but I will be glad to learn a positive result even in the finite case. Then the trivial partition (i.e., one cell coinciding with the whole $G$) is clearly ...
- 3,388
2
votes
1
answer
2k
views
Detecting Negative Cycles in Undirected Graphs
I recently faced the problem of quickly detecting negative cycles in undirected, weighted graphs. Resorting to the Bellman-Ford Algorithm, as commonly suggested, turned out to be very inefficient and ...
- 13.2k
2
votes
0
answers
69
views
Are two degree sequences compatible, for random simple graph generation?
Consider a set $V$ of $n$ vertices, and three degree sequences $a_i$, $b_i$ and $c_i$ such that $c_i = a_i+b_i$, $i=1..n$.
Assume these degree sequences are graphical: there exist simple graphs (no ...
- 1,444
2
votes
1
answer
139
views
Description of Linear Time Algorithm for TSP in Halin Graphs
I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in
"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...
- 13.2k
2
votes
3
answers
16k
views
Cycle of length 4 in an undirected graph
Can anyone give me a hint for an algorithm to find a simple cycle of length 4 (4 edges and 4 vertices that is) in an undirected graph, given as an adjacency list? It needs to use $O(v^3)$ operations (...
- 23
1
vote
0
answers
149
views
Minimum delay path in time-dependent graph
Given a time-dependent graph, where each edge $e$ is on for certain time intervals and off otherwise. Traversing $e$ incurs a delay $d_e$ and is possible only when $e$ is on. Given a pair of vertices $...
- 367
1
vote
0
answers
54
views
Reductions to the MAX-3-DCC Problem
I am currently working on the Max-3-DCC problem that asks for the heaviest vertex-disjoint cycle cover of weighted directed graphs.
The problem has been reduced to 3-SAT in 1979 by L. Valiant in his ...
- 13.2k
1
vote
0
answers
176
views
Reduction graph isomorphism to maximum independent set in very dense graph
We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency ...
- 25.4k
1
vote
2
answers
223
views
Do all graphs with $n$ vertices and $m$ edges have a special property?
Given the positive integers $n$ and $m$, consider the set of graphs $\mathcal{G} = \{G=(V,E): |V|=n \land |E|=m\}$.
For which values of $n$ and $m$ does the following requirement hold:
$\forall G \in \...
- 1,000
1
vote
0
answers
74
views
Reduction maximum independent set to MIS in a very dense graph
We got a reduction maximum independent set to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G$ be graph of order $n$ and ...
- 25.4k
0
votes
2
answers
493
views
Relaxed path decomposition of a graph
Definition
Given a directed connected graph $G$ without multiple edges or self loops. We call a final path of $G$ a path ending with a vertex with no successor (the path can not be extended anymore) ...
- 223