# Questions tagged [graph-theory]

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

183 questions
Filter by
Sorted by
Tagged with
14k views

### Data for testing graph algorithms

I am looking for a source of huge data sets to test some graph algorithm implemention. Please also provide some information about the type/distribution (e.g. directed/undirected, simple/not simple, ...
5k views

### Max-cut with negative weight edges

Let $G = (V, E, w)$ be a graph with weight function $w:E\rightarrow \mathbb{R}$. The max-cut problem is to find: $$\arg\max_{S \subset V} \sum_{(u,v) \in E : u \in S, v \not \in S}w(u,v)$$ If the ...
• 9,850
13k views

### Counting the Number of Simple Paths in Undirected Graph

How can I go about determining the number of unique simple paths within an undirected graph? Either for a certain length, or a range of acceptable lengths. Recall that a simple path is a path with no ...
• 301
1k views

### Maximal classes for which largest independent set can be found in polynomial time?

The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile ...
• 18.9k
3k views

### graphs from real-life problems

Where can I find graphs relevant to real-life problems? Two repositories I know of are: University of Florida's Sparse Matrix Collection Bodlaender's TreewidthLib
• 4,681
2k views

### What bounds can be put on counting reachable nodes in a dag?

Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is ...
• 4,796
3k views

### Network / Social network analysis visualization tools?

I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network /...
2k views

### Transitivity check vs. Transitive Closure

Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to ...
• 399
970 views

### Is this vertex ordering optimization NP-Hard?

Could you help me to prove that the following problem is NP-hard? Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ ...
• 563
357 views

• 3,254
1k views

### NP complete graph problems about structural properties

(This question is a bit of a "survey".) I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some ...
• 431
4k views

### NP-hard problems on paths

everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to ...
• 355
1k views

### Is feedback vertex set problem solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set (FVS) is NP-complete for general graphs. It is known to be NP-complete for degree-$8$ bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is ...
• 368
2k views

### Succinct circuit representation of graphs

The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE: END OF THE LINE: Given circuits S and P ...
• 5,961
7k views

### Partition a graph into node-disjoint cycles

Related problem: Veblen’s Theorem states that "A graph admits a cycle decomposition if and only if it is even". The cycles are edge disjoint, but not necessarily node disjoint. Put another way, "The ...
• 1,443
3k views

### Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3? I know it is NP-complete for the ...
• 2,143
2k views

### Gentle introduction to graph isomorphism for bounded valance graphs

I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it ...
• 1,281
2k views

### Cover Time of Directed Graphs

Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is ...
• 10.6k
4k views

### Is there an online-algorithm to keep track of components in a changing undirected graph?

Problem I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected ...
• 351
900 views

### References for Modular Decomposition

What are good papers/books to better understand the power of Modular Decomposition and its properties? I'm particularly interested in algorithmic aspects of Modular Decomposition. I have heard that ...
• 1,868
506 views

### Global properties of hereditary classes?

A hereditary class of structures (e.g. graphs) is one that is closed under induced substructures, or equivalently, is closed under vertex removal. Classes of graphs that exclude a minor have nice ...
• 18.9k
544 views

### Partition into interval graphs

Suppose there is a graph $G=(V,E)$. I want to test if $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs. I know ...
• 1,006
4k 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/...
• 3,440
1k views

### How to generate graphs with known optimal vertex cover

I'm looking for a way to generate graphs so that the optimal vertex cover is known. There are no restrictions on the number of nodes or edges, only that the graph is completely connected. the idea is ...
• 199
819 views

### Number of vertices present in all maximum matchings

Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible. Is there a solution beside the obvious remove ...
740 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 ...
• 1,955
1k 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 ...
• 9,438
453 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 ...
• 9,438
2k views

• 563
919 views

### What is complexity of this max-edge subgraph problem?

While discussing the question I had asked here, @NealYoung and I encounter another problem, which is to judge complexity of the problem below: Given a connected undirected graph, finding a maximum-...
• 439
1k views

### What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Input: a graph with n nodes, Output: A clique of size $O(\log n)$, Providing links to references would be great
5k views

### Polynomial Time Algorithm for Graph Isomorphism Testing [closed]

"Michael I. Troﬁmov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs. The paper is given in arXiv. The companion website gives a proof-of-concept ...
• 16.5k
573 views

### Pagerank in directed *acyclic* graphs (DAG)

I deal with pagerank computations on large directed acyclic graphs (DAG). I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ...
746 views

### Number of subgraphs with a given number of nodes

Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$. The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where $V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$ ...
• 6,780
213 views

### Finding a simple dual of a simple graph in some surface

Given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph ...
• 669