# Questions tagged [graph-theory]

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

1,354 questions
Filter by
Sorted by
Tagged with
332 views

### Directed Sparsest Cut on Planar Graphs?

The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the ...
3k views

### Incremental Maximum Flow in Dynamic graphs

I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/...
694 views

### Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Crossposted from MO. Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems that ...
2k views

### Extension to the Stable Marriage Problem ?

This may sound more like a social sciences question more than a TCS one, but it is not. When reading "Randomized Algorithms" which describes the Stable Marriage Problem, one can read the following (...
418 views

### Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

Denote by $\delta^+(G)$ the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree. In a related question, I've mentioned the Ghouila-Houri extension of Dirac's theorem on Hamiltonian ...
664 views

### History and status of the graph matching problem

Part of the difficulty of finding out more about this problem is that the graph matching problem is different from its much more famous cousin, the matching problem, but hard to be distinguished from ...
377 views

### MSO properties, planar graphs and minor-free graphs

Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. This is one of the most well-known ...
769 views

### Finding a dual of a graph

According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles, and below $S_n$ ...
559 views

### Complexity of Unique s-t-Connectivity

I would like to know whether the following problem can be decided in $\mathsf{NL}$ (nondeterministic logspace): Given a directed graph $G$ with two distinguished vertices $s$ and $t$, is there a ...
1k views

### Complexity of computing the average distance of a graph

Let $\rm{ad}(G)$ be the average distance of a connected graph $G.$ One way to compute $\rm{ad}(G)$ is by summing up the elements of $D(G),$ the distance matrix of $G$ and scaling the sum ...
597 views

### Find negative cycle with vertex constraints

Given a graph with weighted edges, how can we find a negative cycle that contains at least one vertex in a given vertex set $\{V_1, V_2, \ldots, V_k\}$? Thanks.
708 views

### Graph classes for which the diameter can be computed in linear time

Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) ...
4k views

### Any fast algorithm for minimum cost feedback arc set problem?

In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set. If each edge is associated with a weight $w$, the minimum cost ...
823 views

### For which families of graphs is Generalized Geography in $P$?

