Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
403
questions with no upvoted or accepted answers
32
votes
0
answers
6k
views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
(...
- 6,655
27
votes
0
answers
1k
views
Counting Isomorphism Types of Graphs
Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
- 5,983
23
votes
0
answers
2k
views
$\Delta = 57, d=2$ Moore Graph
I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.
You may recall that Hoffman and ...
16
votes
0
answers
269
views
When does adding edges decrease the cover time of a graph?
When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph $...
- 4,258
16
votes
0
answers
2k
views
What is the fastest deterministic algorithm for incremental DAG reachability?
As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if ...
- 509
15
votes
0
answers
634
views
Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?
Last year I spent some time trying to prove or disprove the following:
Conjecture. Consider a graph $G$ and define a 2-DNF formula $\phi$ that contains a term $x \land y$ iff $x\mathrel{-\!-}y$ is ...
- 4,776
15
votes
0
answers
226
views
Mixing properties of random walks on graphs
I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs.
One of the main ideas of the paper is that random walks on graphs can be used to find sets with small ...
- 259
14
votes
0
answers
183
views
NP-Hardness of 4-cycle packing problem in complete bipartite digraph?
A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
- 451
14
votes
0
answers
363
views
Finding all-pairs anti-distance
Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.
Let $G=(V,E)$ ...
- 211
14
votes
0
answers
415
views
Question on Products of Graphs
Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices.
Let the chromatic number ($\chi(G)$) and the independence ...
- 2,208
14
votes
0
answers
494
views
Bi-partite expander graphs
My question relates to bi-partite expander graphs, defined as bi-partite graphs on $n$ left vertices, $m$ right vertices, constant left-degree $k$, such that
For any linear-sized subset $S$ of the ...
- 1,224
14
votes
0
answers
601
views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
- 1,953
14
votes
1
answer
342
views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(...
- 838
13
votes
0
answers
176
views
Minimal rare subgraphs
I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other ...
- 161
12
votes
0
answers
222
views
Hitting edges in graphs at random and let them die with honor
Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit ...
- 650
12
votes
0
answers
170
views
Generating a random graph with constraints on spectrum
Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple ...
- 10.1k
12
votes
0
answers
360
views
Directed Sparsest Cut on Planar Graphs?
The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the ...
- 426
11
votes
0
answers
344
views
A dynamic data structure to list triangles
Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations?
Insert an edge into the graph
Delete an edge from the graph
Given a query ...
user15587
11
votes
0
answers
146
views
Is RAMSEY COLORING in $NC$?
Say that a function $f$ is a RAMSEY COLORING if on unary input $n$, it returns a complete graph on $n$ vertices with its edges colored red and blue without a monochromatic clique of size $10\log n$.
...
- 13.9k
11
votes
0
answers
304
views
A bijection between ordered lambda terms and rooted planar maps?
Consider the following recurrence in two parameters $n$ and $k$:
\begin{aligned}
NF(0,k) &= 0 \\
NF(n,k) &= Neu(n,k) + NF(n-1,k+1) \\
Neu(n,k) &= [n=1 \wedge k=1] + \sum_{l=1}^{n-1}\sum_{...
- 4,381
11
votes
0
answers
463
views
Cheeger's inequality for directed graphs?
Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to ...
- 775
10
votes
0
answers
258
views
Random unbalanced bipartite graphs are good small set expanders
My question is about small set expansion properties of random unbalanced bipartite graphs.
Fix a positive $\delta<1/2$, and a positive integers $n,m,d$. Let us call a bipartite graph $\mathcal{G}$...
- 101
10
votes
0
answers
169
views
Number of graphs with prescribed spectrum
I have a question relevant to the number of graphs with prescribed spectral ratio.
Let $A$ be the adjacency matrix of a graph on $n$ vertices. Let $\lambda_i$ be its $i$-th largest (signed) eigenvalue....
- 1,346
9
votes
0
answers
104
views
Forbidden Subgraph Characterization for Graphs with few Maximal Cliques
Consider the following property of undirected graphs. A graph has the $s$-vertex overlap property if every vertex is contained in at most $s$ maximal cliques. I am interested in forbidden induced ...
- 1,700
9
votes
0
answers
136
views
Graphs with minimal-size induced subgraphs
I consider undirected graphs $G = (V, E)$ for which I write $\text{n}(G) := |V|$ the number of vertices and $\text{m}(G) := |E|$ the number of edges. For $d \in \mathbb{N}$, I say that $G$ is $d$-...
- 8,234
9
votes
0
answers
357
views
Triangle arrangement problem
Suppose you are given an undirected graph $G$, with each vertex representing an equilateral triangle with sides of unit length. Does there exist an arrangement of these triangles in two dimensions (...
- 91
9
votes
0
answers
269
views
Advances towards proving the Held-Karp conjecture for TSP
I've only began my research into the Held-Karp conjecture and I was wondering about recent progress in proving the conjecture.
The Held-Karp relaxation is conjectured to have an integrality gap of $\...
- 313
9
votes
0
answers
557
views
Is it possible to solve perfect matching in linear time
As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft.
Is it possible to solve perfect matching problem in linear time for given $...
- 99
9
votes
0
answers
367
views
Maximum local edge connectivity
For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a ...
- 4,367
9
votes
0
answers
507
views
Statistical relationship between diameter and density in strongly connected random digraphs
I would like to know if there is any known relation between diameter and density in (connected) simple digraphs. Asymptotic results for n→∞, statistical, conditioned results that would restrict the ...
- 91
9
votes
0
answers
179
views
Pseudorandom object yielding shrinkage in $\ell_p$ norm?
Extractors have the following property: For a random variable $X$ of min-entropy $k$ and a seed $Y$, denote the output of an $(k,\epsilon)$-extractor by $\mathrm{Ext}(X,Y)$. Then $\|\mathrm{Ext}(X,Y)-...
- 651
9
votes
0
answers
289
views
Spectral gap for random bipartite regular graphs
For a graph $G$, let its Laplacian be $\Delta =I − D^{−1/2}AD^{−1/2}$, where
$A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm ...
- 2,796
8
votes
0
answers
114
views
improved analysis of spectral gap of zigzag product?
I am reading the paper introducing zigzag products of expander graphs (https://arxiv.org/abs/math/0406038). The paper mentions the following observation in the introduction:
Moreover, the variational ...
- 81
8
votes
0
answers
178
views
Sublinear time path existence
Consider a graph $G = (V,E)$ with $N$ edges. Consider two vertices $u_1, v_1 \in V$. We wish to find whether there exists a path of length $4$ between these two vertices or not. This is easy to do in $...
- 1,177
8
votes
0
answers
330
views
Embedding a graph with specified edge lengths in d-dimensional space
Given any undirected edge-weighted graph (with weights > 0) and some dimension d, is there a way to assign positions in $\mathbb{R}^d$ to those vertices such that all of the edges between them have ...
- 1,082
8
votes
0
answers
361
views
Upper Bound on Number of $n \times n$ Boolean matrices of Boolean rank at most $k$
An $n \times n$ Boolean matrix $B$ has Boolean rank $k$ if there exist matrices $L \in \{0,1\}^{n \times k}$ and $R \in \{0,1\}^{k \times n}$, s.t. $B = L \circ R$. Here $\circ$ denotes the Boolean ...
- 143
8
votes
0
answers
111
views
Approximating a max-cut's intersection with other cuts
For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set $S$ and its complement. A max cut is one with at least as many edges as any ...
- 181
8
votes
0
answers
523
views
Reducing the maximum degree in a graph
Given a weighted undirected graph $G = (V, E)$ with maximum degree $\mu$ and with positive edge weights, is it possible to construct another graph $H = (V \cup V', E')$ with maximum degree $\mu' = o(\...
- 838
8
votes
0
answers
139
views
Extension of Cheeger's inequality with distinguished vertices
The standard Cheeger's inequality for graph $G$ states that
$\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$
where $\lambda$ is the second smallest eigenvalue of the normalized ...
- 81
8
votes
0
answers
342
views
Combinatorial method for computing the largest eigenvector of the adjacency matrix of a graph
Given a connected and non-bipartite graph $G=(V,E)$ with vertex set $V=\{1,\cdots, n\}$, let $A$ denote its adjacency matrix and let $deg(i)$ denote the degree of vertex $i$. Let $D$ be a diagonal ...
8
votes
0
answers
176
views
Is the dominating set problem constant-factor-approximable in undirected path graphs?
I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class.
A graph is an undirected path graph if it is the vertex-intersection graph of a family of ...
- 2,113
8
votes
0
answers
185
views
Lossless, constant-degree expanders that expand large sets
It is known how to construct "lossless" unbalanced bipartite expanders with the following properties: the bipartite graph has $n$ left vertices, $m$ right vertices, left-degree $D$, and for all left-...
- 3,718
8
votes
0
answers
113
views
Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D
This is a repost from a question on Computational Science. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes:
Is there an algorithm that enumerates the ...
- 191
8
votes
0
answers
2k
views
Fast Hamiltonian Cycle finding Algorithm
We are struggling to understand a fast algorithm for finding Hamiltonian cycle (for random graphs) due to Prof. Alan Frieze* and see whether that algorithm could be implemented efficiently. If there ...
msk
7
votes
0
answers
119
views
Decomposing graph homomorphisms
A homomorphism $h: G\to H$ from a graph $G$ to a graph $H$ is a function from the vertices of $G$ to those of $H$ which preserves edges, that is, if $(x,y)$ is an edge of $G$ then $(h(x),h(y))$ is an ...
- 161
7
votes
0
answers
174
views
Algebraic methods for testing planarity
Mac Lane's planarity criterion states that a graph is planar if and only if it has a cycle basis such that each edge is contained in at most two cycles, we call such a basis a 2-basis. A 2-basis of a ...
- 215
7
votes
0
answers
99
views
Complexity of computing the simplicial width of a graph
Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:
For every edge $\{v_1,v_2\} \in E$, there ...
- 1,217
7
votes
0
answers
209
views
Expansion of the union of two expander graphs
Suppose that $G$ and $H$ are both expander graphs on the same node set $V$ with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$.
Let $G\cup H$ be the graph on $V$ with the smallest set of ...
- 1,251
7
votes
0
answers
935
views
Biconnected components of a directed graph?
I am looking for an algorithm for computing the biconnected components of a strongly connected directed graph.
- 481
7
votes
0
answers
452
views
An algorithm to compute the number of paths of length at most k
So I had to answer the following question:
Given a graph $G = (V, E)$, and two vertices $v_i, v_j$, compute the number of walks between $v_i$ and $v_j$ of length at most $k$. $G$ is not too large, ...
- 445