patternMinor
K Perfect Subgraph Algorithm
Viewed 0 times
algorithmsubgraphperfect
Problem
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.
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.
Solution
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:
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.
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.
Context
StackExchange Computer Science Q#101768, answer score: 2
Revisions (0)
No revisions yet.