Finding maximum subgraph with vertices of degree at most k

Let $$G = (V, E)$$ be an undirected graph and $$U \subseteq V$$ some subset of its vertices. An induced graph $$G[U]$$ is graph created from $$G$$ by removing all vertices that are not part of the set $$U$$.

I want to find a polynomial time algorithm that has graph $$G = (V, E)$$ and integer $$k$$ as input and returns a maximum set $$U \subseteq V$$ with largest size such that all vertices of $$G[U]$$ have degree at most $$k$$.

My idea with greedy algorithm that removes vertices with largest degree or vertices connected with most vertices with degree greater than $$k$$ doesn’t work.

Does anyone know how to solve this problem in polynomial time?

Paint graph ordered vertices

I have the following question: Given graph $$G=(V,E)$$ with given order on its vertices, I mean $$v_1 I need to find minimal colors ordered paining of the graph vertices s.t neighbor vertices don’t have the same color, I mean: $$(v_1,v_2,…,v_j)$$ – painted in fist color and non of them are neighbors. $$(v_{j+1},…,v_l)$$ – painted in second color and non of them are neighbors. and so on.

The complexity needs to be $$O(V+E)$$. Anyone have an idea?

Navmesh awkward path generation with string pulling due to “inner” vertices

I’ve identified a problem and a possible solution related to navmesh-based pathfinding. Before diving in, I’ll preface my post with some questions to keep in mind as you read:

• Is this a known problem that people have solved before?
• Is there a term for the problem that could help me search for information related to it?
• Is the solution I came up with an existing idea? If so is there a name for the algorithm or some other search term I could use to find more information?
• Is there a better solution? If so, please point me to it.

For reference, I’m using images from http://jceipek.com/Olin-Coding-Tutorials/pathing.html#navigation-meshes and generally following the advice laid out there.

tl;dr of that blog post is

Decompose your walkable area into a navmesh, treating convex polygons as nodes and their borders as edges so that you can perform an A* search to get from point A to point B. To translate from “node ids” back to real points, use string-pulling.

Here’s a copy of the example space:

And an example generated path after performing string pulling:

So far so good.

But I realized this approach generates an awkward path in a situation like this:

In this situation, a trio of nodes are all adjacent to each other, and so the A* will generally choose a path directly from the starting node to the ending node, despite an intuitive understanding that the agent can move in a straight line from A to B which travels through a different polygon.

I’ve been working on a solution to this problem and so far my best idea is to apply a transformation to the nav mesh. My description of this will be a little hazy as I’m making up terminology to describe the approach…

• Define a shared edge as a line segment that is shared by two convex polygons in the navmesh. Maybe a.k.a. a “portal” for string-pulling purposes.
• Define an inner vertex as a vertex in the navmesh for which all attached line segments are “shared edges”. The vertex in the center of the three polygons in the image above is an inner vertex.
• Identify an inner vertex. Follow its attached shared edges to what I’ll call neighbor vertex. (possible improvement; If the neighbor vertex is also an inner vertex, recurse to its neighbors until all of the neighbors are non-inner.)
• Remove all shared edges from the navmesh that were traversed in the previous step, forming a new polygon whose border is defined by the neighbor vertices in the previous step. Redefine the edges accordingly (I’ll hand-wave that)
• Repeat until no inner vertices remain.

The result of this on the example above should result in this:

And with the same A-B path from before, the string-pulling should now result in a straight line:

I believe that as long as the navmesh has no inner vertices, all paths generated with the approach described in the linked blog post should seem “natural” and not have any surprise corners in what seems like open space.

Per my questions at the beginning of this post, I’m looking for more information, e.g. has anybody else solved this problem before, is there a better way to do it, and is there even a name/term for this problem?

Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic

So a tournament is just a complete directed graph, I believe.

I’m having trouble proving this problem. I know it is induction however. I was thinking the base case is $$2^1$$ vertices, and therefore we have a sub-tournament of 1 + 1 vertices, which holds.

Then in our induction step we have to show $$2^{n + 1}$$. But I’m not sure how to approach this. Any ideas would be extremely appreciated.

find shortest paths from source to all vertices using Dijkstra’s Algorithm?

For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ??? For example : What is the shortest path from 1 to 4? You need to print the value and the exact path vertices starting from 1 and ending at 4.

write a c++ code to solve shortest path between any two input vertices

Implement Floyd’s Algorithm and Dijkstra’s algorithm using all vertices as sources to solve All- pairs shortest path problem. For Dijkstra’s, you need to call the algorithm |V| times taking each

vertex as a source and store all tables. As a hint you may define T, presented in class, as a two- dimensional array, instead of being a one-dimensional array, of structures. You will read a graph

with random edge weights from a file and store the graph information in an adjacency matrix. Then, you need to answer any query asking for the shortest path between any two input vertices. You need to print the path from Floyd’s and Dijkstra’s algorithms. Your program should ask the user for the name of the input file.

Check if a pair of vertices belongs to the min-cut

Given a digraph $$G = (V,A)$$ with a source $$s \in V$$ and a sink $$t \in V$$, I need to adapt the graph to known if a pair of vertices $$u \in V$$ and $$v \in V$$ belongs to the min-cut $$S$$ between $$s$$ and $$t$$. That is, a new vertex $$a$$ belongs to the min-cut $$S$$ if and only if $$u \in S$$ and $$v \in S$$. This new vertex must preserve the original max-flow from $$s$$ to $$t$$. I tried creating new arcs $$(u,a)$$ and $$(a,v)$$ with infinity capacities, but while $$a$$ belongs to $$S$$ when $$u \in S$$, this immediately forces $$v$$ to belong to $$S$$ also, which is not necessarily true if the max-flow was computed in the original graph $$G$$. So, is there a way to force a new node to be in the min-cut set $$S$$ if a pair of vertices belongs to $$S$$?

Detecting a cycle in an undirected graph and printing the vertices if there is a cycle, printing no cycle otherwise

Problem: Find an O(E + V) time algorithm that outputs the vertices of a cycle of G, if it exists. If G has no cycles, the algorithm outputs no cycle. So if there is a cycle 1, … 3, 1, it would print 1, …, 3, 1.

So I was thinking of doing a BFS, and if the currently examined vertex’s neighbor v has been visited prior, then there is a cycle. However, I am not sure how I might go about tracking the vertices in order to print. I believe I would have to view the BFS-Tree, but unsure.

Identifying useless vertices in a directed graph

I have a randomly generated directed graph with 3 types of vertices: input, output, and the rest (I’ll call them hidden).

A useless vertex is a hidden vertex which:

• can’t be reached from an input vertex, OR
• can’t reach an output vertex.

For example:

• input = yellow/green
• output = blue
• hidden = white
• useless = red border

Note that:

• cycles and self-loops are allowed
• the graph may be disjoint
• inputs and output nodes are known (i.e. you can determine what type of node an edge connects to and from)

So what do you call this type of problem? Is there any algorithm for this?

I’m looking for more information about this. I have a python script which seems to work. I’m just not sure if it will work for all cases since I don’t fully understand it myself. It was a mix of DFS, trial-and-error, manual hand-checking, and a bunch of if statements.

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.