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.

  • $\begingroup$ Can you share where or how you encountered this problem? $\endgroup$ – John L. Dec 19 '18 at 5:56
  • 1
    $\begingroup$ What does subgraph mean here? Are you allowed to remove only vertices, or both edges and vertices, or perhaps only edges? $\endgroup$ – Yuval Filmus Dec 19 '18 at 6:36
  • 1
    $\begingroup$ 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 $\endgroup$ – TrostAft Dec 19 '18 at 7:06
  • 1
    $\begingroup$ 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. $\endgroup$ – TrostAft Dec 19 '18 at 7:12
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.