Questions tagged [subgraphs]
The subgraphs tag has no usage guidance.
20
questions
0
votes
1
answer
25
views
Fully Connected Graph to Lattice
I am looking for algorithms (or at least something similar to the problem definition):
Given a fully-connected weighted graph $G$ with $n$ nodes, find a subset $S$ of edges that form a square lattice ...
- 113
0
votes
1
answer
59
views
Is a predecessor subgraph always connected?
Given an undirected graph $G$ with non-negative edge weights, how can we prove that the predecessor subgraph $G_{p}$ of $G$ is always connected?
Here's how the predecessor subgraph is defined: for a ...
- 67
1
vote
1
answer
38
views
Densest Sub Graph and forbidden Pairs
Given two graphs $G$ and $F$ on the same vertex set $V$. Compute a sub set $\tilde{V}\subset V$ which' sub graph of $G$ is of maximum density and does not have any pair that is connected in $F$.
...
2
votes
1
answer
37
views
Largest isomorphic subgraphs of two graphs with features
the following question came up in a problem I am working on:
Suppose you have two graphs $G_1=(V_1, E_1), G_2=(V_2,E_2)$ that have features attached to them, i.e. to every $v\in V_1$ or $v\in V_2$ ...
0
votes
0
answers
15
views
Ordered nodes/edges subgraph isomorphism
I'm given two graphs: $G=(V_G,E_G)$ and $H=(V_H,E_H)$.
Additionally, there is a special ordering provided that is consisted between these two graphs. Node indexes below are mapped to the $G$:
$V_G: [0,...
1
vote
3
answers
138
views
Algorithm to find Minimal Spanning Subgraph
I'm attempting to solve this problem:
Given an undirected connected graph $G=(V,E)$ with $\mathrm{weight}(e)>0$ for all $e \in E$, and a subset $S \subseteq V$, we define that a sub-graph $H=(V',E')...
- 315
0
votes
1
answer
370
views
Subgraph Isomorphism Problem NP complete?
I found many solution online on how to reduce Subgraph Isomorphism problem to Clique, but how do I prove that it is NP complete by reduction from independent set?
I'm struggling to figure out this ...
2
votes
0
answers
41
views
Finding a circle within a circle
Let $G=(V,E)$ be undirected, and let $s,t\in V$ and $C\subseteq E$ be a circle that contains $s$ and $t$. Assuming $s$ and $t$ are on the circle $C$, we are given a set of edges $F\subseteq E$ which ...
- 435
1
vote
0
answers
46
views
Finding highly-connected regions of graphs
I have a large network of 10,000 nodes and I am trying to identify subgraphs which are clique-like, in that they share many connections. I don't a priori know how many subgraphs fit this criteria.
To ...
- 11
3
votes
2
answers
215
views
Maximum planar subgraph problem
Given a graph G I want to find the maximum planar subgraph which is a grid graph.
(Because the nodes of this subgraph represent points on a grid).
Is there any library in python for finding the ...
- 59
1
vote
1
answer
66
views
Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?
Let suppose we order the nodes first by degree (in + out), to get a list of node structures:
...
- 495
2
votes
1
answer
117
views
Find the directed subgraph with least edges that preserves connectivity
I have a directed graph $G$ with a set of nodes $N$ and a set of edges $E$ with the following property : if $(A\to B)\in E$ and $(B\to C)\in E$, then $(A\to C)\in E$, for all nodes $A,B,C$.
I would ...
- 123
2
votes
1
answer
58
views
Do graphs with a bounded number of incident edges have a polynomial-time subgraph-isomorphism algorithm?
It is well known that the subgraph isomorphism problem is NP-complete. And so a polynomial-time algorithm for solving it would mean P = NP. Thus I'm interested in whether a bounded version of the ...
- 495
3
votes
1
answer
387
views
Minimum number of groups such that every element in graph is included?
Problem Description
Note: I originally posted this question on Stack Overflow but was referred to this community instead.
I have a graph containing selectors and elements. An element can have multiple ...
2
votes
1
answer
265
views
Determine if there's a $P_3$ as an induced subgraph in a graph $G$
Given a graph $G$ on $n$ vertices with $m$ edges, show an algorithm that determines if there's a $P_3$ as an induced subgraph in $G$ in $O(m+n)$ time. ($P_3$ is the path on 3 vertices).
What I was ...
- 317
0
votes
1
answer
108
views
Find subgraphs that can only be reached by two nodes
I want to find subgraphs in a graph that are only connected to the rest of the graph by two nodes; for example, node A is connected to the rest of the graph, as well as node F, but nodes B-E are only ...
- 101
2
votes
0
answers
119
views
How to calculate delta Q (modularity increase matrix) in graphs?
I've been trying to implement the Three-stage Algorithm to compare its results with our new proposed algorithm with different datasets than those mentioned in the article. I've succeeded in ...
2
votes
1
answer
61
views
Is CMCG (Constrained Maximum-Weight Connected Graph) problem NP-complete?
MCG Problem: Consider a positive integer R and an undirected graph G = (V, E), in which each vertex is assigned a weight (or value). The maximum-weight connected graph (MCG) problem
is to find a ...
- 87
0
votes
1
answer
281
views
Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex
Consider an undirected graph $G = [V,E]$. Let $V$ be the set of vertices: $V = \{v_1,..,v_n\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v_1$. I want to ...
- 87
3
votes
1
answer
729
views
Is a subtree of a minimum spanning tree a minimum spanning tree of the subgraph spanned by the subtree?
Let $G$ be a connected weighted undirected graph. Let $T$ be a minimum spanning tree (MST) of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T_a$ and $T_b$, where $Ta$...
user119710