Removing vertices from a labelled graph

Let $ G$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with different integer labels are connected with an edge, but also among all groups of vertices labeled with the same integer, the size of the smallest group (i.e., the number of vertices) is maximum possible?

How to check whether given $k$ vertices make a $k$-clique in an undirected graph $G$ efficiently

Let $ G=(V, E)$ be an undirected graph with vertex set $ V$ and edge set $ E$ . Let $ V’=\{v_1, v_2, …, v_k\}$ be a subset of $ V$ where degree of each $ v_i$ is bigger than or equal to $ k$ . Is there a way to check whether $ V’$ is a $ k$ -clique more efficient than the brute-force algorithm in $ O(k^2)$ ? Thanks in advance.

How can I determine if two vertices on a polygon are consecutive?

Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices on the polygon. Does anyone know of an algorithm that would do this, as in you would input the array of points and the two vertices as parameters and it would return a boolean?

It’s given that the polygon exists and is unique.

How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?

I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List Representation. What I did is as follows:

• Do a simple BFS Traversal using a Queue while maintaining the parent node of nodes enqueued in the queue.

• If I come across a node u that has a neighbor v such that v is already visited but v is not the parent of u then that means there is cycle in the graph.


#adjList is the adjacency list given as a dictionary #myQueue is a double-sided queue containing node and its parent node ([Node, parNode]) #visited is a set containing visited nodes  while(myQueue):     currNode, parNode = myQueue.pop() #dequeue operation     visited.add(currNode) #Marking currNode as visited     for childNode in adjList[currNode]: #Traversing through all children of currNode         if currNode not in visited:             myQueue.appendleft([childNode, currNode]) #Enqueue operation         else:             if childNode!=parNode: #Main logic for cycle detection                 print('CYCLE DETECTED')                 break 

The above approach is working except in cases when I have more than 1 edge between 2 vertices for e.g. in following case we have 2 edges between vertices 0 and 1:

Graph containing cycle

Adjacency list of above graph is: adjList = {0:[1, 2], 1:[0], 2:[0]}. Here we can clearly see that the graph contains a cycle but above algorithm is not able to detect the same because when BFS will reach vertex 1, vertex 0 is already visited but vertex 0 is also the parent of vertex 1 so this cycle will go undetected.

My question is how I can modify above algorithm to detect such cases?

Edit: I tried the same logic on directed graphs also, and I am facing similar problem i.e. case when I have a directed edge from vertex 0 to vertex 1 and another directed edge from vertex 1 to vertex 0

Determine the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle

I need to create an algorithm that will output the number of self-crossings for an irregular orientation of an n-pointed star, whose vertices lie on the boundary of a circle. The sample input is as follows:

5 24.0 168.0 312.0 96.0 240.0 

Where the first integer is n (the number of vertices), proceeded with n lines, each describing the positions of the vertices, taken in order, which form the star. Each vertex is in a unique position on the boundary of the unit circle, specified in degrees from the normal axis. All degree measures will be in the range [0,360).

The sample output for the sample input would be:

5 crossings 

To tackle this problem, I was thinking of maybe separating the unit circle into quadrants and determine whether there are crossings depending on the positions of the vertices in their respective quadrants. However, I haven’t been able to think of a way to implement this.

I was wondering if anyone could provide perhaps a high-level idea or a push in the right direction which could help me think of an algorithm.

Thank you.

Like transitive reduction, but removing vertices rather than edges?

Suppose I have a directed graph $ G = (V, E)$ (or, which is the same, a relation on the set $ V$ as defined by the adjacency matrix) that may contain three vertices $ x, y, z$ such that $ xy, xz, yz \in E$ — that is to say, the relation restricted to $ x, y, z$ is transitive, there is a triangle. Let us call this situation a “local transitivity”. My goal is to obtain all the subgraphs of $ G$ induced by cutting middle vertices from local transitivities until none remain, which I dub “resolution”.

There may be multiple solutions. For instance, consider a graph given by this relation:

  a b c d   a □ ■ ■ □   b □ □ ■ ■   c □ □ □ ■   d □ □ □ □   

(It looks like a square with one diagonal.)

There are two ways it can be resolved:

  a b d        a c d   a □ ■ □      a □ ■ □   b □ □ ■      c □ □ ■   d □ □ □      d □ □ □   

One way I can compute the resolutions of a graph is by giving a “non-deterministic” function $ f :G \rightarrow \{G\}$ that removes any single local transitivity. Repeatedly applying $ f$ to any graph, I will eventually converge to a set of induced subgraphs completely devoid of local transitivities.

One way to define $ f$ is by considering all the triples of distinct vertices and checking them for local transitivity. From each matching triple, the middle vertex is extracted, and any of these vertices is cut. But there is about $ |V|^3$ such triples.

Is there a better way? Is there prior art that I may study?

How to draw a graph whose vertices are elements of permuation group

How to write the following program in C++:

Consider the Permutation Group $ S_3$ .

The elements of $ S_3$ are $ e,(12),(13),(23),(123),(132)$ .

I want to draw a graph $ G$ whose members are the elements of $ S_3$ and two vertices $ x,y$ are adjacent if and only if $ xy\neq yx$ .

I am stuck in doing the following things:

  1. How to call the elements of $ S_3$ through a loop?
  2. How to draw the graph $ G$ ?
  3. How to check whether they commute or not

    I am stuck in the three things. Is there any way to write the code in C++?

As an example if I input $ S_3$ I want to get the following graph

$ G=Graph({1:[2,3,4,5],2:[1,3,4,5],3:[1,2,4,5],4:[1,2,3],5:[1,2,3]})

Any help will be highly appreciated.

Directed Trees: Finding all the edges and vertices in a specific direction

I am an electrical engineer without experience in graph theory. However, I have a problem which I believe can be solved by graph theory. We have a directed tree, such as the one below. We want to find all the vertices and edges starting from a vertex in a given direction. For instance, in the figure below, we want to identify the vertices and edges downward from vertex 1 (the red lines). Is there an algorithm to do this (preferably in MATLAB)? The edges have equal weight.

enter image description here

Ordering vertices of graph based on specific vertex-transitivity

Given any complete directed weighted graph $ G$ with $ n$ vertices $ V$ and matrix of non-unique weights $ W$ , find a weak ordering $ T$ on the vertices of the graph satisfying the following conditions:

  • $ T$ is invariant under permuting the vertices

  • For any two vertices $ u$ and $ v$ , $ u = v$ in $ T$ if and only if there is some automorphism $ f:V(G) \rightarrow V(G)\ $ such that $ f(u) = v$ and $ f(v) = u$

The reason I want such a thing is to have some consistent but arbitrary way to order the vertices of a graph that is invariant under permutation, as a tie-breaker for more meaningful orderings, when the vertices are actually distinct, which will usually be the case. If two vertices cannot be distinguished, picking whichever one happens to be first in my representation is fine.

I expect this problem is in $ NP$ , as it seems like there’s some way to compute graph isomorphisms with it, but my graphs are small and I can precompute the ordering once, so it would still be useful to figure out how to do it.