<p>I am currently working on a property of graphs defined as follows. A graph $G$ is said to be OL-AP iff one of the following two conditions holds:</p>

<ol>
<li>$G$ is an isolated vertex.</li>
<li>$G$ is connected and for every $x \in [1,|V(G)|-1]$ there exists a subset $V_x$ of $V(G)$ with size $x$ such that $G[V_x]$ is connected and $G-V_x$ is OL-AP.</li>
</ol>

<p>Basically, we would like to take some connected parts off a graph whatever their sizes are without disconnecting it. The recursive aspect of this definition should be obvious. <a href="http://www.opuscula.agh.edu.pl/vol31/4/art/opuscula_math_3137.pdf" rel="nofollow">One can refer to this article for some more details</a>.</p>

<p>I have been trying to characterize the complexity of computing this property, but I could not get anything because of the recursivity arising from the definition. </p>

<p>On the one hand, to show that computing this property is in $NP$, I would naively give, as a certificate showing that a graph is OL-AP, a connected part for every possible size of each level. I mean that if my graph has order $n$, I would give the first parts of size $1, ..., n-1$ as well as those of the induced subgraphs, and so on. But I do not think that such a certificate as a polynomial size.</p>

<p>On the other hand, a witness to show that the property is in $co-NP$ would be to give a size $x$ such that we cannot take a connected part with this size off the graph in such a way that the remaining graph is OL-AP. But how the algorithm could check whether a subgraph is OL-AP since this is the property I am dealing with? If such an algorith exists, then dealing with my property would be pointless.</p>

<p>I think that such a problem is in a higher level of the polynomial hierarchy, but I cannot find where because of its recursive aspect. So, any idea or comment is welcomed :) .</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2012-09-07T20:05:34.567Z
you may have already tried this, but it might be useful to build up a dictionary of cases. For example, an edge is OL-AP, and so is any clique, but there are simple trees that are not OL-AP (for example, the spider with a degree three central node connected to three chains each of size n/3)
Suresh Venkat
CC BY-SA 3.0
2012-09-07T22:28:06.600Z
(1) You probably already know this, but it is clearly in PSPACE.  (2) Is there a reason to expect that it is in the polynomial hierarchy, such as a similar problem is in PH?  (3) It would be probably informative if you spell out what “OL-AP” stands for at least once.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-09T13:42:12.227Z
@Suresh: Yeah, if I had to design an algorithm to decide whether a graph is OL-AP, I would proceed like that. But such an algorithm would need to check whether a graph is isomorphic to one graph from the dictionary, and that's a little bit annoying, right?
jbensmai
CC BY-SA 3.0
2012-09-09T13:52:19.403Z
@Tsuyoshi: (2) I must admit that I'm more familiar with time complexity than space complexity. Moreover, this problem can be seen as: for every $x_1$, does there exist a connected part $G[V_{x_1}]$ such that for every $x_2$, does there exist, etc. Thus we have an alternation of quantifiers, and that's why I was thinking of the PH. (1) Could you give me some hints on how you would use a polynomial space in such an algorithm? For a given $x$, I would naively compute every possible connected part with this size in polynomial time and check recursively what's left. Is that all?
jbensmai
CC BY-SA 3.0
2012-09-09T13:57:06.947Z
@Tsuyoshi: (3) OL-AP stands for "online arbitrarily partitionable". Basically, an arbitrarily partitionable graph is a graph you can partition into an arbitrary number of connected parts no matter what their sizes are. In the online version we've been working on, we suppose that the part sizes are not known beforehand but arise one by one. The first part size $x_1$ arrives, and we have to choose the first connected part off the graph. Then $x_2$ is given, and we have to choose the second part in the remaining graph, and so on. The definition I gave comes from this specification.
jbensmai
CC BY-SA 3.0
2012-09-09T15:59:58.977Z
(1) Yes, I was thinking of that algorithm.  (2) Polynomially many alternations of quantifiers characterize PSPACE, just like constantly many alternations characterize PH.  Please check a well-known PSPACE-complete problem called quantified Boolean formula (QBF).  (3) Please add at least “OL-AP stands for ‘online arbitrarily partitionable’” to the question so that people do not have to read comments to understand what it stands for.
Tsuyoshi Ito
<cc.complexity-theory><graph-theory><recursive>
Computational complexity of some recursive property
jbensmai
# Computational complexity of some recursive property

