As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

1,514 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
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 ...
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,...$ ...
1 vote
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$...
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 ...
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?
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 ...
34 views

1 vote
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), ...
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 ...
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 ...
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) . For example 4x4 rook’s graph and the Shrikhande graph are non-isomorphic but the ...
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 ...
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 ...
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 ...
674 views

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 ...
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 ...
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, ...
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)$, ...
89 views

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$, ...
1 vote
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 ...
1 vote
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 ...
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)$. ...
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(...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
1 vote
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 ...
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 ...
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/...
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 ...