The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [graph-theory]

Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

Filter by
Sorted by
Tagged with
0
votes
1answer
37 views

Minimum Clique Cover - Mixed Integer Programming

I have a general (undirected) graph with a set of nodes, a set of edges, and a weight for each edge. I want to find a minimum clique cover of the graph, that is, a partition of the graph into the ...
-1
votes
0answers
20 views

Show that the de Bruijn graph G6,10 is strongly connected and balanced

I've been given this question and have absolutely no idea how to answer it. I can't even find the G6,10 graph nor have I been given it.
1
vote
1answer
21 views

How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?

I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is ...
0
votes
1answer
41 views

binomial tree number of nodes

Does anybody knows that how we can assign number to nodes for binomial tree . I mean how we can represent the number of nodes by array? please give me hint I am really confused .
2
votes
1answer
22 views

Existence of d-regular subgraphs in a k-regular graph

The claim is as follows: Let's say we have a $k$-regular simple undirected graph $G$ on $n$ vertices. Then, does $G$ then always have a $d$-factor for all $d$ satisfying $1 \le d \lt k$ and $dn$ being ...
1
vote
1answer
49 views

How to encode reachability in a graph with walls as a SAT problem

Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we ...
2
votes
1answer
50 views

Matching each unique pokemon with a unique move

Background: There are 832 unique Pokemon in the Pokemon universe, and There are 728 fighting moves that the Pokemon can collectively learn. No Pokemon can learn to do every fighting move, and some ...
0
votes
1answer
38 views

What is minimum cost perfect matching problem for general graph?

It does make sense when we talk about perfect matching in bipartite graphs because there are two sets of points, for example, one set may be jobs and other set may contain different machines. But when ...
-1
votes
0answers
47 views

intervals in geometrical points in 2D space

Can anyone help me and provide me a link for learning geometrical points in 2d space which is related to algorithmic course ? this is the question but as I searched youtube there should be an equation ...
3
votes
0answers
77 views

What is the exact time complexity of randomized Kuhn's algorithm?

Please, read the whole question before answering, the exact details of the implementation are important. Suppose that you want to find largest cardinality bipartite matching in bipartite graph with $...
4
votes
2answers
126 views

How to evaluate all possible groups of adjacent tiles in 2D array?

I'm working on a tile based game idea in Javascript. It's a math puzzle game where players move around tiles with numbers on them, and the goal is to connect groups of tiles that have a sum of certain ...
0
votes
0answers
67 views

FInd a graph on a vertex set similar to another graph

I am looking for a possible algorithmic solution to this problem, but I can't figure out any. Let's say I have a weighted graph (call it G); each vertex on this graph represents a point in a plane, ...
1
vote
1answer
22 views

Directed graph reachability

Given a directed graph G(V,E) and a node s, how do we determine what nodes are reachable from s? Do I need simple traversal algorithms or do I need to look at Tarjan's algorithm?
-1
votes
1answer
57 views

question about algorithm

as you know we have equivalent condition for graphs so I want to ask a very basic question and please help me what is exactly w1(e1) and w1(e2) and w2(e1) and w2(e1) ? If e1 means path from A to B so ...
1
vote
1answer
52 views

Give an example of a connected graph where α(G) =100 and β(G) = 200

So I need to find a form of a graph such that its vertex cover is twice that of its matching, but I am running into problems brainstorming, I know K3 is of this form, but not one at such a magnitude.
0
votes
1answer
27 views

Strongly connected graph proof

Here I have a proof related to strongly connected graph from Algorithms book. However, when I run DFS on the following 2 strongrly connected graph, I get different result than the proof. According ...
1
vote
1answer
51 views

The optimized numbers of variables and clauses to encode a graph coloring problem in CNF

Problem Statement Given a finite graph $G = \langle V, E\rangle$, consisting of vertice set $V$ and edge set $E$, and a finite set of colors $C$, a problem instance of graph coloring is to assign ...
1
vote
1answer
29 views

Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs? Example 1: set(a, b, c, d, e) pairs(a>b, ce) Example 2: set(a, b, c, d, e) pairs(a>b, d>b, c>d, d>e)...
0
votes
1answer
25 views

Efficient algorithm for assigning weights to nodes in graph to create steady state flow

I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem: Definitions: Given a graph $(V,E)$, with non-negative weights ...
1
vote
0answers
36 views

Min-Ones-2-SAT getting to vertex cover

In the Min-Ones-2-SAT problem, we are given a 2-CNF formula φ and an integer k, and the objective is to decide whether there exists a satisfying assignment for φ with at most k variables set to true....
2
votes
0answers
22 views

Computing similarity of two graphs with partially overlapping sets of nodes

Consider two graphs $G_1 = (E_1, V_1) $ and $G_2 = (E_2, V_2)$ with their associated sets of edges $E$ and nodes $V$. I'm familiar with concepts such as edit distance for computing the similarity/...
0
votes
0answers
27 views

Minimise the maximum degree of a vertex in a connected graph

Given $N$ vertices and $M$ edges, how to create a connected graph so that I can minimize the maximum degree of every vertex. A vertex can have at most degree $N$ (self loop and other $N-1$ edges). ...
1
vote
0answers
35 views

C++ finding the shortest path, reducing time complexity, dijkstra v Floyd Warshall Algorithm?

I have an algorithm that I am performing on a graph and I am looking to do an analysis of how to speed it up and would appreciate any comments. The algorithm iterates over every edge in the graph. ...
1
vote
0answers
68 views

