Algorithm for finding “mean center” of unweighted graph

I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I’m calling the “mean center” (the vertex w/ shortest mean distance to all other vertices. Does this already have a name?). I know of an $ O(N^2)$ solution: Starting at every vertex: BFS to calculate the mean distance to all other vertices, choose the minimum. But $ N^2$ is too slow for a graph this size, is there any way to calculate the “mean center” in faster than $ N^2$ time? Are there any good approximation algorithms? Or more efficient algorithms which find some similar “center” of a graph?

Maximum flow on a tripartite graph

I have to solve an assignment problem between $ \{1,\dots, N\}$ agents and $ \{1,\dots, M\}$ objects, which comes to maximize : \begin{equation} \sum_{ij}\beta_{ij}x_{ij} \end{equation} where $ x_{ij}$ equals one if object $ j$ is assigned to $ i$ , $ 0$ otherwise. The benefit of such an assignment is the non-negative value $ \beta_{ij}$ .

This problem usually comes wih some constraints : \begin{equation} \sum_i x_{ij} = 1~,~~\sum_j x_{ij} = 1 \end{equation} stating that an object can only be assigned once and that an agent can only assign one object.

As far as I understand, this problem can also be viewed as a maximum flow on a bipartite graph and can be efficiently solved by an auction algorithm (see Bertsekas et al.)

I have to implement additional constraints labeled $ k=1,\dots, K$ which are all of the same form : the $ k^{th}$ one imposes that on a subset of object $ \mathcal{J}_k$ , only a limited number of them, say $ P_k$ , can be assigned in the same time : \begin{equation} \sum_{j\in \mathcal{J}_k}\sum_i x_{ij} \le P_k \end{equation}

My question is that I find quite difficult to solve former problem with these new constraints on a bipartite graph and I wonder if a tripartite graph would be more convenient.

Here is below how I would do, I would like to call upon more experienced people in this field to assess whether this approach is well suited or if there is a simpler one.

I put the former problem with the additional constraints in the form of a tripartite graph : the first column is still that of agents and the third one that of objects, except that agents and objects are no more directly linked.

Between first and third column, I insert the column of the $ \{1,\dots,K\}$ constraints. Let $ y_{ik}\in\{0,1\}$ be the link between agent $ i$ and constraint $ k$ . The additional constraint $ k$ now reads : \begin{equation} 0\le\sum_i y_{ik} \le P_k \end{equation} The flow of agents onto constraint $ k$ is limited.

Furthermore, let $ z_{kj}\in\{0,1\}$ be the link between constraint $ k$ and object $ j$ .

That is to note, an object $ j$ can be linked to several constraints, let $ \mathcal{K}_j$ be the subset of constraints in which object $ j$ is involved, i.e. $ j\in \mathcal{J}_k$ .

The flow from constraint $ k$ to objects must equal that of agents to this constraint :

\begin{equation} \sum_i y_{ik} = \sum_j z_{kj} \end{equation} which means that an agent $ i$ is connected to constraint $ k$ because there is some object $ j$ linked to it, and conversely.

Then, coming back to the bipartite graph, the link $ x_{ij}$ between agent $ i$ and object $ j$ is now : \begin{equation} x_{ij} = \sum_{k\in\mathcal{K}_j} y_{ik} + 1 – |\mathcal{K}_j| \end{equation} This equals one only if the agent $ i$ is connected to all constraints $ k$ in which object $ j$ is involved. The inconvenient is that $ x_{ij}$ can be negative. Another defintion could be : \begin{equation} x_{ij} = \min_{k\in\mathcal{K}_j} \{y_{ik}\} \end{equation} but I would like to remain as most linear as possible.

Because $ P_k< |\mathcal{J}_k|$ there will always remain at least $ |\mathcal{J}_k| – P_k$ unassigned objects due to constraint $ k$ .

Let’s define a virtual agent $ s$ to which we attach all objects (at zero benefit) not linked with any constraint $ k$ , $ \forall k~~ z_{kj} = 0$ . The link is denoted $ x_{sj}\in\{0,1\}$ because it is a direct link between an agent and objects.

Each object $ j$ must fulfill : \begin{equation} \sum_{k\in\mathcal{K}_j} z_{kj} + |\mathcal{K}_j| x_{sj} = |\mathcal{K}_j| \end{equation} Then, either object $ j$ is connected to all its constraints, $ \forall k\in\mathcal{K}_j~,~z_{kj} = 1$ , or it is connected to the virtual node, $ x_{sj}=1$ .

It is clear that if the flow on all constraints reach its maximum, there will remain at least : \begin{equation} \sum_k (|\mathcal{J}_k| -P_k) \end{equation} objects unassigned, thus : \begin{equation} \sum_j x_{sj} \ge \sum_k (|\mathcal{J}_k| -P_k) \end{equation}

Then, each time the links between an object and its constraints are broken, the object becomes unassigned, so that : \begin{equation} \sum_j x_{sj} – \sum_k (|\mathcal{J}_k| -P_k) = \sum_k y_{sk} \end{equation}

