Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

Filter by
Sorted by
Tagged with
4
votes
0answers
22 views

MST with possibly minimal diameter

I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
1
vote
0answers
22 views

Is dijkstra's algorithm fastest possible algorithm for undirected graph with no additional data?

there are many similar questions, but I haven't found direct answer to this question. Consider I have undirected, weighted graph with positive weights, no additional data - hence no heuristic (so it ...
0
votes
0answers
13 views

Connecting islands to the mainland via flood fill

Say I have a large area filled using floodfill: Where the area in white has been flooded, and all other ares are not connected. I would like to "bridge" these islands to the main area in white, but ...
0
votes
1answer
23 views

Why do we do topological sorting to find shortest or longest path in weighted DAG?

I was wondering why do we need to do the topological sort before performing relaxing of edges. Wouldn't it'd be better if we do : if starting vertex is "s" ...
-2
votes
0answers
22 views

No. of distinct path between two vertices of a complete graph

Let $K_n$ denote the complete graph on $n$ vertices, where $n\ge3$, and let $u,v,w$ be three distinct vertices of $K_n$. Determine the number of distinct paths from $u$ to $v$ that do not contain the ...
1
vote
0answers
6 views

Node ordering at contraction hierarchy of biDirectional Dijkstra

I try to understand the node ordering at contraction hierarchy. To me, ordering and contracting node looks impossible because when contracting a node, then it influence the other node. Therefore, it ...
0
votes
0answers
24 views

Least-weight path in a DAG--why not just use Dijkstra?

I have an assignment to find the least-weight path in a DAG from a source to a target. But the class has already discussed Dijkstra's algorithm, so I'm wondering, why not just use that? It seems too ...
1
vote
0answers
17 views

Maximum edge-disjoint flow

Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such ...
1
vote
1answer
40 views

Use 2SAT to show that an implication graphs must have a cycle if it's not satisfiable

Using 2SAT and implication graphs, how could I prove the following properties of implication graphs: Suppose there is a directed path between literals l1 and l2 in G_φ. Then there is also a directed ...
2
votes
1answer
80 views

Find longest path by number of edges, excluding cycles

I need to analyse a directed graph (not a DAG) but I don't know the name of the algorithm I would need to use. The graph has many cycles. My desired behaviour is: given a graph source and graph sink, ...
0
votes
1answer
31 views

Perfect Matching in Bipartite Graph with mutually exclusive edges

Problem I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive. Example Left vertices: $a,b,c$ Right vertices: $x,y,z$ Edges: $(a,x),(a,y),(b,z),(c,y)...
2
votes
1answer
75 views

Existence of graph spanners

An (unweighted) $k$-spanner of a graph $G$ is a subset of edges $S$ such that the distance between any two vertices of $G$ when using only edges in $S$ is at most $k$ times the distance in graph $G$. ...
2
votes
1answer
25 views

Definition of 2-CNF (a.k.a Krom) formula

In my lecturer's notes, the following definition for a 2-CNF wff is given: A 2-CNF formula, or Krom formula is a CNF formula F such that every clause has at most two literals. However, there is ...
1
vote
0answers
20 views

Minimum basis for the nullspace of sparse matrices

Let $A\in\mathbb{F}_2^{m\times n}$ and denote its nullspace as $V=\{x\in\mathbb{F}_2^m:xA=0\}$. The weight of a basis $B=\{b_1,\dots,b_l\}$ for $V$ is the total weight of vectors in the basis, denoted ...
0
votes
1answer
31 views

generate all unlabelled trees up to size n

Who has published an answer to these problems? An isomorphism signature is a function s on the set of all trees with the property that s(T1) = s(T2) if and only if T1 and T2 are isomorphic. Define ...
-3
votes
0answers
45 views

How to find the fartest distance from a graph?

Pak Dengklek is the best scientist in Singanesia. Right now he was about to try his latest invention, the teleportation machine! He wants to try the machine to move things as far as possible. ...
1
vote
2answers
73 views

