Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,850
questions
3
votes
1
answer
57
views
Partition a graph into connected subgraphs of 3 vertices each
We need to partition a graph into subgraphs of 3 vertices each, such that every subgraph has at least 2 edges.
The problem is similar to the partition into triangles problem (which is NP-complete) but ...
- 71
4
votes
0
answers
74
views
Constant factor approximation algorithm for Vertex Deletion version of Maximum Diameter Bounded Subgraph
I've been stuck with this problem for quite a while now, and after reading so many papers I'm unsure whether this is even possible.
The problem is quite simple:
Given $G = (V, E)$ an undirected graph, ...
- 41
0
votes
0
answers
32
views
Directed graph where each node must contain all elements from source nodes
I'm looking for a directed graph data structure where each node is unique and contains a set of elements (at least one).
Each node must contain all elements from nodes pointing to it so it possible to ...
4
votes
1
answer
322
views
Partitioning a graph into connected pairs and triplets
We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer.
When $k=2$, the problem is equivalent to the perfect matching problem which is ...
- 71
0
votes
0
answers
21
views
Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds
Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system:
1: Assume that initially the nodes have IDs of size $\log(n)$ bits
2: The root is ...
- 315
0
votes
0
answers
18
views
Importance of an edge regarding distances
Given a graph $G=(V,E)$ and any edge $(u,v) \in E$, let us denote by $G_{(u,v)}=(V,E\setminus\{(u,v)\})$ obtained from $G$ by removing this edge.
I am interested in the difference between the average ...
- 625
0
votes
0
answers
23
views
Sparsest cuts of planar graphs
Several algorithms for sparsest cut (and other kinds of balanced cuts) in planar graphs have been published, like for instance:
Finding minimum-quotient cuts in planar graphs, James K. Park, Cynthia ...
- 625
0
votes
0
answers
25
views
Designing Algorithm for MST problem for a optical fiber network bounded by costs
So I need to design an algorithm for the following problem:
Suppose we need to build an optical fibre network for 20 cities. We are given a distance matrix of the cities which tells us which cities ...
- 101
3
votes
1
answer
48
views
Vertex Cover on Comparability Graphs
Is there anything known about the hardness of Vertex Cover on the subclass of comparability graphs? In particular, is it known whether the problem is still NP-hard?
Related Results: In "Modular ...
- 151
1
vote
1
answer
58
views
Reducing the min weight perfect matching problem to a T-join
My lecture notes for $T$-joins states:
If $T = V$ then $T$ -joins of cardinality $V/2$
are exactly the perfect matchings of $G$ = $(V ,E)$.
So, the minimum weight perfect matching problem can be ...
- 423
-2
votes
1
answer
66
views
What would be an efficient algorithm that finds the maximum number of party people?
You want to organize a party and invite as many of your N friends as possible so that the following condition is met: at a party, everyone invited must know at least three other guests and must not be ...
user160756
0
votes
1
answer
37
views
How can I track multiple shortest paths from one node to another using Dijkstra / Bellman-Ford
I want to find how many shortest paths are there from Node A to node B.
For example, let's say we have a graph with 3 nodes and 3 connections:
from 1 to 2 weight 5
from 1 to 3 weight 11
from 2 to 3 ...
0
votes
1
answer
75
views
BFS on a graph and BFS on a tree
I found the following question in my book and I have no clue on what the answer should be:
What is the condition on search graph so that BFS Algorithm for graph and BFS Algorithm for tree generate ...
- 1
0
votes
1
answer
55
views
Pathfinding in a known maze with step limitations, points of interest and more
I hope this is the correct subpage of SE, if not please direct me to the more appropriate place.
Imagine the following scenario:
You are put into a random but known position inside a given maze. The ...
- 101
0
votes
0
answers
28
views
If a graph is 2-vertex-connected, then it can be produced by $K_3$, using only edge division and addition
I want to prove that if a graph is 2-vertex-connected, then it can be produced by $K_3$ (the simple triangle), using only edge division ("splitting" an edge, $(u,v)$, by creating a new ...
4
votes
1
answer
216
views
Finding a minimum cut with an upper bound on the set sizes
In the (unweighted) minimum k-cut problem, the goal is to partition the nodes in a given graph to at least $k$ subsets, such that the number of edges between different subsets is as small as possible.
...
- 5,720
1
vote
0
answers
39
views
Networks and data flow - graph algorithms for propagating updates from nodes correctly
Suppose I have an acyclic directed graph of Nodes which subscribe to Events. When an Event callback is activated for some Node, the Node's internal update() method is called. Then, because the Node ...
- 837
1
vote
0
answers
29
views
generating solvable puzzles for a Double-Choco puzzle game. efficient data structure and algorithm to be used in? [closed]
I'm working on implementing a puzzle board game called Double-Choco published by Nikoli magazine
Where the board is a 2-dimensional matrix with cells that are either white or gray. The goal is to ...
- 111
1
vote
1
answer
54
views
How can we find a shortest closed walk passing through all vertices?
How can we find a walk with the minimal length starting from a vertex $v$, passing through all vertices and returning back to $v$?
We allow vertices and edges to be repeated along the walk. The ...
- 303
0
votes
0
answers
20
views
Solving a weighted minimum dominating set problem with its unweighted counterpart?
Question
Is it possible to find a solution to the weighted minimum dominating set problem, by solving a (related), unweighted minimum dominating set?
Elaboration
In essence, can one convert a ...
- 123
0
votes
0
answers
32
views
Given a complete graph with injective weight function, the $n-2$ most heaviest edges are not in any MST
Let $G=(V,E)$ be an undirected complete graph, where $|V|=n,|E|=m$.
Let $w:E\rightarrow \mathbb{R}^+$ be an injective weight function.
Prove that for any MST, the $n-2$ most heaviest edges are not in ...
- 165
2
votes
1
answer
96
views
Minimum spanning tree with dynamic edge cost based on degrees
I have a problem that I'm struggling to solve or even name, I'd really appreciate any help or pointer to potential existing solutions.
Suppose there is a connected graph $G$ and we are trying to find ...
- 21
1
vote
1
answer
93
views
Boolean constraints for a connected component of a graph
Suppose I have an undirected graph $G=(V,E)$, and boolean variables $x_v$ (one for each vertex $v \in V$). These variables select a subset $S \subseteq V$ of vertices, namely the vertices $S=\{v \mid ...
D.W.♦
- 156k
2
votes
2
answers
90
views
Does there exist an algorithm / software that finds optimal graph partition while enforcing contiguity on a subgraph?
I am interested in the traditional graph partitioning problem, which roughly speaking seeks to obtain a partition of a graph into a number of components, in which each component has about the same ...
- 121
1
vote
1
answer
69
views
4-regular graph without small cycles
My name is Balchandar Reddy. I am a research scholar and am currently working on graph algorithms. I am looking to find a 4-regular graph that does not have small cycles. For example, I want to ...
- 162
0
votes
1
answer
37
views
Universal lower bound of the multi message problem
The multi message problem is:
Let there be an undirected graph $G = (V,E)$ with $n$ vertices, and let $r \in G$. The algorithm sends a message $M_i$ of size $\Omega(\log(n))$ to each vertex $v_i$ ...
- 315
1
vote
1
answer
149
views
Would edges with negative weights affect Prim's Algorithm?
I was studying graphs and it got me wondering if edges with negative weights affected the outcome of Prim's Algorithm in finding a minimum spanning tree. So would the Prim's algorithm still find a ...
0
votes
1
answer
98
views
How to find the subsets S and T and the min-cut of this graph?
I get the residual graph by Ford-Fulkerson Algorithm:
I get that the minimum cut can be found by the residual graph, and when traversing this residual network from the source to all reachable nodes, ...
- 3
3
votes
1
answer
340
views
Maximum Independent Set of a Tree using Greedy Algorithm
I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph?
...
- 31
0
votes
1
answer
20
views
Balanced Directed Graph Realization
I have a list of integers: each integer represents a node in a directed graph, and the value of the integer is both the desired indegree and outdegree of said node.
Some research suggests that this is ...
- 103
1
vote
1
answer
130
views
Chistofides' algorithm for the traveling salesman problem with relaxed triangle inequality
It is known that Christofides’ algorithm returns a 3/2-approximation for the traveling salesman problem given a complete graph $G$ such that distances obey the triangle inequality. Suppose that we ...
1
vote
0
answers
106
views
Preference based assignment problem to maximize utility
I am studying an optimization problem which can be recast as an LP I have described below. I wish to understand the structure of optimizers of the original problem by studying the optimizers of the LP....
- 11
0
votes
0
answers
73
views
How to divide weakly connected graph into "k" weakly connected subgraphs (using e.g. networkx)?
I have a weakly-connected weighted digraph $G$, and I'd like to divide it into $k$ weakly connected subgraphs $G_k$ each with approximate equal total weight $w_{T_k}$ ($w_{T_k}$ = sum of weights of ...
- 11
0
votes
0
answers
49
views
How to efficiently recalculate iterative weighted center
I'm trying to write a gradient ascent approach to divide all points on a polygon into two sets via a continuous line (something like the below, where our polygon is a circle and we partition such that ...
- 101
1
vote
1
answer
140
views
Find a weight threshold for edges for maximum number of connected components in a graph
So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or ...
- 25
1
vote
1
answer
15
views
Defining multi commodity flows as polytopes
In a multi commodity network, we define a demand to be a vector $d \in \mathbb{R}^{k}$, where $k$ is the number of pairs of sinks. That is, $k = \binom{S}{2}$, where $S$ is the set of sinks (aka ...
- 334
2
votes
1
answer
49
views
Is it possible to have a 2 by 2 rigid framework without having a corresponding connected bipartite graph?
According to the theorem(see reference) on the rigidity of frameworks:
A rectangular framework is rigid if and only if its associated bipartite graph is connected.
Now consider the case for a 2-by-2 ...
- 143
-1
votes
1
answer
29
views
Half Clique Property question
Hey I had this question and am stuck on part (b).
I don't see how its possible to find a graph with 7 vertices and 15 edges that does not have the half-clique problem. If there is a way, could someone ...
0
votes
0
answers
29
views
A directed graph in which each vertex has out degree atmost one ,then the graph contains either a single sink vertex or a single cycle
I am solving a problem where I got an observation that, the vertices of the graph has an outdegree of atmost one, but My questions is using this observation ,Can it be proved that graph has either a ...
- 13
1
vote
1
answer
49
views
Is there a good platform/software/language to make a computer analyze this optimization problem?
I am trying to optimize a building layout in a game, and it seems like the problem could be solved by a computer much quicker than by my own trial and error. However, I only have a cursory ...
- 111
1
vote
1
answer
59
views
How to determine if two vertices (or two edges) fall on a cycle of a specific length?
A walk is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct.
A cycle in a graph is a non-empty trail in which only the first ...
- 303
1
vote
0
answers
83
views
Louvain algorithm: self-loop weight calculations for super-node
In the Louvain algorithm, a super node is created in the second phase with self-loops from the sum of intra-community edges. According to the original paper and the lecture CS224W, self-loop edges are ...
- 11
2
votes
1
answer
77
views
Is the clique decision problem in co-NP?
Is the clique decision problem in co-NP?
Definitions:
"In the clique decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph ...
- 23
0
votes
0
answers
23
views
The conjuction of two graphs is connected iff one of them has an odd cycle
The following is a dublicate of the question presented here:
Let $G$ and $H$ be simple graphs. We build the graph $G\times H$ such that every vertex $(u,v) \in V(G\times H)$ is an ordered pair of one ...
1
vote
1
answer
47
views
Given a bipartite graph G and an integer l, how many edge subsets of size l are there such that the degree of each vertex is odd?
Given a bipartite graph $G=(V,E)$ and an integer $l$, how many edge subsets ($E'\subseteq E$) of size $l$ are there such that the degree of each vertex in the resulting subgraph $G'=(V,E')$ is odd?
I ...
- 133
2
votes
0
answers
84
views
Finding a maximum induced DAG in a digraph
I have a digraph D on n vertices formed in the following manner:
I start with k ordered (not sorted) lists of integers, with each integer from 1-n in at least one list. Integers do not show up more ...
- 71
0
votes
0
answers
63
views
What algorithm will convert a regex into a tree of predictable size?
How do we quantify the size of a regular expression?
A problem in computer science which sometimes arises is converting a regular expression into a tree.
What rules can we use to ensure that the tree ...
0
votes
1
answer
64
views
How to recover path, given unordered set of non-repeating arcs for directed graph?
Let's say I have a set of non-repeating arcs, e.g. (0,1), (3,0), (0,3), (1,2), (2,3), ("set" because they don't repeat).
Here's an example of a graph for ...
- 11
0
votes
1
answer
30
views
How reversing the edges of the graph not altering the original conditions?
I was going through the main idea of solution to this problem. I could not assimilate the idea of reversing the edges and then using that graph to check if node 1 is reachable from all others.
How ...
- 13
4
votes
1
answer
182
views
Algorithm to find a set of nodes with a smaller set of neighbours in a bipartite graph
Given a bipartite graph, find a set of nodes on one side that has greater cardinality than the set of its neighbours on the other side.
This is a conceptually simple problem, but I suspect it is ...
- 297