Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,514
questions
0
votes
1
answer
73
views
Finding the shortest cycle containing a vertex in a graph
Given a connected undirected graph with edges $E$ and verticies $V$ and a vertex $v \in V$, find the length of the shortest cycle containing $v$. The best I could do is $O(|E|*deg(v))$, by trying to ...
CommunityBot
- 1
0
votes
0
answers
18
views
Complexity of finding a path of specific cost
What's the complexity of the following problem?
Given a weighted directed graph G, where weights are natural numbers given in binary, and a number n (also in binary), is there a path in G of cost ...
- 113
1
vote
0
answers
34
views
+50
Given several $a_i$-$r$ paths in a planar graph how ``balanced" of a tree rooted at $r$ can I make?
Suppose I am given distinct nodes $a_1,a_2,.., a_l, r$ and several $a_i$-$r$ paths $P_i$ in a planar graph $G$.
I wish to construct a tree $T$ connecting $a_1,a_2,.., a_l, r$ that minimizes the ...
- 187
3
votes
1
answer
371
views
Can Lexicographic BFS be implemented in logspace?
Input: Given graph $G=(V,E)$ vertex labeling in some order
Output: Change the labeling of vertices's such that
labeling start $v_1$ as $u_1$, next label the neighbors of $v_1$ as $u_2,u_3,u_4,...$ ...
- 693
1
vote
0
answers
37
views
Asking boolean question on the nodes of a DAG to find the target node
We are given a DAG $G=(V, E)$ and an unknown target node $x \in V$ to find. There is a mechanism to probe a node, $y \in V$, to ask question of the form "Given the node $y$, is the target node $x$...
- 11
3
votes
0
answers
92
views
Cover all triangles of a graph with n subgraphs as small as possible
What is the smallest number $s(n,\Delta)$ such that for any undirected simple graph $G=(V,E)$ with $n$ vertices and $\Delta$ triangles, there exist $n$ subgraphs of $G$ covering all triangles where ...
- 63
27
votes
2
answers
2k
views
Why are Ramanujan graphs named after Ramanujan?
I recently taught expanders, and introduced the notion of Ramanujan graphs.
Michael Forbes asked why they are called this way, and I had to admit I don't know.
Anyone?
- 27.9k
4
votes
0
answers
55
views
(Where) in the polynomial hierarchy is determining the mixing time of an implicitly defined graph?
Consider an implicitly defined graph; for example, let $G$ be a finite group generated with $n$ generators as $\langle g_1,g_2,\ldots g_n\rangle$ and let $\Gamma$ be the Cayley graph of $G$ under ...
- 957
0
votes
0
answers
34
views
Let $C$ be collection of subsets of $[N]$. Given, $n\in [N]$, what's the terminology for $card\{s\subseteq [N]\mid n\not \in s,\, s \cup\{n\}\in C\}$?
Let $N \ge 1$ be an integer and let $\mathfrak S$ be a nonempty collection of subsets of $[N] := \{1,2,\ldots,N\}$. For any $n \in [N]$, define $\partial_n \mathfrak S := \{S\setminus\{n\} \mid S \in \...
- 291
-1
votes
1
answer
81
views
notation in graph theory [closed]
I was reading a paper, and I found a notation that I don't understand:
$\mathbb{E}[| \textbf{S} |] $, where $\textbf{S}$ is a set. Are there any differences with the notation $\mathbb{E}[formula]$ (I ...
- 13.9k
3
votes
2
answers
763
views
Decompose a complete graph into smaller cliques
The following exercise problem is from the book of D.B.West which i could solve:
If a complete graph can be decomposed into triangles then $n-1$ or $n-3$ is divisible by 6.
So my questions are the ...
CommunityBot
- 1
6
votes
0
answers
85
views
Cycle packing with degree condition
Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard?
Without the degree condition, the ...
- 123
0
votes
0
answers
134
views
What's the connection between branchwidth and treewidth
I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that $branchwidth(G) = Θ(treewidth(G))$.
However, my question pertains to a specific case involving ...
- 21
1
vote
1
answer
151
views
Graph partitioning to minimize sum of intra-partition edge weights
I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
CommunityBot
- 1
0
votes
0
answers
58
views
Ensuring the connectivity of an undirected graph through linear programming
I am trying to solve a linear programming problem that deals with finding an optimal subgraph as a function of several parameters. The case is I am trying to model a constraint that ensures that the ...
- 1
3
votes
1
answer
79
views
END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node
The END OF THE LINE problem is stated as
Given two circuits, P and N, a node, v, is balanced if $P(N(v)) = N(P(v)) = v$ or $P(N(v)) \neq N(P(v)) \neq v$. Given that $0^n$ is not balanced, find ...
- 13.9k
2
votes
1
answer
103
views
Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time
For a proof, I need the fact that we can efficiently embed an input planar graph into a representative of a specific family of high-treewidth graphs. Specifically, I need an embedding as a topological ...
- 98
3
votes
1
answer
173
views
Cover a graph with complete graphs
I want to find the smallest possible function $k(n,m)$ such that for any graph $G$ with $n$ vertices and $m$ edges, there exists $n$ vertex sets $S_1,S_2,...,S_n\subseteq V$ each with size $k(n,m)$ ...
- 63
0
votes
1
answer
42
views
Entries of the Inverse Laplacian
Let $L$ be a graph Laplacian. What is the meaning of the entries of its (pseudo)inverse $L^{-1}$? In other words, are there any interpretations which might help with understanding the entries of $L^{-...
- 141
1
vote
0
answers
36
views
Minimum vertex-separators under edge addition
I am trying to prove the following claim.
Let $T$ be a minimum $st$-separator in an undirected graph $G$, and let $x \in T$.
Let $S\neq T$ be a minimal $st$-separator (i.e., not necessarily minimum), ...
- 95
0
votes
1
answer
307
views
Fractional but not integer multi-commodity minimum cost flow
I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar ...
6
votes
1
answer
115
views
Complexity of induced Steiner Tree problem
Consider the following problem: we are given an undirected graph $G=(V,E)$ and three terminal vertices $t_1,t_2,t_3\in V$. We are asked whether there exists a set of vertices $S\subseteq V$ such that ...
- 1,537
6
votes
0
answers
135
views
Two graphs indistinguishable by 4-WL
There are pairs of non-isomorphic graphs that are indistinguishable by the k-WL (but distinguishable by (k+1)-WL) [1]. For example 4x4 rook’s graph and the Shrikhande graph are non-isomorphic but the ...
- 61
0
votes
1
answer
75
views
increasing minimum graph degree by adding edges
My problem: Given a graph $G=(V, E)$ and an integer $\ell$,add a minimum number of edges to $G$ so that in the resulting graph every vertex has degree at least $\ell$.
Is there a polynomial-time ...
- 9,555
0
votes
2
answers
351
views
Partition a graph into two clusters
Suppose given a complete weighted graph $G=(V,E)$, Is there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized?
Note that, heaviest edge ...
- 194
3
votes
1
answer
134
views
Treewidth for hypergraphs that specify connectedness requirements
This question is about an alternative definition of treewidth, called weak treewidth. It is defined on hypergraphs where hyperedges intuitively require that the connected subtrees of occurrences of ...
- 8,234
8
votes
3
answers
674
views
Is that edge orientation optimization problem NP-hard?
Is the following optimization problem NP-hard?
Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{u\in V} ~\left( d_{...
- 9,555
3
votes
1
answer
296
views
Is this node permutation optimization NP-Hard?
Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in ...
- 121
0
votes
0
answers
65
views
Maintaining a $K_{3,3}$-minor-free graph
Suppose we are given that an undirected, connected graph $G$ is $K_{3,3}$-minor-free.
Let $a,b\in V(G)$ be non-adjacent vertices.
Under what conditions is the graph that results by adding the edge $(a,...
- 95
0
votes
1
answer
55
views
Spectral sparsification of graphs with negative edge weights
I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question.
It is ...
- 111
3
votes
1
answer
119
views
Hardness of Maximum Independent Set in 3-Colorable Graphs
Let $G = (V,E)$ be an undirected graph such that there is a proper coloring of the vertices of $G$ in three colors.
Question: In such graphs, are there known results for the hardness of finding a ...
- 9,555
15
votes
1
answer
5k
views
What is the correct definition of $k$-tree?
As the title says, what is the correct definition of $k$-tree? There are several papers that talk about $k$-trees and partial $k$-trees as alternative definitions for graphs with bounded treewidth, ...
- 10.1k
3
votes
2
answers
220
views
What is this graph problem, and how hard is it?
My problem is quite simple to state, so it surely must have a name:
Given a graph $G=(V,E)$ with edge weights $w(e) \in \mathbb{Z}$, find a $V' \subseteq V$ that maximizes $\sum_{e \in E' } w(e)$, ...
- 50.6k
2
votes
1
answer
89
views
Number of vertices that a connected dominating set can reach in densely connected graphs
Consider a undirected densely connected (every vertex has $>\Theta(1)$ incident edges) graph $G$. Denote its vertices set as $\mathbf{V}$, number of vertices as $n$.
A connected dominating set $\...
- 9,555
3
votes
1
answer
157
views
Connected dominating set in bipartite graphs
Let $G$ a bipartite graph with two disjoint set of vertices $\mathbf{A}$ and $\mathbf{B}$.
Denote $n_a:=|\mathbf{A}|$, $n_b:=|\mathbf{B}|$. Suppose the following conditions hold:
$\Theta(1)<n_b<...
- 9,555
0
votes
1
answer
130
views
2xn grid graphs from ring graphs via local complementations
(Local complementation) A local complementation $\tau_v$ is a graph operation specified by a vertex $v$, taking a graph $G$ to $\tau_v(G)$ by replacing the induced subgraph on the neighborhood of $v$, ...
- 79
1
vote
0
answers
100
views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 11.2k
1
vote
0
answers
26
views
Can input-output matrices optimize bidirectional search?
Given a bidirectional search on a weigthed digraph, could a modified input-output matrix guess what nodes are more likely to belong to the shortest path and the search be done through these nodes ...
2
votes
1
answer
67
views
Spanning Tree that Preserves the Number of Branch Vertices
Suppose a undirected connected graph $G$, denote the number of vertices in $G$ as $n$, number of branch vertices (i.e., vertices with degree $\geq 3$) as $n_{\geq 3}$. Suppose $n_{\geq 3}>\log(n)$.
...
- 9,555
2
votes
0
answers
98
views
Small set expansion and expanders
Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets:
$$
h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ ,
$$
with
$$\phi(...
- 41
-1
votes
1
answer
66
views
Solution for a bipartite demand and supply graph
Given a set of distinct nodes ($A \cup B$) one set represents nodes with a supply ($supply(a), a \in A$) and the other represents nodes with a demand ($supply(b), b \in B$). In a bipartite graph I am ...
- 98
0
votes
0
answers
37
views
Is there a version of Klein-Plotkin-Rao (KPR) Theorem that yields components of small diameter rather than weak diameter?
The Klein-Plotkin-Rao (KPR) Theorem says we can find either a $K_{r,r}$ minor or an
edge-cut of size $O(|E|r/\delta)$ whose removal yields components of weak diameter $O(r^2 \delta)$, that is, any two ...
- 187
4
votes
1
answer
176
views
Finding a "typical" path
Consider an undirected graph with two distinguished nodes $u\neq v$. How hard is it to find an $u-v$ path, such that its length is as close to the average $u-v$ path length as possible?
Formally, for ...
- 9,555
40
votes
10
answers
13k
views
Data for testing graph algorithms
I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
- 355
7
votes
0
answers
134
views
Can one find good distance-2-separators in planar graphs?
It is known that planar graphs admit "good" separators, allowing to design PTASes for specific problems such as MINIMUM INDEPENDENT SET by recursive separation of the graph.
However, it ...
- 355
8
votes
6
answers
729
views
Have any generalizations of maximum weight matching been studied?
For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise.
accordingly, a ...
- 159
1
vote
0
answers
74
views
Packing k vertex trees
Consider a graph $G=(V,E)$ with $n$ vertices.
What do we know about packing of $k$ vertex trees, Both integral and fractional packing are interesting.
$k=2$, it is just the number of edges, hence ...
- 4,367
2
votes
1
answer
71
views
Dual of cut of embedded graph disconnects surface
Let $G$ be a graph that embedded on a surface of genus $g$, moreover the embedding is triangulated. Let $C$ be a collection of edges that forms a minimal edge cut for $G$. Let $C^*$ consist of the ...
- 617
12
votes
4
answers
4k
views
Incremental Maximum Flow in Dynamic graphs
I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/...
- 355
8
votes
1
answer
197
views
Monotone circuit representations of paths in a graph?
Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...
- 8,234