Iterative Depth First Search for cycle detection on directed graphs

I found this pseudocode on Wikipedia, and looks very elegant and intuitive: ...
0
votes
1answer
35 views

Efficiently remove nodes from a connected graph

Suppose you have a connected graph and want to remove k nodes such that the result is still connected. How could you do this efficiently? It occurs to me that you ...
4
votes
2answers
57 views

Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG

We are given directed weighted graph with edges having strictly positive weight(>0) with possibly some cycles with $N$ nodes and $M$ edges. Let's observe all the shortest paths from $1$ to $N$ in this ...
1
vote
2answers
36 views

Articulation points (or cut vertices), but only subset of vertices need to be connected

I know we can find all articulation points efficiently in a graph using DFS. But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is ...
0
votes
1answer
63 views

CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm

I'm trying to better understand Question 24.3-4 From CLRS below: Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm. The program produces $v.d$ and $v.\pi$ for ...
2
votes
2answers
289 views

Proving correctness and optimality of a greedy algorithm

Here is a (slightly abridged) problem from Kleinberg and Tardos: Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated ...
3
votes
0answers
35 views

Random linear arrangement of a tree with constrained edge lengths

Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the ...
1
vote
0answers
32 views

small world networks properties

Small-world networks have two properties: clustering coefficient and average node-to-node distance my questions are: 1- Can a disconnected graph ( which may include multiple connected graphs) hold a ...
2
votes
1answer
60 views

In a DAG, finding the path with the highest score

Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a ...
2
votes
1answer
34 views

Number of `m` length walks from a vertice with steps in [1, s]

The problem is stated as the following: We are given a grid graph $G$ of $N \times N$, represented by a series of strings that describe vertices s.t. $L$ is the vertice we're interested in $P$ are ...
23
votes
4answers
4k views

Assuming P = NP, how would one solve the graph coloring problem in polynomial time?

Assuming we have $\sf P = NP$, how would I show how to solve the graph coloring problem in polynomial time? Given a graph $G = (V,E)$, find a valid coloring $\chi(G) : V \to \{1,2,\cdots,k\}$ for ...
3
votes
1answer
38 views

How to best calculate the best possible path with weights

Given a set of nodes, with connections in certain directions (see image), what is the most coins you can collect between the first and last given node. Not all rooms have coins, and we want to output ...
3
votes
1answer
242 views

Construct a DAG from given multiple topological orderings

I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as ...
1
vote
2answers
130 views

