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
20
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
21
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
7
votes
1
answer
185
views
Random Cerny Conjecture
For simplicity, all DFAs will be using the binary alphabet $\{0,1\}$. Let $M$ be a synchronizable DFA. We let $p(M,n)$ be the probability that a random $x\in \{0,1\}^n$ will synchronize $M$.
We define ...
- 13.5k
16
votes
3
answers
1k
views
Subgraph isomorphism with a tree
If we have a large (directed) graph $G$ and a smaller rooted tree $H$, what is the best known complexity for finding subgraphs of $G$ isomorphic to $H$? I am aware of results for subtree isomorphism ...
- 261
1
vote
0
answers
47
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
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 ...
CommunityBot
- 1
38
votes
17
answers
5k
views
Conjectures implying Four Color Theorem
Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-...
- 117
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 ...
- 1,422
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
72
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
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 ...
- 35.7k
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
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
14
votes
1
answer
347
views
Generating Graphs with Trivial Automorphisms
I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism.
It is "commonplace" (yet controversial!) to assume the existence ...
- 14.8k
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-...
- 211
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 ...
- 166
7
votes
2
answers
582
views
Capacitated multiple vehicle routing problem with handovers
I'm looking for literature about a variant of the capacitated vehicle/fleet routing problem (a.k.a. VRP, CVRP, etc.) that takes into account the possibility of handovers between multiple vehicles, i.e....
- 61
17
votes
2
answers
4k
views
Finding k shortest Paths with Eppstein's Algorithm
I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works
and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap ...
- 107
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^...
- 1,110
19
votes
2
answers
864
views
Axioms for Shortest Paths
Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences ...
- 107
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
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{...
CommunityBot
- 1
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
25
votes
6
answers
2k
views
Graph families which have polynomial time algorithms for computing the chromatic number
Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings.
...
- 261
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
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,...
- 50.2k
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,237
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
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
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
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
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
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
-2
votes
1
answer
315
views
Find research partner (profession and beginner)
I've 10 years of industrial work, but in my free time, I do research, write papers to conferences, help to teach to my old friend at the university and I even did a Ph.D. full-time program.
Now, I've ...
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 ...
- 22.3k
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
4
votes
0
answers
294
views
Computational Complexity of cycle double cover
Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...
- 13.5k
35
votes
4
answers
2k
views
Why is "topological sorting" topological?
Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why ...
- 119