Efficiently finding “unfounded edges” in a strongly connected graph

I’ve encountered a problem I need to solve concerning dependency graphs. I’ve simplified it as follows:

Consider a strongly connected graph G = (V,E).

  • We define a subset of vertices S ⊆ V as source vertices.
  • We call an edge e = (a,b) unfounded if there is no simple path from any source vertex to b that includes e. In other words, all paths from a source vertex that include edge e, must include vertex b at least twice.

The problem:

  • Find all unfounded edges in G.

There are some obvious ways to solve this inefficently (e.g. a depth-first traversal for each edge in G), but I was wondering if there was any O(|E|) approach. I’ve been struggling with this for a while and I keep “almost” solving it in linear time. Perhaps that’s impossible? I have no idea what the lower bound on efficiency is, and I was hoping some readers here could help me discover some efficient approaches.

Finding pairs of vertices which would disconnect a graph

An assignment question asks,

Given a connected, undirected graph $ G$ , describe an algorithm which can determine if the removal of any pair of vertices would cause $ G$ to become disconnected.

There is an obvious brute force solution, which is to just generate all pairs of vertices, produce new graphs with those vertices removed, and then test if that graph is connected using something like a BFS, running in $ O(|V|^3)$ time.

However, I feel like this is not the intent of the question. We learned about an algorithm to find the articulation points of a graph, and it seems like something like this should be possible to determine if the removal of any pair of vertices would disconnect the graph, but I am not sure how it would be applicable.

Determine if the edges of a graph are distinguishable

Mathematica 12.1 introduces edge tagged graph (EdgeTaggedGraph), which is supposed to solve the problem of distinguishability of parallel edges. Unfortunately, the feature is not very well done, and there is no way to guarantee distinguishability. It is allowed that some edges do not have tags at all, or that parallel edges have the very same tag.

Thus, if we were to implement a function which requires that edges be distinguishable, we must check that that is really the case. Since this check will be run every time out function is called, it should be very fast. In Mathematica 12.0 and earlier, which had no edge tagged graphs, one could simply use MultigraphQ. This is an O(1) operation, I assume achived through caching.

How can I check that all edges of a graph are distinguishable in Mathematica 12.1, with good perfomance?

My current solution:

nonDistinguishableEdgesQ = MultigraphQ[#] && (Not@EdgeTaggedGraphQ[#] || canonicalEdgeBlock@Not@DuplicateFreeQ@EdgeList[#])& 

where canonicalEdgeBlock is from here (a still open question also asking for performance improvements).

Requirements:

  • As fast as possible.
  • Must work on all kinds of graphs that Mathematica supports, including mixed graphs.
  • It is acceptable (in fact it is practically necessary) for the function to have multiple branches, selecting the fastest possible method for the type of given input graph.
  • It is acceptable to use IGraph/M specific functions, such as IGIndexEdgeList, for the implementation.

Query: Given a graph, is edge x in an optimal TSP tour?

Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph.

It may be argued that the complexity of this problem is strictly greater than any co-NP problem. The idea is that it’s perhaps impossible to come up with a counter-example, since we need e.g. an optimal tour candidate before we can consider a counterexample (but no optimal tour candidate is given in this problem statement).

On the other hand, it may be argued that the complexity of this problem is strictly smaller than any P-space-complete problem, as our problem may be seen as

$ \exists$ “a tour A containing x” $ \forall$ “tours B”: (some formula stating that A <= B)

whereas some probably “minimal” P-space-complete problem has O(n) alternations of $ \exists$ and $ \forall$ : the quantified boolean formula problem (QBF).

Based on this argument, is it reasonable to expect that there’s a complexity class between co-NP and PSPACE? Does this particular class have a name? Can we expect to find arbitrarily more such classes by adding another one alternation of $ \forall$ or $ \exists$ to the previously found such class?

training SimpLE model for link prediction on knowledge graph

Referring to this paper by Prof Kazemi, Prof Poole on SimpLE model for link prediction on knowledge graph.

In page 3, the paragraph on learning SimpLE Models, I understand that we have a batch of positive triples from the knowledge graph, where for each positive triple in the batch, we generate $ n$ negative triple by corrupting it. So does that mean the batch size just increased by a factor of $ n$ and there are only negative examples in the batch?

I think I understand the optimization function but I don’t understand how we generated the labeled batch. Clarification would help!

Finding a hamiltonianISH path in a graph


Problem statement

Given a graph of all the blue squares in the following image where each blue square is connected to other blue squares in all 4 cardinal directions.

Given any starting node.

What algorithm will allow for finding the longest(ish) path.

Considering that each node can only be visited once.

Considering that we don’t care where the path ends.

Considering that speed is more important than necessarily visiting each node.

Example

I have traced an example of the desired result in the image below. As you can see, the path does not visit each node and that is fine. I’m looking for a fast algorithm that will give me one of the longest possible path on this graph. 80% coverage or more is what I’m shooting for.

enter image description here

Perfect Matching in Bipartite Graph with mutually exclusive edges

Problem

I would to solve Perfect Matching in Bipartite Graph Problem where some edges are mutually exclusive.

Example

Left vertices: $ a,b,c$

Right vertices: $ x,y,z$

Edges: $ (a,x),(a,y),(b,z),(c,y)$

Exlusive pairs: $ (b,z)$ and $ (c,y)$

Answer: no perfect matching

Question

Is the problem in P or NP?

Solution Attempts

I know that Perfect Matching in Bipartite Graph Problem is in P. But I cannot find a polynomial-time algorithms for the above version of this problem. I have also tried proving that it is NP, but without any luck.

Efficiently remove nodes from a connected graph

Suppose you have a connected graph and want to remove k nodes such that the result is still connected. How could you do this efficiently?

It occurs to me that you could find any spanning tree, say by a tree search of any kind. Identify all leaves in the spanning tree, all of these can be removed without disconnecting the remaining vertices. If you have more than k leaves then you’re done, but in any tree you’re only guaranteed 2 leaves. So you may need to reiterate the process until you’ve removed k vertices.

That implies O(k) runs of a tree search. Does a more efficient algorithm exist? I don’t think you can just look for articulation points or bridge edges because removing a single vertex may suddenly make other vertices which weren’t articulation points now turn into articulation points.

Prove that if we take all the edges in directed graph that are on some shortest path from 1 to N we will get a DAG

We are given directed weighted graph with possibly some cycles with $ N$ nodes and $ M$ edges. Let’s observe all the shortest paths from $ 1$ to $ N$ in this graph, finding the single-source-shortest paths from $ 1$ in the normal graph and the single-source-shortest path from $ N$ in the inverse graph we can check for each edge whether it belongs to some shortest path or not.

If we take all the edges that belong on some shortest path and build a separate graph we will get a directed acyclic graph. How can we prove that this graph will never have a cycle? I haven’t written many proofs on graphs before, so I solved the problem, however I’m not sure why this will always hold.

How to create random graph with certain properties?

My question consists of two parts.

  1. How to create a random undirected connected graph s.t. the probability of the event “The degree of a vertex equals k” is equal to $ \frac{k^{-\gamma }}{\zeta (\gamma )},\,k=1,2,\dots,\,\gamma >1$ ? Of course, I looked in RandomGraph , but didn’t find the answer. My attempt RandomGraph[ZipfDistribution[2]] is not successful.
  2. Additionally, let the probability of the event “The vertices of degrees $ k_1$ and $ k_2,\, k_1\ge k_,\,k_2\ge 1$ are connected by the edge” be equal to $ $ \frac {k_1^{-\gamma}k_2^{-\epsilon}} {\zeta(\gamma ) \zeta (\epsilon )},\,\gamma > 1, \epsilon >1.$ $

The question is motivated by the article Lazaros K. Gallos, Chaoming Song, and Hern$ \acute{\rm a}$ n A. Makse, Phis.Rev. L. 100, 248701 (2008).