# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

4,949 questions
Filter by
Sorted by
Tagged with
3 views

### Clever algorithm for ordered compact sub-grouping

I have a set of 2D points (called "seats"), with each having a scalar numerical value attached to it. I have an ordered sequence of groups, each with an integer attributed to it, such that ...
• 101
1 vote
42 views

### Is this graph grouping problem $\mathsf{NP}$-hard?

Let's introduce the notion of layer: given a simple graph $G$ a layer is a subgraph of $G$ satisfying the following property: If any pair of vertices is connected with an edge, these two vertices ...
• 1,696
1 vote
20 views

### Do edge lists have O(E) storage if default values are used for absent keys?

Ordinarily, edge list representations of graphs take $O(V+E)$ space, where $V$ is the number of vertices and $E$ is the number of edges. For example, consider a graph with 5 nodes and a single edge ...
• 1,568
33 views

### $O(|V||E|)$ algorithm for finding all the cut vertices in a connected graph

Given a connected graph $G = (V, E)$, how to find all the cut vertices in $G$ in $O(|V||E|)$ time? I have considered some algorithms for finding all cut vertices in a connected graph as follows. ...
• 7
1 vote
27 views

### Bron-Kerbosch algorithm for finding cliques missing a few edges?

The Bron-Kerbosch algorithm takes a graph and finds its maximal cliques in an efficient manner (as far as I'm aware, it is $O(3^{n/3})$, where $n$ is the number of vertices). Let $t$ be a positive ...
25 views

### Kruskal's algorithm including an edge

I'm trying to solve the following question in which I have to find a list of critical edges and pseudocritical edges. From my understanding of the problem, critical edges are edges that must be ...
• 101
206 views

### MSOL and Courcelle's theorem for maximum clique

The Clique Problem is known to be NP-complete but is known to be fixed-parameter-tractable (FPT) if the treewidth of the underlying graph is fixed. The traditional proof is by a dynamic programming ...
• 537
1 vote
31 views

### Chromatic Polynomial of Hamming Graphs

I'm trying to calculate the chromatic polynomial of different Hamming Graphs , especially $H(3, 3) = K_3 \times K_3 \times K_3$, so the Graph Cartesian product of the complete graph with three ...
• 61
1 vote
49 views

### Find the transitive closure but with a twist

Situation I have a set of set of elements V, and relations over V: a R b: "a is related to b" (reflexive and symmetrical) a N b: "a is not related to b" (anti-reflexive and ...
• 229
73 views

• 537
27 views

### Adding edges to enlarge vertex cover

Given a graph $G=(V,E)$, and two positive integers $k$ and $\gamma$, decide if there is a set of new edges to be added such that $|E'|=k$, $E' \cap E = \emptyset$ and any subset $V'\subseteq V$ of ...
• 537
1 vote
43 views

### BFS on directed graph with disjointed edges?

There is a graph (directed and unweighted) and a collection of nodes. If I want to find a tree that has all those nodes in it and potentially some other ones as well, would BFS be a good algorithm to ...
• 11
63 views

### Find hierarchical clustering of documents

Given some large set of documents, how would one find a human usable hierarchical clustering to them (ie. place them into a file system such that one can find a document in the minimal time)? My ...
• 121
364 views

### Easy/hard NP-hard problems on perfect graphs

Three problems --- Graph coloring, Stable set, and Clique --- are known NP-hard problems (on general graphs) that can be solved in polynomial time, when we know that the given graph is a perfect graph....
• 537
47 views

### Convert a Graph to a Good Graph using Maximum Matching in Bipartite Graphs Algorithm

Consider a graph $G = (V, E)$ where a vertex $v \in V$ is designated as the center if it is connected to every other vertex $u \in V$, such that both $uv$ and $vu$ are present in $E$. A ...
1 vote
41 views

### Shortest path between two nodes with time-dependent edge weights

I have city traffic data. The roads are represented as a directed graph (a road can have traffic both ways, at most two-lane roads included), vertices being points on a map where two or more road ...
• 111
29 views

### Given a family of 0-1 matrices $M$ find the sum of matrices from $M$ which has minimal rank

Given a family of matrices $M$ with entries in $\mathbb{F}_2$ find the subset $N \subseteq M$ such that the rank of the matrix $$A = \sum_{m \in N}m$$ is minimal. I am wondering if anyone have seen ...
• 225
1 vote
36 views

### MSOL framing of max-flow probem

Given a graph $G=(V,E)$ with edge capacities $c_e$ for each $e\in E$, a source $s\in V$ and destination $t\in V$, how do I frame the max-flow problem in MSOL?
• 537
32 views

### Implementation of planar graph max cut

http://comopt.ifi.uni-heidelberg.de/conferences/aussois2009/slides/pardella.pdf Can you simply implement or pseudo code the content of this slide as a whole?
18 views

### True/False: Given an edge $(u,v)$: no path exists from $u$ to $v$ in the residual graph w.r.t a max flow $\iff$ $(u,v)$ crosses some minimum cut

I was asked to show if this is true or false. I believe it is true, but proving it seems difficult. Is it true and how might one show this?
• 113
22 views

### Tree width given path decomposition

I have a family of graphs whose path decompositions I know. Is it possible to compute the tree-width of these graphs in polynomial time?
• 537
437 views

### Undecidable problems in finite graphs

Are there any natural questions in finite graphs (or digraphs) that are undecidable?
• 537
39 views

### Why there is no definition of cut vertex in directed graph?

We know cut vertex is an important definition in undirected graph, indicating a vertex which when removed, the number of connected components would increase. And we also have an efficient algorithm ...
• 23
47 views

### Usage of matrix multiplication for distance products

This is more of a validation question, for the current best known results. On one hand, we have classical matrix multiplication. Its running time is denoted as $n^\omega$. On the other, we have ...
36 views

1 vote
46 views

### Proving that the shortest simple path problem between two vertices 𝑠 and 𝑡 in a graph with given path upperbound be positive is NP-complete

This is the same problem here but with one more condition that the sum of the distance cannot be a negative integer. The full description of the problem is: Is it possible to find a simple path (no ...
• 113
720 views

### What don't I understand in topological sort using DFS?

Wikipedia says: The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since ...
• 493
1 vote