Questions tagged [graph-theory]
Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.
1,481
questions
0
votes
0
answers
55
views
What's the difference between 'theoretical' and 'applied' runtime complexity?
I recently followed a course on complexity theory and according to the professor I got one particular question wrong. The question involved the runtime complexity of checking the correctness of a ...
- 1
0
votes
0
answers
30
views
The "branch-depth" parameter and its use in FPT algorithms
Let $P=(v_1,\dots,v_q)$ be an induced path in the undirected graph $G(V,E)$. In [1], the authors define the branch depth of $P$ to be $b(P)=|N_G[\{v_1,\dots,v_{q-1}\}]|-1$. Further, in [1] it is shown ...
- 65
1
vote
0
answers
51
views
The tree augmentation problem, but with hyperlinks
In the (Weighted) Tree Augmentation Problem, we are given a tree $T = (V,E)$ and a set of additional edges $L$ called links with non-negative costs. Each link $\ell = (u,v)$ covers the tree edges ...
- 557
0
votes
1
answer
65
views
Is there FPT or XP algorithms knowm for Shortest Steiner cycle and $(a,b)$-Steiner path problem
Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems.
The Shortest Steiner cycle problem is defined ...
- 141
1
vote
0
answers
47
views
Is there an FPT or XP algorithm known for this version of $k$-edge disjoint paths problem?
The shortest $k$-edge disjoint paths problem is defined as follows:
Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$.
Question: Find (if exist) $k$-pairwise ...
- 141
1
vote
0
answers
73
views
Cheapest Insertion is $2$-approximation for TSP
Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
- 11
0
votes
0
answers
88
views
Separation oracle for breaking cycles in directed graph
I am working on a directed graph problem and am collaterally interested to know whether there is a separation oracle for the following set of linear constraints.
We are given a directed graph $G$ ...
- 89
0
votes
0
answers
34
views
Is there an MMSNP formula for 3-colouring?
By MMSNP, I mean Monotone Monadic SNP without inequality. For $k\in\mathbb{N}$, the problem $k$-COLOURABILITY takes a graph $G$ as input and asks whether $G$ is $k$-colourable.
It is well-known that ...
- 1,603
1
vote
0
answers
15
views
Locally bijective homomorphism between locally-H graphs
Graphs in this question are finite, simple and undirected.
For a fixed graph $H$, a graph $G$ is said to be locally-$H$ if for every vertex $v$ of $G$, the neighbourhood of $v$ in $G$ induces $H$ (i.e....
- 1,603
2
votes
0
answers
58
views
Is k-ACYCLIC COLOURABLITY in CSP?
All graphs in this question are finite, simple and undirected.
Let $k$ be a fixed positive integer.
A $k$-colouring of a graph $G$ is a function $f\colon V(G)\to\{1,2,\dots,k\}$ such that $f(u)\neq f(...
- 1,603
4
votes
1
answer
79
views
Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)
I am learning the very basics of tensor network theory and I am trying to understand why some ways to contract tensors are better than others in terms of computational complexity. Knowing in which ...
0
votes
0
answers
48
views
Locally bijective homomorphism between line graphs
Graphs in this question are finite, simple and undirected.
A function $\psi\colon V(G)\to V(H)$ is a locally bijective homomorphism from $G$ to $H$ if for every vertex $v$ of $G$, the restiction of $\...
- 1,603
0
votes
0
answers
65
views
Does the Christofides algorithm ensure this inequality?
Let $(X,d)$ be a finite metric space. Let $C$ be a Hamiltonian cycle (over $X$) outputted by Christofide's algorithm. Also, let $K$ be a minimum spanning tree. I am aware that Christofide's algorithm ...
- 141
0
votes
0
answers
34
views
On infinite bipartite graphs with no infinite rays
I'm working on a problem in logic and it reduces to proving that a certain infinite graph is connected. The graph has the following properties:
It is bipartite
It is not necessarily finite (or ...
- 193
0
votes
0
answers
19
views
2-connectivity of dual of a minimal cut in a bounded genus graph
Let $G$ be a graph of genus $g$ embedded on a surface of genus $g$. Let $s,t \in V(G)$. Consider a minimal $s,t$-cut $C$ in $G$. Let $H$ consist of the union of faces adjacent to $E(C)$. Notice that $...
- 2,267
2
votes
1
answer
114
views
Is the center of a BFS tree a good approximation of the graphs center?
Given a graph $G=(V,E)$, a center is a vertex $v\in V$ with minimal eccentricity (i.e., $v\in\text{argmin}_v\max_u d(u,v)$).
Finding the center of the graph can easily be done using all-pairs-shortest-...
- 21
2
votes
1
answer
106
views
Proving a property of minimal st-separators that are not minimum st-separators
Let $G$ be an undirected, connected graph, and $s,t$ non-adjacent vertices in $G$.
Denote by $k_{st}(G)$ the $st$-connectivity of $G$. That is, $k_{st}(G)$ is the size of any minimum $st$-separator of ...
- 65
3
votes
3
answers
471
views
Evaluating asymptotic probabilities of First Order Logic Formulas?
0-1 Laws in first order logic state that the probability of a FOL sentence $\Phi$, defined as follows:
$$P(\Phi) = \frac{|\{\omega \in \Omega^{n}:\omega \models \Phi\}|}{|\Omega^{n}|} $$
where $\Omega^...
- 684
1
vote
0
answers
23
views
Upper Bound for distance-two chromatic number in terms of maximum degree
Let us consider simple,finite, undirected graphs. A distance-two colouring of a graph $G$ is a fuction $f:V(G)\to\{1,2,\dots\}$ such that $f(u)\neq f(v)$ whenever $dist_G(u,v)\leq 2$. A distance-two ...
- 1,603
0
votes
0
answers
38
views
Reducing computing the partition function to computing the number of min-cardinality (s, t) cut
Consider a partition function for a graph as follows:
\begin{equation}
\mathrm{Z}_\mathrm{G}(\beta) = \sum_{z \in \{-1, 1\}^{n}} \beta^{\underset{(i, j) \in E, i < j}{\sum} w_{i,j} ~z_i z_j},
\end{...
- 153
7
votes
2
answers
193
views
Directed acyclic graphs with logarithmic diameter
Fix an ordering $v_1,\ldots, v_n$ of the vertices $V$ of a directed acyclic graph (DAG), so if there is a directed edge from $v_i$ to $v_j$ then $i < j$. Define the diameter of the graph to be the ...
- 201
1
vote
0
answers
56
views
On Negami's planar cover cojecture
For this question, let us consider only simple, finite, undirected graphs.
A homomorphism $\psi$ from a graph a $G$ to a graph $H$, $\psi\colon V(G)\to V(H)$, is a Locally Bijective Homomorphism from $...
- 1,603
0
votes
0
answers
115
views
Three questions about the LPA* algorithm
I have a few questions about the LPA* algorithm, I think I know the answers to most of these questions, but I just wanted to be sure.
Here is the pseudocode for reference:
and here is the link to the ...
- 9
0
votes
0
answers
47
views
Breaking ties in A* to produce same path as D*lite
What tie breaking criteria do I need to implement in A* to mimic exactly the same behaviour as D* lite. Ofcourse both algorithms use the same heuristic and cost functions. So basically if I run A* ...
- 9
3
votes
1
answer
93
views
Name for set of vertices that are pairwise within distance two
A 2-stable set (or a distance-two independent set) of a graph $G$ is a set of vertices which are pairwise at a distance greater than 2 in $G$.
Is there a name for a set of vertices which are pairwise ...
- 1,603
2
votes
0
answers
45
views
Existing results around approximation of minimum 2-edge connected Steiner subgraph
Problem $1$: minimum 2-edge connected subgraph
We are given a $2$-edge connected undirected graph $G(V,E)$, and we are asked to find a $\textit{spanning}$ subgraph $H$, with minimum number of edges, ...
- 141
5
votes
1
answer
153
views
Is there a standard axiomatization of graph width parameters?
There are many useful graph properties described as "width parameters" that show up in algorithm analysis (especially for FPT-type algorithms). The most famous example is probably treewidth,...
- 2,293
4
votes
0
answers
74
views
Reducing counting minimal vertex covers to counting minimum cardinality vertex covers
Consider two problems.
Problem 1: Given a graph $G = (V, E)$, find the number of minimum cardinality vertex covers of $G$.
Problem 2: Given a graph $G = (V, E)$, find the number of minimal vertex ...
- 153
0
votes
1
answer
88
views
On structure of graphs with average degree equal to maximum average degree
For a simple graph $G$, the $\text{average-degree}(G)=|E(G)|/|V(G)|$ and
the maximum average degree $\text{mad}(G)=\max\{\text{average-degree}(H)\colon H \text{ is a subgraph of } G\}$.
If $\text{...
- 1,603
2
votes
0
answers
55
views
Is there a poly-time algorithm to compute the drawing of a simple graph (need not be planar) in a 2D-plane such that any two edges cross at most once?
Does there exists a ploynomial time algorithm to embed a simple graph(need not be planar) in a plane satisfying the following conditions?
No edge touches vertices other than its end vertices.
At any ...
1
vote
0
answers
168
views
Easier famility of graphs for MAXCUT [closed]
I would like to know if there are particular family of graphs for which the Goemans-Williamson MAXCUT Approximation Algorithm renders higher than 0.878 approximation ratio. TIA
- 997
1
vote
0
answers
107
views
Is finding a very large clique NP-hard?
We know that, unless P=NP, for any $\epsilon$ we can't distinguish in polynomial time between the two cases:
There exists a clique of size at least $n^{1-\epsilon}$
All cliques have size at most $n^\...
- 191
0
votes
0
answers
69
views
Is there a term for 'no-turn-back walk' in graph theory?
Let $G$ be a finite undirected graph. A walk in $G$ is a finite sequence $<v_1,e_1,v_2,e_2,\dots,v_{k-1},e_{k-1},v_k>$ where $v_j$'s are vertices in $G$, $e_j$'s are edges in $G$, and $e_j=v_jv_{...
- 1,603
3
votes
0
answers
44
views
Does high connectivity of line graph of $G$ imply high (cyclic) connectivity of $G$?
All graph considered here are finite, simple and undirected.
We know that a graph $G$ is $k$-edge connected if and only if its line graph is $k$-connected (where $k\in\mathbb{N}$). In particular, if $...
- 1,603
2
votes
0
answers
60
views
Summing over weighted paths optimally
Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications?
Is there a name for this problem?
This comes up in ...
- 4,631
3
votes
1
answer
102
views
On cubic planar graphs with face boundaries of length divisible by 4
All graphs considered here are finite, simple and undirected.
Let $\mathscr{G}$ denote the class of cubic plane graphs for which all face boundaries are of length divisible by four. The 3-cube $Q_3$ ...
- 1,603
1
vote
0
answers
39
views
Cycle double covers of cubic graphs using only a few cycles
This is a reference request question. Let $G$ be an arbitrary cubic graph.
Is the problem of finding a cycle double cover $D$ of $G$ with minimum number of cycles in $D$ studied in the literature?
I ...
- 1,603
1
vote
1
answer
180
views
How to show that Color Tiles is NP-Complete
Color Tiles is a puzzle game where color tiles are laid out in a rectangular grid. A tile is visible to an empty grid cells if there is a clear line-of-sight in one of the 4 cardinal directions (You ...
0
votes
0
answers
26
views
How does symmetric difference of b-matchings look like?
It is easy to see that symmetric difference of two matchings are cycles or simple paths. But what about b-matchings? Is there anything known about how they look? Even for restricted cases such as ...
- 109
1
vote
0
answers
28
views
Cycle decompositions of locally linear 4-regular graphs
(Preface)
We consider only finite, simple, undirected graphs here. An orientation of a graph $G$ is obtained by assigning some direction to each edge of $G$.
(Question starts)
A graph is locally ...
- 1,603
0
votes
1
answer
72
views
Is a grid graph a vertex-minor of a complete graph? [closed]
Consider a graph $G$. A graph $H$ is the vertex-minor of the graph $G$ if $H$ can be obtained from $G$ using vertex deletions and local complementations. For more information, look at Definition 2.1 ...
- 153
8
votes
0
answers
109
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
1
vote
0
answers
43
views
Properties of half-way locally bijective homomorphisms between Eulerian orientations
Short Version
Let $G$ and $H$ be two Eulerian graphs and let $\overrightarrow{G}$ and $\overrightarrow{H}$ be Eulerian orientations of those graphs. Let $f$ be a homomorphism from $G$ to $H$.
(...
- 1,603
1
vote
0
answers
33
views
Is arrangement-type graph on cyclic $k$-permutations of $n$ already studied?
The arrangement graph $A_{n,k}$ is the graph whose vertices are $k$-permutations of an $n$-vertex set $X$ (say, $X=\mathbb{Z}_n$) and two $k$-permutations are adjacent if they differ in exactly one ...
- 1,603
0
votes
0
answers
94
views
optimization on graph edges selection
I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there.
I am ...
- 1
-1
votes
1
answer
243
views
Does such a graph exist? [closed]
[EDITED FOR CLARITY]
Does there exist an edge-colored graph $G$ with the following properties?
$G$ has a vertex $r$ with exactly three, distinctly colored, incident edges: $(r, u)$, $(r, v)$, $(r, w)$...
- 49
6
votes
1
answer
328
views
Complexity of optimal elimination for a planar tensor network
Edit Dec 15 it's not obvious this problem is tractable when further restricting to trees, see cs.SE question
Suppose we need to sum out variables in a tensor network (a factor graph where each ...
- 4,631
-1
votes
1
answer
110
views
Algorithm for finding traffic equilibrium
I watched a youtube video about a certain interesting property of springs and road networks. It made me think: if we represent a network of roads as a graph where edges are roads described by a ...
2
votes
0
answers
56
views
Complexity of a matrix partition problem in graphs
All graphs in this question are finite, simple, and undirected. Let $H$ be a regular graph on at least five vertices, let $v_1,v_2,\dots,v_n$ be the vertices in $H$, and let $M$ be the adjacency ...
- 1,603
2
votes
1
answer
56
views
Is every 4-colourful Eulerian Orientation of a planar 4-regular graph good?
Let $G$ be a simple undirected plane 4-regular graph. Basic definitions are given at the bottom of this question.
An Eulerian orientation of $G$ is good if for each vertex $v$ of $G$, the edges around ...
- 1,603