where $ y_{sk}$ is the link between the virtual agent and the constraint $ k$ , whose capacity is $ \{0,\dots,P_k\}$ and checks : \begin{equation} \sum_i y_{ik} + y_{sk} = P_k~,~~0\le y_{sk}\le P_k \end{equation}

Coming back to the assignment problem, the maximization becomes : \begin{equation} \begin{split} \sum_{ij}\beta_{ij}x_{ij} =& \sum_{ij}\beta_{ij}\biggl(\sum_{k\in\mathcal{K}_j} y_{ik} + 1 – |\mathcal{K}_j|\biggr)\ =& \sum_{ik}\biggl(\sum_{j\in\mathcal{J}_k}\beta_{ij}\biggr) y_{ik} + \sum_j (1 -|\mathcal{K}_j|)\sum_i \beta_{ij} \end{split} \end{equation} so that the maximization now takes place between agents and constraints. I would like then to write the dual formulation of this problem in order to solve it with an auction algorithm : agents have to buy all constraints to which an object is related in order to be assigned this one.

Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

We have an undirected simple connected graph with odd number of vertices. We also know the number $ k$ which is actually the closest odd number greater than or equal to $ \Delta$ . (So if $ \Delta$ is even, $ k = \Delta +1$ else $ k=\Delta$ .) i.e $ k$ is the least odd number that is greater than or equal to degrees of all vertices.

We want to find a linear time algorithm that colors the graph with $ k$ colors.

I am very new to graph coloring algorithms. I know that a greedy algorithm is actually linear time and can color the graph with $ \Delta +1$ . But I can’t guarantee I can color it with $ k= \Delta$ when $ \Delta$ is odd. Also, we probably should use all the information the question gives us. i.e using odd number of vertices somehow, but greedy algorithm don’t use this extra information.

How can I solve this?

Artificial ant colony algorithm for graph

let’s assume we have ant at node $ 1$ and she has $ \{2,3,4\}$ vertices. How do I compute which one she choose? I mean if the formula $ p_{ij}(k)$ is the probability of $ k$ -th ant at node $ i$ choose $ j$ node, for example, do I take $ j=2$ , compute the probability and if it satisfies $ random(0,1)<p_{12}(k)$ , the ant choose $ j=2$ , if not move to next vertex $ j=3$ until the inequality is satisfied? The next question is, can you recommend me the sources, where I can find conversion from this algorithm graph version to optimizing function version. Thank you.

Clique-problem for planar graph

I have to show, that the clique problem is in P for planar graphs. I found a post, that anwers this here. However I don’t get the conclusion “This follows already from Kuratowski’s theorem: a clique is at most of size 4.”

I’ve never heard of that theorem before and the exercise indicates to proof it with the fact, that the class of planar graphs is closed under sub graphs. Thank you for your help!

Algorithm for breaking a graph into sub-graphs based on an attribute

I am a biologist doing some computational work. I encountered a problem and need some help since I don’t have much algorithmic background.

The problem:
Assume we have a non-directed, weighted graph, in which every node has some categorical attribute, e.g. color. I want to break the graph into sub-graphs in which there is at most one node of each color. Decisions should be made by trying to preserve the strongest connections (edges with highest weights). For example, let’s look at the graph below (I didn’t include weights as this would be hard to see):
enter image description here
In this case, I would like to break the graph into two sub-graphs (assuming that this is what the weights indicate): enter image description here
Two notes (I don’t know if they matter though):

  • The maximal number of colors is known in advance
  • After the graph was broken, I don’t really care about the topology anymore – I just want to know which nodes ended up together.

My questions:
My first question is: does this look familiar to you? Has this problem been solved before? Maybe it’s a variant of something every CS student learns? If so, can you please refer me to relevant information/literature?
If not, Then I’d like some help on how to approach this. Can you give some ideas on how to start developing and algorithm that can solve this type of problem?
Any other advice would be useful. Thank you!

Literature request: Generating all vertex subsets of a graph

I made the same post here in Mathematics Exchange but maybe here is a better place.

I am working in an algorithm which finds a unique maximal independent set of vertices which generates all other vertex subsets. This is done using two measures of ‘importance’ for vertices. I assume this might have some applications outside mathematics, especially in computer science, but I am not sure where I can read about such applications. Does anyone have any good literature suggestions?

Graph problem with expectation

Consider an undirected graph G = (V, E) representing the social network of friendship/trust between employees. We partition the set of node triples into four sets T0, T1, T2, and T3. A node triple v1, v2, v3 belongs to T0 iff no edge exists between the nodes v1, v2, and v3, – T1 iff exactly one of the edges (v1, v2), (v2, v3), and (v3; v1) exists,- T2 iff exactly two of the edges (v1, v2), (v2, v3), and (v3, v1) exist,- T3 iff all of the edges (v1, v2), (v2, v3), and (v3; v1) exist. |T3| denotes the number of connected triples in the graph that is the quantity we need to estimate. if i apply the following algorithm:

  • Sample an edge e = (a, b) uniformly chosen from E

  • Choose a node v uniformly from V \ {a, b}

  • if (a, v) ∈ E and (b, v) ∈ E then x = 1, else x = 0

How can I show that |T1| + 2|T2| + 3|T3| = |E|(|V | − 2)?