# Questions tagged [graph-theory]

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

1,323 questions
Filter by
Sorted by
Tagged with
1k views

### is Facebook friendship graph connected? [closed]

In Facebook friendship graph the nodes are profiles and the edges are friendships (alternatively subscriptions could serve as well if we allow directed edges). Is the graph connected? (Obviously it ...
113 views

### Finding the maximum no. of people who get along in a group [closed]

Suppose that there are 15 people in a room. Assume that each person gets along with other people in the room (but not everyone). (Note that the "feeling is mutual" between any two people who are ...
89 views

### tagging and graph “compression”

I have a question on stack-overflow about "compressing" a graph. Suppose I have tags from a finite set $T$ and objects from a finite set $O$. Moreover there are (uni-directional) links from elements ...
518 views

### How to find the minimum number of vertices to join disconnected components of a graph? [closed]

Suppose, i have a graph with fixed number of nodes and edges. However, all the nodes doesn't remain active all the time causing the graph disconnected. In this sort of situation, i want to find out ...
28 views

### Algorithm to decide percentage of data from previous node, current node and forward nodes

I have a graph-like structure, let's say there is one node $C$, who has 2 predecessors $A,B$ and 1 successor $D$. I have a value of $C$. Let's say value at $C=30$%. From this, I could infer that I ...
7k views

### Efficient algorithm to create a directed dependency graph

I am looking for an efficient algorithm to create a graph like this: Initially the graph is filled with x then hs then ...
3k views

### Algorithm to find shortest path from a set of nodes to another set of nodes? [closed]

I'm developing a route planner, and I was reading some graph theory. I read a little bit of Dijkstra's shortest path, shooting star and turn restrictions, and I tend to think that this algorithms are ...
413 views

### “tree-like” vs “DAG-like” resolution

hi all there seems to be a deep/not-much-explored phenomenon in the way that SAT resolution proofs can define a tree and/or a DAG & its relationship to lower bounds/circuit complexity. could there ...
104 views

886 views

### Compact representation of DAG,

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that: ...
147 views

### Is a k-connected graph also k-1 connected?

So I'm reading about k-connected graphs, and I'm a little confused about them. This is the main definition I've seen: A graph is k connected if and only if for any distinct x, y vertices in the graph,...
275 views

### How to prove that a 3-connected 5-regular planar graph has chromatic number <= 4? [closed]

I can think of a way that to prove a 3-connected 5-regular planar graph does not contain a 5-critical subgraph. We can choose two non-adjacent vertices a,b and contract them into a single vertex. If ...
181 views

### Destroy shortest path in graph

Given graph G(V,E)and two vertices A and B, show how to eliminate the least number of edges so that length of shortest path between A and B become longer.(I need an algorithm)
66 views

### How to find the pair of two of edges which, removed from a graph, makes it disconnected?

How to find ALL the pair of two edges which, removed from a graph, makes it disconnected? I was thinking about a O(M * (N + M )) algorithm, and I am wondering if there is a better algorithm. Thanks in ...
265 views

### Polynomial algorithm for HAMPATH transformed into an algorithm that solves the problem sequentially? [closed]

Let us assume (probably wrongly) that P=NP, meaning that we know a way to output a hampath if it exists. A graph has $n$ vertexes. Can the algorithm that solves the problem be modified in ...
77 views

### Argument that Graph Isomorphism is polynomial via reduction to CNF

In short we found 3 invertible transformations which imply that Graph Isomorphism is polynomial. Meta reasoning: Isomorphism preserving transformation CNF to "sparse" CNF is possible and ...
52 views

### Distinguish Graph from Tree using Adjacency Matrix

Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle). For example, given the adjacency matrix: ...
117 views

### Looking for an algorithm to construct a graph from two subgraphs

I am looking for an algorithm to construct a graph from two subgraphs. The problem is as following: Given two graphs g1(V, E) and g2(V, E), find a graph G(V, E) where V(g1) ⊆ V(G), V(g2) ⊆ V(G), E(g1)...
1k views

### Time complexity of finding the shortest path in DAG [closed]

I apologize for seemingly basic question: I saw numerous times that the time complexity of finding the shortest path in directed acyclic graph is O(|V| + |E|). ...
807 views

### What is the complexity of the fastest method of k-coloring any graph? [closed]

I heard brute-force is the only method. Is there any other way? Is there a way to prove that the complexity cannot be exponential?
3k views

### Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. Suppose that G is a weighted undirected graph with positive ...
Short question: How many self-avoiding-filling-polygons are there in a grid-graph of $n×n$? Long question: Edit: This question is not about p = np. I am searching for a way to calculate the numbers ...