I have an undirected weighted graph without multi edges. All the edge weights are whole numbers and known. I want to know in how many ways node values(node values are also whole numbers) can be assigned to the nodes such that the graph satisfies the condition that for every edge its edge weight is exactly equal to maximum of two node values this edge is incident on.

# Tag: graphs

## Directed Grid Graphs; All Possible Paths Through Nodes

I have a problem in which I am interested in taking a matrix of positive integer weights, including zero, where the matrix has dimensions nrow x ncol and the columns always sum to the same arbitrary number. I want to search for a list of paths (sets of edges essentially) that traverse through the grid space of the same dimension & create the paths such that the # of edges in a path going through a node is equal to the nodes weight (from the matrix). Ie: if a particular index in my matrix was "3", there would be 3 edges that would run into (and out of) this node.

Some important restrictions. Firstly, The only direction the edges can move is rightward (so vertical edges are disallowed) but only one column distance at a time. I do allow for the edges to go from any row_j (in column_i) to any other possible row_j in column_i+1, so diagonal edges (either upwards or downwards are allowed). Here’s an example of such a solution (it is non singular which is why Im interested in ALL possible paths)

Most importantly, I am interested in two things. First I want all possible paths from this process, and even more critically, I want to minimise the number of possible diagonal edges that my resulting paths will contain.

Any sort of algorithm here to solve this would be hugely helpful.

I have managed to solve the case when I don’t care about the number of diagonal edges, and just want a set of paths that match with the weights. To do that, I used the weights at adjacent columns to generate a Markov transition process. This gave me a series of transition matrices (of length ncol-1) which from there I was able to construct probabilistically what my paths through my weights were.

Let me know if anyone needs any more details/explanations here.

## Bipartite graphs with min weights

I have a full bipartite graph with node sets $ A=\{a_1,a_2,\ldots,a_n\}$ and $ B=\{b_1,b_2,\ldots,b_n\}$ . Each node has a weight, $ v_i$ for $ a_i$ and $ w_i$ for $ b_i$ . Each node $ a_i$ is connected to exactly one node of $ B$ , say $ b_j$ , via an edge $ e_i$ , whose weight is $ \min(v_i,w_j)$ . Now I want to find a one-to-one mapping from $ A$ to $ B$ , whose sum of edge weights is as small as possible.

My idea is to sort $ v_i$ s increasingly and $ w_i$ s decreasingly and then find the sum of all $ \min(v_i,w_i)$ after sorting. Is it correct? Can you give a proof/disproof?

## Finding simple path on grid graphs of length $l$

Let $ G$ be a grid graph and we are given two vertices $ s$ and $ t$ and $ l$ , the goal is to check if there exists a path from $ s$ to $ t$ simple path of length $ l$ ?

Brute force algorithm will give $ n^l$ time algorithm as I will simply enumerate all the paths of length $ l$ . Are there faster algorithms for this problem?

My observation is grid graphs are bipartite graphs so all paths will be either of odd length or even length but I don’t know how to use this fact. Note that in grid graphs the degree is bounded by four so from any vertice to any other vertex, number of paths of length $ l$ are bounded by $ 4^l$ . I am looking for an algorithm faster than $ 4^l$ .

## Is realization of unit disk graphs hard?

It is known that recognizing a unit disk graph is NP-hard [1].

However, the paper does not mention how hard is the realization problem.

I have looked up several references [2][3][4]. None of the papers answer whether the following problem is NP-hard:

Given a unit disk graph $ G = (V,E)$ , find a configuration of a set $ \mathcal{D}$ of disks, such that the intersection graph $ G(\mathcal{D})$ of $ \mathcal{D}$ is isomorphic to $ G$ .

The difference between this problem and the recognition problem is that the input of this problem is guaranteed to be a unit disk.

Is there any study that shows the complexity of the above problem? I expect it to be NP-hard, but I am yet to find a full proof.

## Max independent set in planar graphs PTAS proof

I’ve been searching a few hours for a proof to Max independent set in planar graphs beeing in PTAS but I couldn’t find anything, I’m searching for one without any reductions and I wonder if anyone here can help me find one.

Thanks in advance.

## What are some real world applications of graphs?

Can you give some real world examples of what graphs algorithms people are actually using in applications?

Given a complicated graphs, say social networks, what properties/quantity people want to know about them?

## Ant Colony Optimization on Maximum Partitioning Graphs with Supply and Demand

I’m still new to the field of Computer Science and I’m having trouble understanding this paper An ant colony optimization algorithm for partitioning graphs with supply and demand. Can I ask for a simpler explanation of the paper?

## Are there graphs for which A* cannot be admissible?

Wikipedia states that “On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)>\varepsilon >0$ for some fixed $ \varepsilon$ ), A* is guaranteed to terminate only if there exists a solution.”

Does this mean that, if I have such a graph, then there is no admissible A* which exists for this graph? When one says that A* is not admissible, this means that its heuristic is not admissible, right?

Furthermore, is it correct to say that a heuristic is only admissible with respect to a graph – not generally admissible?

For example, if I have a infinite graph which has a finite branching factor, and the cost of each edge is half of the cost of the edge preceding it (something like this: $ goal\leftarrow_{_{c=2}} start \rightarrow_{_{c=1}}q1 \rightarrow_{_{c=1/2}} q_2 \rightarrow …$ ), the heuristic and therefore the A* is necessarily inadmissible as there exists no fixed $ \epsilon>0$ that is less than the cost of any edge?

To generalize, the $ epsilon$ constraint is to make sure that there is no infinite path who’s total cost converges, thereby assuring termination?

Any clarification is appreciated. Thanks!

## When should we construct trees, graphs to analyse an algorithm?

In many algorithms, it’s easy to understand how the algorithm is executed, but as for why it works well and how it can work, it’s not very easy to see, sometimes, authors construct trees or graphs to put things analysed in them and use those stuctures to describe the property of the research object and prove some property of the structures to finally give an explanation why it works well…

When should we use trees, graphs to analyse an algorithm? Or equivalently, what property do trees or graphs do well in describing in theory.

Like, in sort algorithms, many algorithms are analysed with a binary tree, in 2SAT algorithms, the core of the problem is decribed as a graph.

Well, for the problems with fixed mode, the structures can be implied easily, like the problems in OI or leetcode, however, in research such situation is not so likely to happen.

If the best probably answer is: well, when you feel some structures are proper, you can try them, it is hard to say which must be used and which shouldn’t. I accept it. I look forward to a more inspiring answer.