Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
1answer
10 views

Finding topologically sorted connected components in directed acyclic graph

I am aware topological sort and connected component algorithms are very related, but I have been looking for an algorithm to simultaneously compute both, rather than one after the other, and I am ...
1
vote
1answer
30 views

Devising a way to spot a contradiction given a set of statements using graphs

If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John. Would there be a way to figure out that there is a contradiction ...
4
votes
1answer
42 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
1
vote
1answer
22 views

A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher

Referring to these notes regarding DFS - Click Here They refer to the following claim that follows Definition 0.2. as observation: A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and ...
1
vote
2answers
59 views

An algorithm to maximize the number of parallel tasks

I have a set of compute tasks I want to schedule, these tasks have dependencies and a task may not be executed until all its dependencies are executed. The problem can be represented as a directed ...
0
votes
0answers
31 views

Show that for each even n, there exists a graph with n vertices, such that the 2-approx VC alg returns a VC which is exactly twice the Minimum-VC

Question: Show that for each even n, there exists a graph with n vertices, such that the ALG(algorithm) returns a vertex cover which is exactly twice the size of minimum vertex cover. Define ALG: ...
2
votes
0answers
9 views

Graph Layout: Fixed node locations

I'm aware of a large amount of literature on the problem of graph layout. Usually this involves taking a list of nodes and edges, and choosing locations and paths for both respectively. Are there any ...
3
votes
1answer
64 views

3SAT instance with EXACTLY 3 instances of each literal

I'm trying to solve a question which requires me to prove that an instance of 3SAT where each literal appears in exactly 3 clauses (positive and negative appearances combined) and each clause ...
4
votes
2answers
517 views

Prove that the total distance is minimised (when travelling across the longest path)

Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have ...
0
votes
0answers
25 views

What do we mean by “spectral domain” in the context of graphs?

What do we mean by the spectral domain in the context of graphs? For example, I have heard that graph convolutions are easiest to define in the spectral domain. When it comes to the word "spectral", I ...
2
votes
0answers
6 views

Motivation behind the definition of order-$k$ (edge) expansion?

I'm trying to understand the motivation behind the idea of order-$k$ (edge) expansion for partitions of a graph, defined below: For simplicity, let's focus on $d$-regular graphs. The definitions I'm ...
0
votes
0answers
33 views

Correctness of algorithm and its complexity

I am trying to solve problem of generation of so called activity-on-edge (activity-on-arc) network graph given based on given activity-on-node network graph. So, I found this paper proposing an ...
0
votes
0answers
21 views

What is the complexity of an algorithm that ensures 2 “aggregate graph properties”?

Background Let $G(V,E)$ be a graph. Let $S$ be the set of all combinations of $|V|$ edges. Let $A$ & $B$ be two subsets of $S$, where: each subset is a collection of all elements of $S$ that ...
1
vote
1answer
20 views

Good resources for Graph labelling

I'm searching for good resources on different graph labelling, especially Graceful, Antimagic and Antibandwidth Labelling. Could anyone please help me with that? It will be very much appreciated. ...
2
votes
2answers
115 views

Isomorphisms between regular graphs of same degree

Are all $n$-vertex regular graphs of degree $d$ isomorphic? Can someone provide an example of two non-isomorphic graphs $G_1$ and $G_2$ which are both regular with degree $d$ and have the same number ...
3
votes
2answers
45 views

How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs

The Bellman-Ford algorithm on a graph with $n$ vertices, normally includes a loop executed $n-1$ times. Each time through the loop we iterate over the list of edges $(u,v)$ and relax $v$. Note that ...
1
vote
1answer
61 views

