# Tagged Questions

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

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,...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
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-...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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?
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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)$...
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@...
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,...
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 ...
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 ...
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 ...
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 ...
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 ...