Count bridging edges in a family of two component forests

I am given a (simple, undirected, connected) graph $ G = (V, E)$ and a fixed spanning tree $ T$ in this graph. Removing an edge $ e\in E(T)$ from $ T$ splits it into a spanning forest $ F^e$ with two components $ F_1^e$ and $ F_2^e$ . I am interested in the number $ c(e)$ of edges in $ G$ that connect $ F^e$ i.e. with one vertex in $ F_1^e$ and the other in $ F_2^e$ .

I would like to compute the number $ c(e)$ for all $ e$ in $ T$ simultaneously. This can be done naively in $ O(|V||E|)$ . Is there a faster way to achieve this?

The graphs I am working with are small-world graphs. In particular the average distance between nodes in $ G$ can be assumed to be small.

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.

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.

Find longest path by number of edges, excluding cycles

I need to analyse a directed graph but I don’t know the name of the algorithm I would need to use. The graph has many cycles.

My desired behaviour is: given a graph source and graph sink, find the longest path by number of edges, excluding cycles.

By graph source, I mean a vertex with one or more edges to other vertices and no incoming edges, and the opposite for sink. If there’s better terminology, then please let me know about this.

By excluding cycles, this might entail not traversing an edge the process traversed previously.

Do you recognise this algorithm and could you tell me the name, please?

Thanks in advance

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.

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.

Graph algorithm to match labled edges to sequence of labled edges

I’m looking for a standard algorithm to solve a particular type of graph matching problem. Consider the following two graphs:

Graph 1 1 --A--> 3 1 --B--> 2 2 --C--> 3 4 --A--> 8 4 --B--> 5 5 --C--> 6  Graph 2 1 --X--> 3 4 --X--> 6 

When these are matched, I’m looking for a result as follows:

Graph 1:    a --B--> ? --C--> b             == Graph 2:    a --X--> b 

That is, edge X of Graph 2 maps to path BC of Graph 1. The reason is that the start and end vertices joined with edge X in Graph 2 are same as the start and end vertices joined by path BC in Graph 1. Edges labeled A in Graph 1 represent extraneous connections.

Is there a standard algorithm to solve this, especially one implemented in Python? If so, what is it called?

Finding an algorithm that after removing k edges we get an acyclic graph

Assuming there’s an algorithm that can decide belonging to ACYCLIC in polynomial time. How can I use this algorithm in another algorithm that upon the input of a directed graph and a positive number k, returns k edges that after removing them, the graph becomes acyclic(has no cycles). there are no weights in the graph, just regular directed graph.

ACYCLIC is for a directed graph that is acyclic.

What I am trying to do is something like this: For a directed graph G=(V,E), Assuming there exists an algorithm isacyclic that returns true or false whether given graph is acyclic or not:

1)select a vertex and begin traverse the graph

2)while number of edges > 3 and we did not finish traversing the graph(3 edges can form a cycle, and i need at least one more because k should be positive, meaning number of edges that upon removing i’ll obtain an acyclic graph)

2.1)if (number of edges traversed – 3) greater than k

2.2)if isacyclic returns false:

2.3)try eliminating last edge and rerun isacyclic, if returns true – add edge to a list/stack and continue traversing without it

if at the end of the algorithm there are no k edges in the list/stack – reject

else accept

The algorithm I wrote was general idea of what I am looking for. I assume that there exists an algorithm that can decide belonging to ACYCLIC in a polynomial time for the questions sake.

What I am looking for is an algorithm that for a directed graph g and a positive number k, can give me k edges that when I remove them, I get an acyclic graph

The algorithm should be polynomial in regards to its input size.

Thank you very much!

Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

i don’t understand the following:

If there’s an algorithm that can decide ACYCLIC in Polynomial time, then there’s an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without circles – in polynomial time.

The algorithm should get a directed graph and a natural k as an input, and output, if there are k edges as needed, a list of k edges, so that the graph obtained from erasing those k edges is circleless. if there are no such k edges, it simply outputs “no”.

Problematic part: I can only use an algorithm that decides ACYCLIC, but it is forbidden to use any other NP-Complete algorithms, and it’s running time must be polynomial in regards to its input size.

My attempt: well, to check/decide if a directed graph is ACYCLIC or not, we’ll visit it topologically using DFS, then using a stack, we’ll traverse edges to see if any edge in the digraph leads back to an edge already visited. if already visited – there’s a cycle, if not – there’s no cycle.

The algorithm: on an input of a directed graph, to check ACYCLIC:

1)finding an vertex that has only outgoing nodes – if such node doesn’t exist – return “graph has cycles”

2)on that node, run DFS and traverse the digraph; add each edge found to a stack. if a vertex is shown twice – return “graph has cycles”.

3)if no cycles found, accept.

But, I am not sure how to do it in regards to the algorithm required in the problem(first two paragraphs of the questions – basically, returning a set of k edges, so that by removing them, the graph will be circleless.

would really appreciate knowing how to do it.

thank you very much

Graph theory question involving weights of edges

I’m trying to solve the following problem but I can’t understand it. Could you guys kindly break it down for me? I’m not asking for anyone to solve it. I just want to be able to grasp the problem.

Given a graph of siblings who have different interests, you’d like to know which groups of siblings have the most interests in common. You will then use a little math to determine a value to return.

You are given integers sibling_nodes and sibling_edges, representing the number of nodes and edges in the graph respectively. You are also given three array integers, sublings_from, siblings_to and siblings_weight, which describe the edges between siblings.

The graph consists of nodes numbered consecutively from 1 to siblings_nodes. Any members or groups of members who share the same interests are said to be connected by that interest (note that two group members can be connected by some interest even if they are not directly connected by the corresponding edge).

Once you’ve determined the node pairs with the maximum numbers of shared interests, return the product of the node pairs’ labels. If there are multiple pairs with the maximum number of shared interests, return the maximum product among them.

For example, you are given a graph with subling_nodes = 4 and sibling_edges = 5:

   FROM   TO   WEIGHT    1      2    2    1      2    3    2      3    1    2      3    3    2      4    4 

If we look at each interest, we have the following connections:

   INTEREST   CONNECTIONS       1          2,3    1          1,2    2          1,2,3    2          2,4 

Example input:

   siblings_nodes: 4    siblings_edges: 5    siblings_from: [1, 1, 2, 2, 2]    siblings_to: [2, 2, 3, 3, 4]    siblings_weight: [1, 2, 1, 3, 3] 

output:

   6