Find total count of all paths starting from a fixed vertex to all other vertexes of the graph

Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e. $$ \text{#(paths from 1 to 2)}+\text{#(...
1
vote
1answer
34 views

residual graph and augmenting path in max flow

I thought I understood max flow perfectly until I got to the exam and we got this. I know how to compute a maximum flow by means of the Ford-Fulkerson algorithm, specify the residual network and ...
1
vote
1answer
47 views

Generating project network graph

I had a problem of generating project network graph (like there and there) from list of activities and their dependencies. Informal description: Every activity is represented as edge of directed ...
0
votes
0answers
23 views

Find no of acyclic paths of any length in a directed graph from a single source given that every node has at most 4 in/out degree

let A,B,C be nodes of directed graph with edges A->B,B->A,A->C,C->A,B->C,C->B then no of paths will be 5 that is A,A->B,A->C,A->B->C,A->C->B If i apply dfs and increase counter for every node i ...
0
votes
1answer
14 views

What does flow denotes in the minimum-cost network?

What is flow in context of minimum-cost network? I know that a minimum cost network is a directed graph G={V,E}, where each edge has a cost and capacity value. The problem is to find best 'path' to ...
1
vote
0answers
26 views

Optimal improper vertex-coloring of graph with weighted edges

I have an undirected graph with weighted edges. I want to color the vertices with a given $k$ colors. Let's assume there is no proper coloring with $k$ colors such that adjacent nodes will always have ...
0
votes
0answers
26 views

Find maximal matching in tree in $O\left(\frac{n}{\log n}\right)$

As any tree can be described as a binary sequence ($i$-th bit is 0 if the edge goes down and 1 otherwise, every edge is travelled twice $-$ up and down, so such sequence's length is $2 |V| - 2$), any ...
0
votes
1answer
36 views

Determine endpoint of a graph given as a list of nodes + direct successors and predecessors

EDIT @20190313 I can rephrase my question a follows : I am given everyday a non weakly-connected directed graph by its so-called adjacency list representation -- nodes are stored as objects, and ...
1
vote
1answer
12 views

Simple algorithm to generate a linear extension from partial order set

I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.
2
votes
1answer
37 views

All pair shortest path in a tripartite graph

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
3
votes
1answer
25 views

Longest simple walk below a certain weight

Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight < $w$ that visits as many nodes as possible. Currently, I have a recursive ...
-1
votes
0answers
23 views

Formula for maximum matching in bipartite graph

Let $G = (U, W, E)$ be a bipartite graph. Show that $\alpha'(G) = \min(|U| - |S| + |N(S)|)$, where $S$ ranges over all subsets of $U$, $\alpha'(G$) is the size of maximum matching of $G$, and $N(S)$ ...
-2
votes
0answers
26 views

Maximum weight collection of disjoint directed cycles

Can someone help me with this task: Let $G = (V,E,w)$ be a directed graph with positive edge weight function $w$. Give an efficient algorithm to find a collection of vertex-disjoint cycles in $G$ ...
0
votes
1answer
28 views

Dijkstra complexity analysis using adjacency list and priority queue?

I just got to look at the Implementation of Dijkstra using adjacency list and priority queue. The time complexity is $O(E\log V +V)$, I tried looking for the proof but couldn't find one. Any help will ...
2
votes
2answers
55 views

Floyd Warshall's All pair shortest path problem does not evaluate all possible paths

We know that the FW all pair shortest path is a Dynamic Programming (DP) approach to solving the problem. Being a DP, it smartly evaluates all possible options before deciding the final option at each ...
0
votes
0answers
31 views

Clique number of a graph given its order and average degree

Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree. Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$. Find the ...
5
votes
1answer
126 views

How does treewidth behave under graph minor operations?

It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G. Minors of a graph are created through the ...
5
votes
1answer
60 views

Find all edges in a tree whose removal doesn't separate color classes

Given a tree of $N$ vertices, each colored in one of the colors $1,\dots,N$. Let’s call an edge a separator if when the edge is removed from the tree, all vertices of each color stay connected. ...
2
votes
1answer
33 views

Name of a tree with arbitrary number of branches at each fork point?

A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes. How do you call a rooted tree if the number of branches per ...
1
vote
1answer
30 views

Path of maximum value with bounded cost in DAG

Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is ...
1
vote
1answer
46 views

Shortest path from source to all vertices, but with some wildcards

Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer). You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated ...
0
votes
0answers
21 views

If you can have cyclic base types, or if they need to be infinite types

I am confused how to properly think about classes of classes. Basically, you can have a dog "filo" which is an instance of the dog "class". But the dog class is itself not an instanceof of "animal", ...
0
votes
0answers
12 views

Distributed maximal matching from vertex coloring

How to use a $\Delta +1$ vertex coloring to find a maximal matching in a distributed graph.
1
vote
1answer
35 views

Reduction Vertex cover into Dominating Set

I have a question to the reduction from Vertex Cover into Dominating Set. So my lecture says if I have a undirected Graph $G = (V,E)$ where $S \subseteq V$ is a vertex cover. Then we construct a new ...
4
votes
2answers
79 views

Add lines to star with fixed coordinates maximizing smallest angle

I have the following problem: There are existing stars (as in graph-theory stars) with a fixed representation in a 2D coordinate space, meaning that angles between the edges are not allowed to change....
3
votes
1answer
65 views

Is maximum edge-weighted triangle-free graph NP-hard?

Given a graph $G$ with weights $w_e$ on the edges, choose a subset $S$ of the ''edges'' such that $S$ doesn't contain any 3-cycles, maximizing $\sum_{e\in S} w_e$. Is this problem NP-hard? I thought ...
1
vote
1answer
30 views

Approach to find minimum set in one table consisting of all items in second table

wondering if you can help me with the following problem. I have one table consisting of items in each person's bag: ...
3
votes
1answer
49 views

Find path from A to B which length ≈ L

I have an undirected weighted graph. I want to find the path from A to B which length (sum of the weights) is as close as possible to a specific value "L". To do that, I have been doing a DFS to ...
0
votes
1answer
36 views

set cover to edge cover

I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I ...
1
vote
1answer
51 views

Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?

John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his errands where he visits each of k different shop in order. However, each ...
1
vote
1answer
48 views

Partitioning vertices in a bipartite graph according to minimum vertex covers

How to solve this problem? A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover ...
0
votes
0answers
18 views

Finding subgraph in multigraph using deeplearning

I have big multigraph each node represent entity with 0..n attributes(e.g. name, address, salary). My problem is: I will get for example 10 subgraph selected from user and these subgraphs represent ...
1
vote
0answers
25 views

Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$

I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows: Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a ...
1
vote
0answers
20 views

Maximum subset of connected edges

I have a graph $G$ with $m$ vertices $V$ and $n$ edges $E$. $G$ is weighted, directed, and cyclic. I want to select heaviest $k$ edges from $E$ such that all of the edges form a connected, undirected ...