As @Marzio mentioned, the following game is known as Generalized Geography. Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows: At each turn (two players ...
1k views

### Regular Graphs and Isomorphism

I would like to ask whether there is an already published result on that: We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and ...
426 views

### Computation of max H-free sets

In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question,...
344 views

### Generalization of Dilworth's theorem for labeled DAGs

An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth'...
395 views

### Making SAT solvers competitive with specialized algorithms

What are obstacles to making SAT solvers competitive with specialized graph algorithms? In other words, is it feasible to expect SAT solvers that can replace the role of algorithm designer -- ie, be ...
781 views

### 3-Clique Partition for graphs of fixed diameter

The 3-Clique Partition problem is the problem of determining whether the vertices of a graph, say $G$, can be partitioned into 3 cliques. This problem is NP-hard by a simple reduction from the 3-...
253 views

### An improper planar coloring with monochromatic component size $\leq 2$

Let us relax the coloring a little bit, that is, we allow a small number of adjacent vertices to be assigned the same color. A monochromatic component is defined to be a connected component in the ...
241 views

### Optimal preprocessing for certain types of queries

Suppose we have a semigroup $(S,\circ)$ with elements $S=\lbrace s_1,s_2,\dots,s_n\rbrace$. Our goal is to compute products $s_i\circ s_{i+1}\circ \cdots\circ s_j$. In their paper "Optimal ...
3k views

### Number of reachable vertices in DAG for every vertex

Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running dfs from every ...
462 views

### Minimum equivalent digraph with respect to sources and sinks

Given a DAG (directed acyclic graph) $D$, with sources $S$ and sinks $T$. Find a DAG $D'$, with sources $S$ and sinks $T$, with minimum number of edges such that: For all pairs $u \in S, v \in T$ ...
938 views

### Confusion about reduction counting vertex covers to counting cycle covers

This confuses me. One easy case of counting is when the decision problem is in $P$ and there are no solutions. A lecture show that the problem of counting the number of perfect matchings in a ...
337 views

### A dynamic data structure to list triangles

Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations? Insert an edge into the graph Delete an edge from the graph Given a query ...
144 views

### Is RAMSEY COLORING in $NC$?

Say that a function $f$ is a RAMSEY COLORING if on unary input $n$, it returns a complete graph on $n$ vertices with its edges colored red and blue without a monochromatic clique of size $10\log n$. ...
158 views

### Generating a random graph with constraints on spectrum

Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple ...
409 views

### Cheeger's inequality for directed graphs?

Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to ...
3k views

### The number of cliques in a graph: the Moon and Moser 1965 result

I'm looking for the full text of the Moon and Moser 1965 clique result On Cliques in Graphs (there exist graphs with a number of maximal cliques exponential in $n$). My university's paywall doesn't ...
382 views

### Graph theoretic restriction to Proofs in Proof Complexity Theory

Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of ...
565 views

### Can such a matrix exist?

During my work i came up with the following problem: I am trying to find an $n \times n$ $(0,1)$-matrix $M$, for any $n > 3$, with the following properties: The determinant of $M$ is even. For ...
690 views

### What are the root difficulties in going from graphs to hypergraphs?

There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking. Why do you think problems ...
216 views

### Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

Let $Q$ be a hereditary class of graphs. (Hereditary = closed with respect to taking induced subgraphs.) Let $Q_n$ denote the set of $n$-vertex graphs in $Q$. Let us say that $Q$ contains almost all ...
515 views

### Completeness spanning trees

A spanning tree of a graph is called a completeness tree if the set of its leaves induces a complete subgraph in the host graph. Given a graph $G$ and an integer $k$, what is the complexity of ...
290 views

### Refinements of pair approximation for network analysis

When considering interactions on networks, it is usually very hard to calculate the dynamics analytically, and approximations are employed. Mean-field approximations usually end up ignoring the ...
7k views

### What is an algorithm to find a minimum vertex cover on a bipartite graph with weighted vertices?

I know that for an unweighted bipartite graph, I can find the minimum vertex cover by first finding the maximum matching and turning it into a vertex cover using König's Theorem. Is there a ...
473 views

### Finding even cycle in directed graphs

Given a directed graph, we want to decide whether it contains a directed cycle of even length. This 1997 paper by YUSTER and ZWICK states that the problem is not known to be in $P$ nor is it known to ...
302 views

### Hamilton Decomposition Decision Problem

Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a Hamilton decomposition of $G$ if the subgraph induced by each set $V_i$ is either a Hamilton graph ...
21k views

### Application of graph theory in computer science

I am a CS student. We did graph theory in one course. I found it interesting. What are the real applications of graph theory in the computer science field? For example, I found that some concepts ...
548 views

### Amplitude of Random Cubic Graphs

Consider a connected random cubic graph $G=(V,E)$ of $n =|V|$ vertices, drawn from $G(n, 3$-reg$)$ (as defined here, i.e. $3n$ is even and any two graphs have the same probability). Of course there ...
315 views

### Classes of graphs with superconstant treewidth

There are several interesting classes of graphs with bounded treewidth. For instance, trees (treewidth 1), series parallel graphs (treewidth 2), outerplanar graphs (treewidth 2), $k$-outerplanar ...
2k views

### Random walk and mean hitting time in a simple undirected graph

Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges. I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, ...
1k views

### Deciding graph homomorphism

Deciding Graph Homomorphism is in general NP-Complete. Are there any results which study this problem when the underlying graphs have algebraic structure (such as deciding homomorphisms from Cayley ...
152 views

### Is there a planar 4-regular graph that is 3-acyclic colourable?

A colouring is said to be an acyclic colouring if there is no bicoloured cycle (i.e each cycle gets at least 3 colours). Burstein proved that 4-regular graphs are 5-acyclic colourable. It seems to me ...
653 views

### Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory

The post is related to: https://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles How far away is the Lovasz bound from the zero-error ...
333 views

### Hidden path in square grids

I stumbled on an open problem posed by David Eppstein and I am interested in its complexity status. He conjectured that it is NP-complete. Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ 0’...
234 views

### “Relatives” of the shortest path problem

Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such ...
407 views

### Hardness of approximating fractional chromatic number on bounded degree graphs

Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average ...