Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,534
questions
-2
votes
0
answers
45
views
d-regular graphs and edge expanders
Show that there is no (n, d, ρ)-edge expander for ρ > 0.5
Is this statement even true?
My attempt: Let n = 2, then we can have 2 vertices, A and B. Let d = 1, therefore there is an edge between A ...
-1
votes
0
answers
50
views
Average case complexity of decision version of NP-hard problem
I am a bit confused regarding the average case complexity of certain graph problems that are NP-hard like graph coloring, clique, dominating set and whose decision version is NP-complete. It is ...
0
votes
0
answers
16
views
Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?
Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
- 1
4
votes
0
answers
72
views
Name for a cyclic path in a graph that visits every vertex while minimizing the maximum number of times a given vertex is revisited?
Me and my colleague are interested in whether anyone has looked into a generalization of Hamiltonian cycles where vertices can be revisited, but we want to minimize the maximum number of times a given ...
- 429
-1
votes
1
answer
74
views
Representation of binary strings by graphs and hypergraphs
Let $\Sigma$ be the set $\{ 0, 1 \}$, then the set of all finite binary strings of length $n$ is written as $\Sigma^{\star}_{n}$.
Question: Which further ways of representing binary strings of length $...
- 1
1
vote
3
answers
91
views
Stable/Robust Traveling Salesman Approximation Methods
I was wondering if there are TSP approximations that are "stable". More specifically, consider the set $G = x_1, ..., x_n$ and the set $G^* = G \cup x_{n+1}$, where $x_i$ are points in $R^d$....
- 11
0
votes
1
answer
67
views
A variation of the longest path problem
What about finding a path of maximum length in a given graph which may contain cycles, with the constraint that a vertex (or an edge) can be visited at most X (say 2 or 3) times ?
EDIT: X would be ...
0
votes
2
answers
148
views
Bottom up TSP solution?
I'm not sure if this is something new or if I'm just not getting previous efforts. TSP can be thought of as a list of weighted links and nodes. If one takes the Nearest Neighbor (NN) of every node and ...
0
votes
0
answers
62
views
How to reduce a code down to its configuration
I have built a system where from atomic information of a UI code I could generate a framework specific code. Here is the concept https://github.com/imvetri/ui-editor. For example, the user of this ...
- 99
1
vote
0
answers
79
views
Tractability of computing generalized hypertreewidth on bounded arity hypergraphs
Generalized hypertreewidth is a generalization of treewidth to hypergraphs. Unlike treewidth, it is not tractable, for a fixed width $k \in \mathbb{N}$, given a hypergraph $H$, to determine if $H$ has ...
- 8,896
1
vote
0
answers
84
views
Generalization of the Hamiltonian path problem on Grid Graphs
Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$.
Define the following ...
- 31
0
votes
0
answers
83
views
5-color graph and minor
We have a 5-color graph G without 5-clique. The question is: is there a minor H of G that is a 5-clique? Here the minor definition.
With "5-color graph G" I mean $\chi (G)=5$.
1
vote
1
answer
103
views
Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths
I am working on a problem involving partitioning a directed acyclic graph into distinct multiple paths, each with a maximum length constraint. The goal is to minimize the number of paths (this should ...
- 11
1
vote
0
answers
33
views
Application LCL definition to vertex coloration
I'm reading the article "What can be computed locally?" by Naor & Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2)
An Locally ...
- 111
1
vote
1
answer
46
views
What is known about the complexity of Network Diversion?
In the Network Diversion problem, we are given an undirected graph $G$ on $n$ vertices, with specified nodes $s$ and $t$ and specified edge $e$, and a positive integer $k$, and are tasked with ...
- 576
4
votes
1
answer
85
views
Independent set queries with preprocessing
Suppose we have a sparse undirected graph $G = (V, E)$ with $|E| = O(|V|)$, and we want to process it and then answer queries of the following type: given a set $A$, is it an independent set in the ...
- 464
0
votes
1
answer
67
views
What's the exact complexity of a DFS if we revisit nodes?
By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
- 13
3
votes
1
answer
182
views
What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?
Here, by 3D-grid of sidelength $n$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,n\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$.
I known how to get the treewidth of $n*n$ grid is ...
- 315
1
vote
0
answers
45
views
Notion between connected and strongly connected graphs
Let $G$ be a directed graph without loops (or even better an oriented graph). Let us assume that $G$ is finite.
The graph $G$ is connected if its underlying graph $G^*$ is connected (i.e., for every ...
- 1,723
0
votes
0
answers
50
views
What is a combinatorial embedding?
I got a reviewer comment saying that I should consider using combinatorial embeddings rather than idk what I should call what I was doing topological embeddings?.
But I'm confused because as far as ...
- 186
3
votes
1
answer
99
views
Maximum cardinality matching on DAGs
A question on computational complexity and graph theory. The problem of finding maximum cardinality matchings of undirected graphs (the largest selection of edges such that each vertex is "...
4
votes
0
answers
120
views
Exploding number of homomorphisms
I'm trying to tackle the following problem: given two graphs $A$ and $B$, if there exists a graph $D$ such that $\hom(A, D) > \hom(B, D)$ (i.e. there is more homomorphisms from $A$ to $D$ than from ...
1
vote
0
answers
49
views
Bound on the treewidth of a graph from modular contraction
I cannot find a reference for this easy to prove result concerning the treewidth of a graph with respect to the treewidth of a modular contraction of it.
Let $G=(V,E)$ be a graph. A module $M \...
- 2,164
1
vote
0
answers
60
views
Graphs such that every rotation system admits an embedding on a surface of small genus
Let $G$ be a finite, simple, undirected graph.
What conditions on $G$ ensure that every rotation system of $G$ corresponds to a cellular embedding of $G$ on an oriented surface of small genus?
(e.g. ...
- 1,723
1
vote
0
answers
45
views
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 ...
- 186
1
vote
0
answers
38
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
109
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
0
votes
1
answer
136
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 ...
5
votes
0
answers
84
views
(Where) is determining the mixing time of an implicitly defined graph in the polynomial hierarchy?
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 ...
- 1,063
0
votes
0
answers
35
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
85
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 ...
- 1
6
votes
0
answers
93
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
154
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 ...
- 315
0
votes
0
answers
107
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
89
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 ...
- 135
2
votes
1
answer
115
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 ...
- 8,896
0
votes
1
answer
49
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
3
votes
1
answer
201
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
1
vote
0
answers
37
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
6
votes
1
answer
129
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 ...
- 3,416
6
votes
0
answers
180
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
77
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 ...
- 33
3
votes
1
answer
159
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,896
0
votes
1
answer
74
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 ...
- 1
3
votes
1
answer
152
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 ...
- 173
1
vote
0
answers
233
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 ...
- 11
3
votes
2
answers
221
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)$, ...
- 31
1
vote
0
answers
103
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.3k
3
votes
1
answer
163
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<...
- 177
2
votes
1
answer
94
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 $\...
- 177