Minimum path cover in a DAG

Given a directed acyclic graph $G=(V,A)$ and a set $A'$ of $A$. It is well known that searching for a minimum number of vertex-disjoint paths that cover all the vertices of $G$ can be solved in ...
2
votes
1answer
28 views

Finding partition with maximum number of edges between sets

Given a graph (say in adjacency list form), is there an algorithm to find a partition of vertices such that the number of edges between the two sets of the partition is the maximum possible? For ...
4
votes
0answers
125 views

Is this equivalent to any famous NP-complete problem?

Given the following problem. Given an $n\times n$ matrix $A := \{a_{ij}\}$. Find an $n\times n$ matrix $X := \{x_{ij}\}$, where $x_{ij} \in \{-1, 1\}$ for $i, j \in [n]$, that minimizes the ...
3
votes
1answer
69 views

Algorithm to find a simple path with maximum weight less than a constant in DAG

Given a weighted directed acyclic graph $G=(V,E,W)$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should ...
4
votes
1answer
43 views

How to find all the edges shared by all diametral paths of a tree?

A diametral path in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $n$ nodes, I would like to find the set of edges (possibly empty) which are ...
0
votes
1answer
53 views

Longest path in a directed acyclic graph with constraints

Given a directed weighted acyclic graph G=(V,D,W) and a subset of edges D' of D. The problem is to find the longest path in G that passes by exactly one edge of D'. What is the complexity of this ...
3
votes
0answers
35 views

What does “edge-connected components of graph” means in paper PUNCH?

I'm recently trying to study the paper "Graph Partitioning with Natural Cuts": https://www.microsoft.com/en-us/research/wp-content/uploads/2010/12/punchTR.pdf There is a term edge-connected ...
0
votes
0answers
13 views

APSP on GPGPU with paths reconstruction

There is a huge number of works on efficient solution of all-pairs shortest paths (APSP) by using GPGPU. But the main goal of these works is to compute the length of the shortest path. Are there exist ...
0
votes
2answers
33 views

Louvain algorithm: self-loop weight is double?

In the 2nd phase of the Louvain algorithm, self-loops are given by the sum of all the intra-community weights. I'm wondering from their own figure, why all of the self-loops seem to have ...
2
votes
1answer
47 views

Like transitive reduction, but removing vertices rather than edges?

Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in ...
2
votes
1answer
48 views

Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”

In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality. In Fig. 1.3, the author says a black colored leaf ...
2
votes
0answers
25 views

Why is the distribution of the clustering coefficient of a random network independent of degree?

I was reading about clustering coefficient distribution, and it seems that it is independent of node degree for the case of random networks, or even scale-free networks. I'm wondering why this is the ...
3
votes
1answer
59 views

k-disjoint pair paths where any source can pair with any sink

I have a question regarding a problem I'm working on. The problem is given an MxN grid with k sources and sinks, find non intersecting paths (vertex disjoint) such that all sources are paired with a ...
1
vote
1answer
22 views

Number of induced paths in an interval graph

Let $G$ be an interval graph. For any two vertices $u,v$ in $G$, how many induced paths are between them in $G$? Is it polynomial in terms of the number of vertices in $G$?
0
votes
0answers
70 views

A question about Fleury's algorithm

The following is the Problem 1.4 in [1]: Finding an Eulerian path. Show that if a connected graph has two vertices of odd degree and we start at one of them, Fleury's algorithm will produce an ...
0
votes
0answers
26 views

Divide directed weighted graph into two parts

I have a directed, weighted graph $G = (E,V)$. For example, one might be $|E| = 74000, |G| = 725$. I want to divide this graph into two parts/clusters/communities, taking the edge weights into ...
1
vote
1answer
46 views

Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes

I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of ...
1
vote
1answer
33 views

Ford Fulkerson maximum flow for all vertices

Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, ...
2
votes
1answer
20 views

Network density vs connectivity

I was reading this paper where they mention about undirected networks: "The total connectivity of a network is defined as $C=\frac{E}{N(N-1)}$ where E is the number of edges and N the total ...
0
votes
0answers
19 views

Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
0
votes
0answers
19 views

What is the approximation for odd cycle transversal?

What is the best approximation for odd cycle transversal? (on general graphs) Sorry if this is easily found everything I found about odd cycles is about paramaterized complexity and kernels
-1
votes
1answer
53 views

Strongly connected components in a directed graph

Let $G$ be an arbitrary directed graph. Does $G$ always have the same strongly connected components on $G$ as on $G^*$? Here, $G^*$ is the inverted graph of $G$ (i.e., $(u,v)\in E \rightarrow (v,u) \...
3
votes
0answers
27 views

Bounded treewidth implies bounded clique-width

We have a graph G of treewidth $\operatorname{tw}(G)\leq k$, for some $k\in\mathbb{N}$. I've seen a claim that that implies that the clique-width of the same graph is at most $k \cdot 2^k$. This ...
0
votes
0answers
9 views

Graph with arboricity a, all verteces are marked active

So I came across this problem that I would like help solving/explaining: We have a graph with arboricity a (can be partitioned to a min of a trees). We run the following algorithm on the graph: - All ...
2
votes
2answers
83 views

For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Traditionally, the traveling salesman problem has you visit a city at least once and at most once. However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
1
vote
2answers
58 views

Verifying connectivity of a graph in O(n^2)

I trying to solve the following problem in $O(n^2)$: We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph ...
3
votes
1answer
162 views

Merging nodes of a DAG

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them. After each merge operation, ...