# K Perfect Subgraph Algorithm

I have a problem that goes as follows:

Problem. Suppose we have undirected graph $$G$$. We denote a $$k$$-perfect graph as a graph such that $$\forall v \in G, degree(v) = k$$. Present an algorithm that constructs a subgraph $$H$$ such that $$H$$ is $$k$$-perfect, for $$k$$ maximized. Do this in $$\theta(|V| + |E|)$$ time.

I was thinking that perhaps we could borrow techniques from a BFS based topological sort, to work on the "fringe" vertices and continuously cut inwards. Formally, we would identify vertices with small degree and cut them out, but I don't know how to make sure that this doesn't accidentally take out a vertex that would create a $$k$$ perfect graph of larger $$k$$, and how to do this without the check for if we're done costing $$\theta(V)$$.

Have you got any ideas?

Note that we define a subgraph here as: $$H = (V', E')$$ is a subgraph of $$G = (V,E)$$ if $$V' \subseteq V$$ and $$E' \subseteq E$$. Basically we are allowed to remove both edges and vertices.

• Can you share where or how you encountered this problem? – Apass.Jack Dec 19 '18 at 5:56
• What does subgraph mean here? Are you allowed to remove only vertices, or both edges and vertices, or perhaps only edges? – Yuval Filmus Dec 19 '18 at 6:36
• I have just learned that my terminology for $k$ perfect is called $k$ regular in the normal nomenclature. Looking up this problem under that name right now – TrostAft Dec 19 '18 at 7:06
• After looking this up, this problem seems to be out of the scope of the course, which means I must have copied down this problem wrong. I will email professor and update with answer. – TrostAft Dec 19 '18 at 7:12
• Indeed -- the problem as stated is NP-hard (F. Cheah & D.G. Corneil, 1990). So yes, the formulation was probably different, unless your professor is sneakily trying to have you prove P = NP. Incidentally, the problem remains NP-hard under any of the 3 possibile notions of subgraph. – Vincenzo Dec 19 '18 at 14:26

This problem is NP-hard, meaning it's very unlikely that any algorithm exists that can solve every instance in polynomial (let alone linear!) time. I'll show this by reducing the NP-hard problem Clique to this problem. In Clique, we are given an undirected graph $$F$$ and a number $$K$$, and the task is to determine whether or not $$F$$ contains a clique (complete subgraph) with at least $$K$$ vertices. The strategy will be to add universal vertices to $$F$$ -- that is, new vertices that are connected to all existing vertices -- and show that doing so grows the size of cliques in $$F$$, but does not grow the size of any other regular subgraphs in $$F$$.

Let there be $$n$$ vertices in $$F$$. We will construct an instance $$(G, k)$$ of your problem from the given instance $$(F, K)$$ of the Clique problem:

• $$G$$ is formed by adding $$n+1$$ new vertices to $$F$$ that are adjacent to each other and to every vertex in $$F$$.
• $$k = K + n$$.

First we show that if there is a clique in $$F$$ of size at least $$K$$, then there is a regular subgraph with degree at least $$K+n$$ in $$G$$. Clearly a clique of $$K+n+1$$ vertices can be formed by including the $$K$$ clique vertices in $$F$$ and all $$n+1$$ new vertices. A clique containing $$i$$ vertices is regular with degree $$i-1$$, so this clique is regular of degree at least $$K+n$$. Thus a YES answer to the given Clique problem implies a YES answer to the constructed instance of your problem.

Now we show that if there is a regular subgraph $$H$$ with degree at least $$K+n$$ in $$G$$, then there is a clique of size at least $$K$$ in $$F$$. First observe that this $$H$$ must include at least one of the $$n+1$$ newly added universal vertices, since the largest degree obtainable using just the original $$n$$ vertices of $$F$$ is $$n-1 < n+K$$. The following lemma is key:

Lemma: If a regular graph $$I$$ contains a universal vertex, then it must be a clique.

Proof: Let $$c \ge 1$$ be the number of universal vertices in $$I$$, and let $$a$$ be the number of other vertices. Since $$I$$ is regular, it must be that every non-universal vertex has the same degree $$c+d$$ for some $$d$$ -- that is, removing the $$c$$ universal vertices from $$I$$ must leave a $$d$$-regular subgraph, which I'll call $$I'$$. Again, since $$I$$ is regular, we must have that the degree $$c-1+a$$ of each universal vertex in $$I$$ is equal to the degree $$c+d$$ of the other vertices. But this implies $$a-1=d$$, i.e., $$I'$$ is a clique of $$a$$ vertices, and thus $$I$$ is a clique of $$c+a$$ vertices.

Since $$H$$ contains at least one universal vertex, by the above lemma, it must be a clique of size at least $$K+n+1$$. Since we only added $$n+1$$ universal vertices to $$G$$, at least $$K$$ of the vertices in $$H$$ must have come from the original graph $$F$$, where they also form a clique since every induced subgraph of a clique is a clique. Thus a YES answer to the constructed instance of your problem implies a YES answer to the given Clique problem.

Since a YES answer to one problem instance implies a YES answer to the other, it follows that a NO answer to one problem instance also implies a NO answer to the other. Thus any algorithm that could solve your problem could also solve Clique. Since constructing the instance of your problem requires only polynomial time, a polynomial-time algorithm that could solve your problem could also solve Clique in polynomial time.