# 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
Filter by
Sorted by
Tagged with
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
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, ...
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 ...
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
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
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 ...
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 ...
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 ...
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 ...
1 vote
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
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 ...
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 ...
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 ...
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
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 ...
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
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 ...
1 vote
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
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
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
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
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
93 views

• 133
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
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 ...
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 ...