(Asked by: username_0 on 2012-09-07)

I am currently working on a property of graphs defined as follows. A graph $G$ is said to be OL-AP iff one of the following two conditions holds:

1. $G$ is an isolated vertex.
2. $G$ is connected and for every $x \in [1,|V(G)|-1]$ there exists a subset $V\_x$ of $V(G)$ with size $x$ such that $G[V\_x]$ is connected and $G-V\_x$ is OL-AP.

Basically, we would like to take some connected parts off a graph whatever their sizes are without disconnecting it. The recursive aspect of this definition should be obvious. [One can refer to this article for some more details](http://www.opuscula.agh.edu.pl/vol31/4/art/opuscula_math_3137.pdf).

I have been trying to characterize the complexity of computing this property, but I could not get anything because of the recursivity arising from the definition.

On the one hand, to show that computing this property is in $NP$, I would naively give, as a certificate showing that a graph is OL-AP, a connected part for every possible size of each level. I mean that if my graph has order $n$, I would give the first parts of size $1, ..., n-1$ as well as those of the induced subgraphs, and so on. But I do not think that such a certificate as a polynomial size.

On the other hand, a witness to show that the property is in $co-NP$ would be to give a size $x$ such that we cannot take a connected part with this size off the graph in such a way that the remaining graph is OL-AP. But how the algorithm could check whether a subgraph is OL-AP since this is the property I am dealing with? If such an algorith exists, then dealing with my property would be pointless.

I think that such a problem is in a higher level of the polynomial hierarchy, but I cannot find where because of its recursive aspect. So, any idea or comment is welcomed :) .

Thanks in advance!

**Tags:** cc.complexity-theory, graph-theory, recursive

> **Comments:**
> **username_1**: you may have already tried this, but it might be useful to build up a dictionary of cases. For example, an edge is OL-AP, and so is any clique, but there are simple trees that are not OL-AP (for example, the spider with a degree three central node connected to three chains each of size n/3)  
> **username_2**: (1) You probably already know this, but it is clearly in PSPACE.  (2) Is there a reason to expect that it is in the polynomial hierarchy, such as a similar problem is in PH?  (3) It would be probably informative if you spell out what “OL-AP” stands for at least once.  
> **username_0**: @Suresh: Yeah, if I had to design an algorithm to decide whether a graph is OL-AP, I would proceed like that. But such an algorithm would need to check whether a graph is isomorphic to one graph from the dictionary, and that's a little bit annoying, right?  
> **username_0**: @Tsuyoshi: (2) I must admit that I'm more familiar with time complexity than space complexity. Moreover, this problem can be seen as: for every $x_1$, does there exist a connected part $G[V_{x_1}]$ such that for every $x_2$, does there exist, etc. Thus we have an alternation of quantifiers, and that's why I was thinking of the PH. (1) Could you give me some hints on how you would use a polynomial space in such an algorithm? For a given $x$, I would naively compute every possible connected part with this size in polynomial time and check recursively what's left. Is that all?  
> **username_0**: @Tsuyoshi: (3) OL-AP stands for "online arbitrarily partitionable". Basically, an arbitrarily partitionable graph is a graph you can partition into an arbitrary number of connected parts no matter what their sizes are. In the online version we've been working on, we suppose that the part sizes are not known beforehand but arise one by one. The first part size $x_1$ arrives, and we have to choose the first connected part off the graph. Then $x_2$ is given, and we have to choose the second part in the remaining graph, and so on. The definition I gave comes from this specification.  
> **username_2**: (1) Yes, I was thinking of that algorithm.  (2) Polynomially many alternations of quantifiers characterize PSPACE, just like constantly many alternations characterize PH.  Please check a well-known PSPACE-complete problem called quantified Boolean formula (QBF).  (3) Please add at least “OL-AP stands for ‘online arbitrarily partitionable’” to the question so that people do not have to read comments to understand what it stands for.  

---

## 0 answers

