# Questions tagged [graph-theory]

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

1,436 questions
Filter by
Sorted by
Tagged with
21 views

### Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?

The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph. It seems like these problems would fall under the framework of network design problems (...
44 views

### What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?

Suppose we have a graph $G$ with treewidth $t$. Let $p \in (0,1)$ be a constant. Then let's independently remove each edge from $G$ with probability $p$. What is the expected treewidth of the ...
41 views

### Constructing boolean formula for graph coloring problem

For a given graph $G = (V, E)$, construct a Boolean formula $F$ of polynomial-size, which is true iff there exists a coloring of edges of the graph in 3 colors, such that any two edges with a common ...
37 views

### Permutation Graphs is Chordal?

Whether the permutation graphs are a subclass of the chordal graphs? If not, what is the counter-example?
95 views

### Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$? I read abstract of this paper that mentioned an algorithm with running ...
102 views

### Does a graph resulting from the union of triangles has a particular name?

I have different simple triangle graphs. As an instance, $G_1=(V_1,E_1)=(\{1,2,3\},\{\{1,2\},\{2,3\},\{3,1\}\})$ and $G_2=(V_2,E_2)=(\{1,4,5\},\{\{1,4\},\{4,5\},\{5,1\}\})$. The union of both graphs ...
95 views

### exact path cover for undirected graph

In a Python plotting application, I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path. The number of ...
28 views

### Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
154 views

### State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia: The polynomial-time approximation algorithm for Max-Cut with the best known ...
49 views

### Minimal lexicographical path on DAG in O(||V| + |E|)

Let's assume, that we have directed asyclic graph and nodes U and V. Every edge of this graph is marked with alphabet letter (alphabet size is fixed). Is there any way to answer, what is the shortest ...
72 views

21 views

### Going from one base packing to another using basis exchanges

Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So ...
140 views

### Fastest exact algorithm for MAXCUT

Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA Ryan Williams, A new algorithm for optimal $2$-constraint satisfaction and its ...
224 views

88 views

60 views

### Number of connected partitions (or labelings) in a grid graph

Let $G$ be a 2D lattice graph (undirected) of size $W\times H$. Each "inner" vertex has $4$ adjacent vertices, whereas "boundary" vertices have $2$ or $3$ adjacent vertices, ...
55 views

### Prove that this linear relaxation has half-integral extreme points

Given a graph $G=(V,E)$, here is a Linear Relaxation of the edge cover polytope: (1) For each $v \in V, \sum_{e \in \delta(v)} x_e \geq 1.$ (2) For each $e \in E$, $0 \leq x_e \leq 1.$ Here $\delta(S)$...
57 views

### Weak incidence colouring

Let $G(V,E)$ be a simple undirected graph, let $k\in \mathbb{N}$, and let $I(G)=\{(v,e)\ :\ e\in E, v\in e \}$ (here, $v\in e$ means $v$ is incident on $e$). A $k$-incidence colouring of $G$ is a ...
82 views

### Monotone circuit representations of paths in a graph?

Consider a directed graph $G = (V, E)$ with a source $s \in V$ and sink $t \in V$. From $G$, I can define a monotone Boolean function $\phi_G$ on the set of variables $E$, in the following way: every ...
Define the common neighborhood of two vertices $u$ and $v$ of a simple undirected graph as the set $N(u,v)=N(u)\cap N(v)$. For a simple bipartite graph $G=(U,V,E)$, define the pairwise-common ...
### How long does it take at most for $k$ boolean variables to map back to themselves with a positive disjunctive update rule?
I have a vector of boolean variables $v=(x_1,\dots,x_k)$. In each step each variable is updated according to a positive disjunction like so: $x_1 \leftarrow x_i \vee \dots \vee x_j$ $\dots$ \$x_k \...