<p>Sorry this is too long for a comment :)</p>

<p>Maybe the complete graph is a trivial graph but it illustrates that e.g. graphs $G = (V,E)$ with large cliques of size $\Omega(\vert V \vert)$ also have exponentially many $0$ obstructed induced subgraphs. And I don't think that $N$ can be easily computed in such graphs. </p>

<p>I also think that 3-regularity doesnt help: Let $A$, $B$ be a partition of $V$ each of size $\vert V \vert /2$. The induced subgraph consisting of nodes from either $A$ or $B$ is a cycle and the edges between $A$ and $B$ form a perfect matching. This graph is $3$-regular and every induced subgraph consisting of at least all nodes in $A$ or all nodes in $B$ is $0$ obstructed.</p>

CC BY-SA 3.0
2013-05-24T14:24:04.420Z
2013-05-24T14:24:04.420Z
Marc Bury
<p>Let $G=(V,E)$ be a $3$-regular graph. Let a vertex induced subgraph of $G$ be $i$ extendible if and only if it has both the following properties:  </p>

<ul>
<li>It has no isolated vertices.</li>  
<li>It is possible to add $i$ vertices to it without implying (by the very definition of vertex induced subgraph) the introduction of any new edge (in other words, it is possible to add $i$ isolated vertices).</li>  
</ul>

<p>Clearly, if a vertex induced subgraph is $i$ extendible it is also $j$ extendible for any $j &lt; i$. </p>

<p>Now, let a vertex induced subgraph of $G$ be $i$ obstructed if and only if it is $i$ extendible but not $i+1$ extendible.</p>

<p>I'm interested in $0$ obstructed vertex induced subgraphs.</p>

<blockquote>
  <p><strong>Questions</strong>  </p>
  
  <ol>
  <li>Let $N$ be the number of $0$ obstructed vertex induced subgraphs of $G$. Is $N$ polynomially bounded in the size of $G$? I believe yes (and I've made some empirical tests that seem to suggest so), but so far I was unable to prove it.</li>
  <li>If the answer to question 1. is no, is it nevertheless possible to compute $N$ in polynomial time?  </li>
  <li>If the answer to question 2. is no, is it nevertheless possible to compute $N\ mod\ 2$ in polynomial time?</li>
  </ol>
</blockquote>

<p>I'm curious to know if anyone already dealt with $0$ obstructed vertex induced subgraphs previously, how he encountered them in the first place, and what is known about them.  </p>

<p>Another way to express question 1. is the following: which is the maximum number $\alpha$ of vertices that can be removed from $G$ without making it $1$ extendible? My sensation is that $\alpha \in O( log\ |V| )$, as I'm inclined to believe that $\alpha$ is strongly related to the diameter of $G$.</p>

CC BY-SA 3.0
2013-05-24T13:34:42.740Z
Maybe I miss something, but I think every induced subgraph of a complete graph is 0 obstructed, i.e., $N$ is not polynomially bounded.
Marc Bury
CC BY-SA 3.0
2013-05-24T13:56:14.280Z
@MarcGillé: You are absolutely right in saying that my conjecture fails with the complete graph. However, such class is trivial and thus uninteresting. Let us focus on non trivial classes (by non trivial I mean those where computing $N$ is non trivial), like $3$-regular graphs. I've clarified the beginning of the question accordingly.
Giorgio Camerani
CC BY-SA 3.0
2013-05-25T14:40:25.113Z
I presume you mean with your second condition that for the induced subgraph $G[V']$ (where $V' \subseteq V$), there should be some $V'' \supseteq V'$ such that $|V''| = |V'| + i$ and the induced subgraph $G[V'']$ contains the same edges as $G[V']$?
András Salamon
CC BY-SA 3.0
2013-05-25T16:29:26.570Z
@AndrásSalamon: Exactly, you are right.
Giorgio Camerani
<cc.complexity-theory><graph-theory><co.combinatorics>
Zero Obstructed vertex induced subgraphs
Giorgio Camerani
# Zero Obstructed vertex induced subgraphs

(Asked by: username_0 on 2013-05-24)

Let $G=(V,E)$ be a $3$-regular graph. Let a vertex induced subgraph of $G$ be $i$ extendible if and only if it has both the following properties:

* It has no isolated vertices.
* It is possible to add $i$ vertices to it without implying (by the very definition of vertex induced subgraph) the introduction of any new edge (in other words, it is possible to add $i$ isolated vertices).

Clearly, if a vertex induced subgraph is $i$ extendible it is also $j$ extendible for any $j < i$.

Now, let a vertex induced subgraph of $G$ be $i$ obstructed if and only if it is $i$ extendible but not $i+1$ extendible.

I'm interested in $0$ obstructed vertex induced subgraphs.

> **Questions**
>
> 1. Let $N$ be the number of $0$ obstructed vertex induced subgraphs of $G$. Is $N$ polynomially bounded in the size of $G$? I believe yes (and I've made some empirical tests that seem to suggest so), but so far I was unable to prove it.
> 2. If the answer to question 1. is no, is it nevertheless possible to compute $N$ in polynomial time?
> 3. If the answer to question 2. is no, is it nevertheless possible to compute $N\ mod\ 2$ in polynomial time?

I'm curious to know if anyone already dealt with $0$ obstructed vertex induced subgraphs previously, how he encountered them in the first place, and what is known about them.

Another way to express question 1. is the following: which is the maximum number $\alpha$ of vertices that can be removed from $G$ without making it $1$ extendible? My sensation is that $\alpha \in O( log\ |V| )$, as I'm inclined to believe that $\alpha$ is strongly related to the diameter of $G$.

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics

> **Comments:**
> **username_1**: Maybe I miss something, but I think every induced subgraph of a complete graph is 0 obstructed, i.e., $N$ is not polynomially bounded.  
> **username_0**: @MarcGillé: You are absolutely right in saying that my conjecture fails with the complete graph. However, such class is trivial and thus uninteresting. Let us focus on non trivial classes (by non trivial I mean those where computing $N$ is non trivial), like $3$-regular graphs. I've clarified the beginning of the question accordingly.  
> **username_2**: I presume you mean with your second condition that for the induced subgraph $G[V']$ (where $V' \subseteq V$), there should be some $V'' \supseteq V'$ such that $|V''| = |V'| + i$ and the induced subgraph $G[V'']$ contains the same edges as $G[V']$?  
> **username_0**: @AndrásSalamon: Exactly, you are right.  

---

## 1 answers

### Answer by username_1 on 2013-05-24. Score: 4

Sorry this is too long for a comment :)

Maybe the complete graph is a trivial graph but it illustrates that e.g. graphs $G = (V,E)$ with large cliques of size $\Omega(\vert V \vert)$ also have exponentially many $0$ obstructed induced subgraphs. And I don't think that $N$ can be easily computed in such graphs.

I also think that 3-regularity doesnt help: Let $A$, $B$ be a partition of $V$ each of size $\vert V \vert /2$. The induced subgraph consisting of nodes from either $A$ or $B$ is a cycle and the edges between $A$ and $B$ form a perfect matching. This graph is $3$-regular and every induced subgraph consisting of at least all nodes in $A$ or all nodes in $B$ is $0$ obstructed.


---

