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
12
votes
1answer
331 views

Negative results on identical particles approach to Graph Isomorphism (GI) problem

There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed ...
12
votes
1answer
1k views

Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance

We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some ...
12
votes
1answer
262 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 ...
12
votes
0answers
220 views

Hitting edges in graphs at random and let them die with honor

Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit ...
12
votes
0answers
168 views

Minimal rare subgraphs

I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other ...
12
votes
0answers
335 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 ...
12
votes
4answers
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/...
11
votes
4answers
703 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 ...
11
votes
3answers
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 (...
11
votes
3answers
423 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 ...
11
votes
3answers
690 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 ...
11
votes
1answer
388 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 ...
11
votes
1answer
794 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$ ...
11
votes
1answer
587 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 ...
11
votes
1answer
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 ...
11
votes
2answers
647 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.
11
votes
2answers
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 ...
11
votes
2answers
851 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 ...
11
votes
3answers
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 ...
11
votes
1answer
431 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,...
11
votes
1answer
374 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'...
11
votes
1answer
398 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 ...
11
votes
1answer
841 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-...
11
votes
1answer
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 ...
11
votes
3answers
4k 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 ...
11
votes
1answer
476 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$ ...
11
votes
1answer
982 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 ...
11
votes
0answers
341 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 ...
11
votes
0answers
145 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$. ...
11
votes
0answers
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 ...
11
votes
0answers
425 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 ...
10
votes
4answers
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 ...
10
votes
3answers
386 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 ...
10
votes
3answers
818 views

Number of connected components of a random nearest neighbor graph?

Let us sample some big number N points randomly uniformly on $[0,1]^d$. Consider 1-nearest neighbor graph based on such data cloud. (Let us look on it as UNdirected graph). Question What would the ...
10
votes
1answer
567 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 ...
10
votes
4answers
699 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 ...
10
votes
2answers
220 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 ...
10
votes
2answers
520 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 ...
10
votes
3answers
312 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 ...
10
votes
1answer
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 ...
10
votes
1answer
477 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 ...
10
votes
1answer
304 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 ...
10
votes
6answers
22k 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 ...
10
votes
2answers
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 ...
10
votes
1answer
327 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 ...
10
votes
2answers
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, ...
10
votes
2answers
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 ...
10
votes
1answer
194 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 ...
10
votes
1answer
672 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 ...
10
votes
1answer
509 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 ...

1
3 4
5
6 7
29