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
36 views

Are there good analogues to Sparsest Cut/Balanced cut for vertex separators instead of edges cuts?

Most problems about cutting graphs into roughly equal parts such as Sparsest cut, Graph partition, Balanced Cut, etc are based on minimizing the size of an edge cut. Even if all of those problems are ...
user avatar
-2 votes
0 answers
27 views

Comparing objects [closed]

Say for example you have 100 list objects, each list containing a mixture of strings and integers, contained within a dictionary like so {a : [100, "cat", 50, "mouse"], b : [100,&...
user avatar
0 votes
0 answers
23 views

Comparing communication network graphs [closed]

I started out with a grid graph, performed some operations on it, and ended up with a set of networks; for example, , , , I need to compare these graphs. A thought that I had was to compare them with ...
user avatar
  • 101
2 votes
1 answer
69 views

Regularity Lemma for Multi-Relational Graphs?

Is there an analogous to Szemerédi regularity lemma in the setting, where I have multi relational graph i.e. I have $n$ nodes, but instead of having edges to be in $\{0,1\}$ i.e. there is an edge or ...
user avatar
  • 704
0 votes
0 answers
37 views

Comparing networks using graph theory [closed]

I'm new to graph theory so forgive if I use unconventional terminology. Please ask if there's any confusion regarding the statements I make. I have a bunch of undirected, unweighted, simple graphs ...
user avatar
  • 101
2 votes
0 answers
69 views

Finding Hamilton cycles in random graphs

For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)? If this is an open problem, I will also accept an empirically ...
user avatar
1 vote
0 answers
49 views

Find the minimum cost spider joining a root to some leaves

A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider. I am interested in the following problem: We are given an undirected graph $G = (V,E)$...
user avatar
0 votes
0 answers
25 views

How to maximize flow through a graph based on edge orientation (in 3D Cartesian Coordinate Space)?

Problem Stmt: Suppose you have a graph $G$ with edges $E$ and nodes $V$. The nodes have ${x,y,z}$ coordinates in 3D Cartesian space. Assuming each node contains an $x$ amount of material, the idea is ...
user avatar
  • 1
2 votes
0 answers
64 views

Origin of Berge's (Weak) Perfect Graph Conjecture

In an account of his thought process (refer p. 3) leading up to the perfect graph conjecture (which I'm preparing a seminar talk on), C. Berge states what seems to be a crucial step: (1) a graph $G$ ...
user avatar
  • 21
0 votes
0 answers
68 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
1 vote
0 answers
48 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
  • 75
1 vote
0 answers
52 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
78 views

Is there FPT or XP algorithms known 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
50 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
76 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
91 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
35 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
62 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
84 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
49 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
66 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
116 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
107 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
  • 75
3 votes
3 answers
475 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
  • 704
1 vote
0 answers
24 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
196 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
64 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
48 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
47 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
155 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,313
4 votes
0 answers
75 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
90 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
  • 190
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
104 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
40 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
182 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
29 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
76 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

1
2 3 4 5
30