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
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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....
user avatar
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(...
user avatar
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 ...
user avatar
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 $\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 $...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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^...
user avatar
  • 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 ...
user avatar
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{...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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* ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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,...
user avatar
  • 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 ...
user avatar
  • 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{...
user avatar
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 ...
user avatar
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
user avatar
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^\...
user avatar
  • 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_{...
user avatar
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 $...
user avatar
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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$. (...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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)$...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
30