Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 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 ...
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 ...
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$ ...
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
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 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....
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(...
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 $\...
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 ...
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 ...
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 ...
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 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-...
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 ...
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....
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 ...
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^...
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 ...
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 ...
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{...
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{...
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 ...
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. ...
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 $...
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 ...
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,...
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 ...
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* ...
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, ...
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 ...
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
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^\...
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_{...
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 $...
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$ ...
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 ...
-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 ...
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 ...
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$...
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 ...

1
2 3 4 5
30