# Questions tagged [graph-theory]

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

1,373 questions
Filter by
Sorted by
Tagged with
366 views

### Is the following graph optimization problem approximable within a constant factor?

Let $G=(V,E)$ be an undirected graph, and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{pred}_{\pi}(v)$ (respectively $\text{succ}_{\pi}(v)$) the set of ...
125 views

344 views

### A variation on discrepancy involving random graphs

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$. The number of $+1$s that we have to assign is ...
700 views

### Computing a transitive completion / path existence oracle

There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible: Assume we get an input directed graph $G$ and would like to answer ...
226 views

### When does a graph admit an orientation in which there is at most one s-t walk?

Consider the following problem: Input: a simple (undirected) graph $G=(V,E)$. Question: Is there an orientation of $G$ satisfying the property that for every $s,t \in V$ there is at most one (...
379 views

### Parametrized Complexity of Counting Bicliques

In a previous question Parametrized Algorithm for Finding Bicliques, I inquired if there were fast parametrized algorithms for finding a $k\times k$-biclique in an $n$ vertex graph and learnt that it ...
180 views

### Graph partitioning, balancing on within subset edge weights

I'm interested in pointers to algorithms (approximation algorithms are fine) that attempt to partition a graph into two subsets such that the sum of the edge weights within each subset is (...
270 views

### Directed multigraphs as minimal automata

Given a regular language $L$ on alphabet $A$, its minimal deterministic automaton can be seen as a directed connected multigraph with constant out-degree $|A|$ and a marked initial state (by ...
2k views

366 views

### Is the complexity of this covering problem known?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
1k views

### Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion

I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if ...
412 views

498 views

282 views

### Spectral gap for random bipartite regular graphs

For a graph $G$, let its Laplacian be $\Delta =I − D^{−1/2}AD^{−1/2}$, where $A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm ...
6k views

### What are theoretically sound programming languages for graph problems?

There are numerous graph theoretic tools/packages. Each with its pros and cons. What should be the semantics/syntax of a programming language meant to solve graph theoretic problems?
2k views

### What kind of mathematical background is needed for graph theory?

It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years? Which subjects should be ...
632 views

### Have any generalizations of maximum weight matching been studied?

For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise. accordingly, a ...
520 views

### Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?

It is well known result proved by Holyer that deciding 3-edge colorability of cubic graphs is $NP$-complete problem. By Vizing's theorem, all cubic graphs are edge colorable using $\Delta +1$ colors....
2k views