Graph with exactly 2 Minimum Spanning Trees

Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs). Given this condition stipulated, prove that any cycle formed by all the edges in both the MSTs (i.e., the union of the edges in ...
2
votes
1answer
45 views

Finding all “basic” cycles in an undirected graph?

Say you have a graph like a — b — c | | | e — f — g and you would like to find the cycles c1, {a,b,f,e}, and c2, {b, c, g, f}, but not c3, {a, b, c, g, f, e},...
2
votes
0answers
41 views

Efficient algorithm for enumerating minimal vertex separators

Let $G$ be a non-empty connected undirected graph, which is not a complete graph. We treat $G$ as a set, writing $G \setminus \{v\}$ for vertices $v$, etc; subsets of $G$ should be understood as ...
1
vote
0answers
29 views

A state space for river crossing puzzle

I am solving the river crossing puzzle with 6 participants. You must transfer all the people across the river in this flash game respecting the following rules: The ferry can carry no more than 2 ...
3
votes
1answer
44 views

how to generate all spanning trees from one spanning tree

If I have one spanning tree from a connected and undirected graph, how can I generate all other spanning trees of this graph by modifying this spanning tree one edge at a time? All intermediates must ...
1
vote
1answer
61 views

Some paths in directed graph

Given directed graph $G = \langle V, E \rangle$, such that some vertices are red, and some vertices are black, and some edges are blue or green, decide for all vertices $v \in V$ if there is path from ...
1
vote
1answer
28 views

A pathfinding algorithm for graphs in which arc weights can change over time

So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction. Here's the situation, I have a weighted undirected ...
1
vote
0answers
18 views

Restoring the minimum vertex cover on bipartite graph from the maximum matching

I had to solve a problem on finding the minimum vertex cover on a bipartite graph, and I used the Kőnig's theorem and reduced it to maximum matching problem on bipartite graph, which is easily ...
1
vote
0answers
22 views

No integrality gap between maximum weight independent set and its LP-Clique relaxation

I am looking for classes of undirected graphs $G=(V,E)$ for which the maximum weight independent set problem and its LP-clique relaxation have the same solution for any weights $w:V\to\mathbb{R}_{>...
0
votes
1answer
24 views

Find bipartial subgraph such that number of edges is maximum and sum of edge lengths is maximum

Let there be graph $G = (V, E)$. $G$ has neither loops nor parallel arcs. $V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$ For simplicity's sake, let's consider $G$ is ...
0
votes
1answer
26 views

Find bipartial subgraph such that mean square deviation of edge lengths is minimum

Let there be graph $G = (V, \, E)$. $G$ has neither loops nor parallel arcs. $V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$ For simplicity's sake, let's consider $G$ ...
0
votes
1answer
28 views

Find bipartial subgraph such that sum of edge lengths is maximum

Let there be graph $G = (V, E)$. $G$ has neither loops nor parallel arcs. $V = A \cup B, \, A \neq \emptyset, \, B \neq \emptyset, A \cap B = \emptyset$ For simplicity's sake, let's consider $G$ is ...
3
votes
1answer
49 views

Minimize function on permutations

Problem: Consider $[k] = \{ 1, 2, \dots, k \}$ and function (of two arguments) $f: [k]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in [k]^{2}$ (all ordered pairs of numbers from $[k]$...
0
votes
0answers
34 views

Routing algorithm for public transport without timetable

I'm trying to implement a simplified version of RAPTOR algorithm for journey planning. Raptor tries to find fastest route based on the arrival and departure time in each stop. There is a concept of a ...
1
vote
1answer
43 views

Solving a modified Travelling Salesman Problem(TSP)

I am trying to solve a modified version of the TSP. In my version, multiple visits to a city are allowed, as long as the path is the shortest, and also, only subset of the cities are compulsory to ...
-1
votes
0answers
11 views

Coloring k-Uniform hypergraph with k colors

If I want to color a k-uniform hypergraph with k colors. I think it will be hard to color it with k colors such that each hyperedge has k distinct colors. But what is the corresponding problem to ...
0
votes
0answers
14 views

Creating a hierarchical graph

To test some procedures, I am trying to create "toy models" of graphs with communities present. I want to create two distinct types of graphs: "flat" and hierarchical. Hierarchical graphs should ...
1
vote
2answers
62 views

Are all calculations graphs?

I've come to understand that programs are graphs on several layers. Call-graphs are an example that come to mind without a textbook handy, another is mutation flow. So I do understand that code is ...
6
votes
1answer
75 views

Selecting vertices in a graph in an order to keep border vertices as few as possible

I am given an undirected graph. Initially all vertices are white. I need to color them black in such an order that the maximum number of vertices which are on the border between black and white ...
3
votes
0answers
33 views

Algorithm for undirected projective dependency parsing

I am looking for an algorithm that will get an optimal projective undirected dependency parse. That is, given the sentence 'Mary does love John', and an edge-weight function $f$ (that is, a function ...
3
votes
1answer
45 views

Longest path length in an undirected tree, can we prove this algorithm is correct (which it is)?

Hello I solved this leetcode https://leetcode.com/problems/tree-diameter/ question reserved for people who pay the subscription. The question: Given an undirected tree (tree is not disjoint), ...

1
2 3 4 5
71