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

learn more… | top users | synonyms

1
vote
1answer
71 views

Reduce Min-Cut to 0/1 Integer Program

Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by: $$ w(U,U^C) := \sum_{\{i,...
-2
votes
1answer
29 views

I can find in a graph a path between two input nodes to be exactly of length k

I have in input an undirected graph and two nodes. It is possible to find a path of lenght k, where k is a constant, in polynomial deterministic times? Or this problem belongs to NPC? Thanks
0
votes
0answers
8 views

What is a good way to move nodes into a block(also referred to as modules) for blockmodelling in graphs? [on hold]

I am working on a blockmodelling problem in a graph. The idea is that given a number N, I need to identify less than or equal to N blocks in the given graph, and nodes (or vertices ) are to be put in ...
-3
votes
0answers
49 views

Problems that are easy (e.g. in P) for straight cisgender people, but difficult (e.g., NP-hard) for general p?

Some classical problems are formulated in reference to people looking for a spouse, such as the marriage problem for straight people and the stable marriage problem for straight people. Both are in ...
0
votes
0answers
25 views

RMAT graph generator : Expected number of nodes with degree k?

I read this paper "R-MAT: A Recursive Model for Graph Mining" by Deepayan Chakrabarti ( In SDM. Vol. 4. 2004)(http://repository.cmu.edu/cgi/viewcontent.cgi?article=1541&context=compsci) from cmu ...
2
votes
1answer
274 views

Constructing orthogonal latin square Parker/Knuth method

I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal latin square. The ...
0
votes
1answer
61 views

I know the algorithms, but i still don't know how to approach the questions

I study Graphs Analysis by myself and i understood most of the material just fine. But, there is one huge problem with my approach that prevents me from solving tests. I don't know how to build new ...
0
votes
1answer
23 views

Should all internal node keys in B+ tree also be in the leaves?

I was reading about B+ tree insertion. The algorithm takes following form: Insert the new node as the leaf node. If the leaf node overflows, split the node and copy the middle element to the ...
0
votes
1answer
73 views

Understanding The Mapping Of Edges to Nodes In A Graph Theory Problem

I am really confused with this problem. Here's the problem: You have $N$ points numbered $1$ through $N$,inclusive, and $N$ arrows again numbered $1$ through $N$,inclusive. No two arrows start at ...
-3
votes
0answers
22 views

Find orientation graph of undirected graph that mimimizes absolute difference of in-degree and out degree

Here's a question from our uni's ICPC programming competition selections. I'm stating it in simpler terms here. Given an undirected graph, orient the edges of the graph in such a manner that the ...
-1
votes
0answers
25 views

Number of ways to join n distinct trees

I have been trying to solve a problem in which i need to join N distinct trees with disjoint set of nodes. After searching a lot I came across this formula but i am not able to understand it. Please ...
0
votes
0answers
13 views

Complex Network Betweenness Centrality algorithm [closed]

I am writing a function in VB.net to calculate the betweenness centrality given in this paper Betweenness Centrality in a directed network. I have written the following code to do so. Please aware ...
1
vote
2answers
41 views

Describe an algorithm for painting cards in the following game

It's my first question out here, so please don't judge me too strictly. I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) ...
3
votes
0answers
39 views

Qualifications for a problem to be solved as a single source shortest path problem

What are the pre-conditions for any problem X to be qualified for being solved in a single source shortest path problem (SSSP) setting? Lets, say we have a problem X. What should be the pre-...
1
vote
2answers
50 views

Can a graph have multiple identical elements?

Can a graph have multiple nodes that have the same value ? For instance, could a graph holding numbers have the same number present multiple times across the itself ? My current approach is to not ...
1
vote
1answer
45 views

Degree Reduction in Max Cut and Vertex Cover

I have been reading Alimonti and Kann's paper "Some APX-Completeness results for cubic graphs" and I don't understand why the degree-reduction gadgets for Max Cut and Min Vertex Cover have to be ...
0
votes
1answer
39 views

Rules to follow to create edges in graph

I am currently writing a graph object in Swift, I see that there are different types of graphs, some that are undirected and some that are directed. Here are my questions : Can a graph be both ...
2
votes
1answer
182 views

Converting a non-planar graph to planar

Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness. ...
0
votes
0answers
37 views

Compression of a complete Directed Acylcic Graph

Consider a DAG $g$ as a label $l$ with a list of sub-nodes $\bar{g}$: $g ::= l \enspace \bar{g}$ This is an "unfolded" representation of the DAG, i.e. it contains double entries, when two paths ...
3
votes
0answers
47 views

Orient edges in a mixed graph to minimize the critical path

A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way that no cycle is ...
2
votes
2answers
189 views

Find hamilton cycle in a directed graph reduced to sat problem

I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to ...
0
votes
0answers
32 views

Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
2
votes
0answers
23 views

Powerlaw graphs : Number of hubs and fraction of edges incident on them

As per the definition of power law, the fraction P(k) of nodes with k degree for large values of k , given by P(k) ~k ^-r . In this definition, the term large value is not clearly defined. Does ...
6
votes
2answers
576 views

Simple graph canonization algorithm

I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
-1
votes
1answer
44 views

What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other ...
7
votes
1answer
190 views

Binary rooted tree isomorphism

My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below: How many isomorphism classes of trees with n vertices are ...
3
votes
1answer
59 views

Automorphism of a Graph with a given Set of Permutations

Given a graph $H$. A set of permutations $\alpha$ which contains permutations of vertices of $H$. The permutation set $\alpha$ has automorphisms of subgraph $H_1, H_2,..... H_x$ where $x$ is the ...
2
votes
0answers
71 views

General Steiner Tree Variants

In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all ...
0
votes
1answer
9 views

What is the difference in 'logical array blocked' and array list B, and what do they represent?

In Johnson's 1975 Paper 'Finding All the Elementary Circuits of a Directed Graph', his psuedocode refers to two separate data structures, logical array blocked and list array B. What is the difference ...
23
votes
1answer
843 views

Is Logical Min-Cut NP-Complete?

Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
0
votes
1answer
36 views

Maximize cost in graph with variable costs

Consider the following problem. A prisoner eats once a day, he can either have a low, or a high calorie dish. In order to be allowed to eat the high calorie dish, he must not have eaten the previous ...
2
votes
1answer
37 views

Permutation on matrix to fill main diagonal with non-zero values

I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled ...
2
votes
1answer
31 views

Flaw in linear programming solution for multi-commodity flow problem?

The multi-commodity flow problem problem statement - wiki According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. ...
2
votes
2answers
81 views

How many $(x, y)$-paths of length $20$ are there, where $x$, $y$ adjacent vertices in cycle $C_5$?

As the title of the question suggests, let $x$ and $y$ be two adjacent vertices in the cycle $C_5$. How many $(x, y)$-paths of length $20$ are there?
2
votes
1answer
36 views

Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph?

I am working on a hex-based game in which I'm trying to pre-calculate pathfinding for a given map using the Floyd-Warshall algorithm. The map size is on the order of thousands of hexes (so maximum ...
3
votes
1answer
569 views

Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$. Now we decrease the weight by $k$ of ...
0
votes
0answers
12 views

Does marginalizing on a Bayesian network preserve its original independence assumptions?

I know that marginalizing over a Bayesian network causes changes to the graph (e.g. marginalizing node c in the V-structure given by $a \rightarrow c \leftarrow b$ results in $a$ and $b$ being ...
1
vote
0answers
20 views

Reconstructing a graph from set of sequences of edges

I have posted the same problem to Math Overflow, not sure where it fits better. I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, ...
1
vote
0answers
25 views

probability that the vertex set {1,…,k} is component of random graph

Consider a graph with vertices 1,...,n and suppose that each of the $\binom{n}{2}$pairs of vertices is, independently, an edge of this graph with probability p.Let $P_n$ denote the probability that ...
0
votes
1answer
62 views

Voronoi Diagram: Exactly 2n-5 vertices

I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices. I tried to use the Euler ...
1
vote
0answers
23 views

Variable elimination in Bayesian network

I'm trying to check if my understanding of variable elimination is correct. Assume the above Bayesian network is factorized as: $p(a,b,d,e,l,s,t,x) = p(a)p(t|a)p(e|t,l)p(x|e)p(l|s)p(b|s)p(d|b,e)p(s)$...
1
vote
2answers
95 views

Linear-time algorithm to find an odd-length cycle in a directed graph

Problem: Give a linear-time algorithm to find an odd-length (directed) cycle in a directed graph. (Exercise 3.21 of Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.) The related post@...
3
votes
0answers
64 views

How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal. Since,...
1
vote
1answer
32 views

Minimum Weight Directed Subgraph ensuring all pairs reachability?

After some work on Minimum Spanning Trees and Steiner trees in combinatorial problems I came across this problem that I would like to look further in my research, but I want to know if there is an ...
2
votes
2answers
159 views

Basic questions about network flow calculations

Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to ...
1
vote
1answer
32 views

Relation between MAX CUT and MIN CUT

I'd like to ask a question about MAX CUT and MIN CUT on graphs with unit edge-weight. I know that MAX CUT is NP-Hard, but MIN CUT is in P (i think)? Barahona, in 1982, showed (Lemma 1) finding a cut ...
1
vote
0answers
23 views

What is the psuedo-code for Tremaux's Algorithm as a Depth First Search to solve a maze?

I was interested in the Tremaux Algorithm as a Depth First Search to solve a Maze. Unfortunately I was not able to understand what Data Structures are and how they could be used. For example, I saw a ...
1
vote
2answers
51 views

Equivalent definition of minimal spanning tree

Prove that $T$ is MST $\Leftrightarrow$ for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$. It's my attempt to prove $\Rightarrow$: Consider the ...
3
votes
0answers
23 views

How to compute amortized complexity of n runs of Dijkstra's algorithm?

I'm trying to figure out how to compute an amortized complexity/ or complexity of this algorithm. We have a Graph which is oriented. And we are going to run Dijkstra's algorithm for finding a shortest ...
1
vote
0answers
27 views

Generate a graph to exact size using Kronecker product graph model

In network science, we can take sample a complex system and derive from this sampling a representative network (or graph) that describes the system to some extent. A model of a network, is a powerful ...