<p>Consider a poset $P = (V,A)$. We may define a <em>path structuring</em> of $P$ as a chain $\Sigma$ of the form $X_0 \subset X_1 \subset \ldots \subset X_n$ where :</p>

<p>(i) for every $x \in V$, the set $\{ i \in [n] : x \in V_i \}$ is an interval,</p>

<p>(ii) for every $i$ we have $X_{i+1}$ of the form $X_i + \{x\}$ or $X_i - \{x\}$,</p>

<p>(iii) for every $i &lt; j$, $P$ contains no backward arcs joining $X_j - X_i$ to $X_i - X_j$.</p>

<p>The <em>width</em> of $\Sigma$ is defined as $w(\Sigma) = \max_i |X_i|$, and the <em>path-width</em> of $P$ is defined as the minimum width of a path structuring of $P$. In particular, the path-width is always smaller than the width (defined as the size of a largest antichain).</p>

<p>The following questions seem natural in this respect:</p>

<ol>
<li><p>is it possible to define a corresponding notion of tree-width that is well-behaved? E.g. we would expect forest posets to have tw at most 1, and series-parallel posets to have tw at most 2.</p></li>
<li><p>is it possible to get a width measure that is algorithmically useful? A possible application would be the <em>counting of linear extensions</em>: it is feasible in $n^{O(w)}$ for a poset of width $w$, but the extension to path-width / tree-width seems unlikely at this point.</p></li>
</ol>

CC BY-SA 3.0
2014-04-25T07:01:59.413Z
Judging from your definitions, you probably want $V_j := \bigcup_{k \leqslant j} X_k$ and $V_j \subset V_{j+1}$. Anyway: every poset describes a directed acyclic simple graph (omitting the self-loops). If the graph is finite, it also has a transitive reduction. Your path structuring is then effectively the path decomposition which is standard in graph theory, and one may consider tree decompositions instead if one wishes.
Niel de Beaudrap
CC BY-SA 3.0
2014-04-25T08:07:38.500Z
The purpose of this site is, essentially, for us to help each other with research. The [Help Center](http://cstheory.stackexchange.com/help/on-topic) says, "You should only post questions you're actually seriously thinking about." If you had seriously thought about these questions before posting them, you would know whether or not they were natural, rather than just saying that they "seem natural". It seems to me that you are just posting questions here because you want to give people questions to answer, not because you actually want the answers. Please stop doing this.
David Richerby
CC BY-SA 3.0
2014-04-25T08:31:44.160Z
I admit that you're right, however I'm not the only one to do this, e.g. there are several questions related to separation of complexity classes which I doubt the author is serious about. As I said earlier I was just trying to suggest some directions for research that (i) I consider fruitful but (ii) I don't have time to investigate currently. I'm not aware of any other place that would better suit this purpose.
NisaiVloot
CC BY-SA 3.0
2014-04-25T10:55:21.407Z
The open problems section of your next paper?
Tyson Williams
CC BY-SA 3.0
2014-04-25T11:10:23.760Z
I canot tell if this is ironic, but given the delays due to reviews & revisions I'd rather post here first where I have the possibility of getting a larger audience & targeting different topics. I will consider your suggestion in due course though..
NisaiVloot
CC BY-SA 3.0
2014-04-25T12:52:13.200Z
@DavidRicherby: perhaps you could take this to Meta?
András Salamon
CC BY-SA 3.0
2014-04-27T01:30:23.440Z
Would you please add an example for a poset satisfying the conditions. I couldn't understand the first condition. A pointer to what you mean by (i) would be highly appreciated.
seteropere
<counting-complexity><partial-order>
Is there a useful notion of pathwidth-treewidth for posets?
NisaiVloot
# Is there a useful notion of pathwidth-treewidth for posets?

(Asked by: username_0 on 2014-04-25)

Consider a poset $P = (V,A)$. We may define a *path structuring* of $P$ as a chain $\Sigma$ of the form $X\_0 \subset X\_1 \subset \ldots \subset X\_n$ where :

(i) for every $x \in V$, the set $\{ i \in [n] : x \in V\_i \}$ is an interval,

(ii) for every $i$ we have $X\_{i+1}$ of the form $X\_i + \{x\}$ or $X\_i - \{x\}$,

(iii) for every $i < j$, $P$ contains no backward arcs joining $X\_j - X\_i$ to $X\_i - X\_j$.

The *width* of $\Sigma$ is defined as $w(\Sigma) = \max\_i |X\_i|$, and the *path-width* of $P$ is defined as the minimum width of a path structuring of $P$. In particular, the path-width is always smaller than the width (defined as the size of a largest antichain).

The following questions seem natural in this respect:

1. is it possible to define a corresponding notion of tree-width that is well-behaved? E.g. we would expect forest posets to have tw at most 1, and series-parallel posets to have tw at most 2.
2. is it possible to get a width measure that is algorithmically useful? A possible application would be the *counting of linear extensions*: it is feasible in $n^{O(w)}$ for a poset of width $w$, but the extension to path-width / tree-width seems unlikely at this point.

**Tags:** counting-complexity, partial-order
> **Comments:**
> **username_1**: Judging from your definitions, you probably want $V_j := \bigcup_{k \leqslant j} X_k$ and $V_j \subset V_{j+1}$. Anyway: every poset describes a directed acyclic simple graph (omitting the self-loops). If the graph is finite, it also has a transitive reduction. Your path structuring is then effectively the path decomposition which is standard in graph theory, and one may consider tree decompositions instead if one wishes.  
> **username_2**: The purpose of this site is, essentially, for us to help each other with research. The [Help Center](http://cstheory.stackexchange.com/help/on-topic) says, "You should only post questions you're actually seriously thinking about." If you had seriously thought about these questions before posting them, you would know whether or not they were natural, rather than just saying that they "seem natural". It seems to me that you are just posting questions here because you want to give people questions to answer, not because you actually want the answers. Please stop doing this.  
> **username_0**: I admit that you're right, however I'm not the only one to do this, e.g. there are several questions related to separation of complexity classes which I doubt the author is serious about. As I said earlier I was just trying to suggest some directions for research that (i) I consider fruitful but (ii) I don't have time to investigate currently. I'm not aware of any other place that would better suit this purpose.  
> **username_3**: The open problems section of your next paper?  
> **username_0**: I canot tell if this is ironic, but given the delays due to reviews & revisions I'd rather post here first where I have the possibility of getting a larger audience & targeting different topics. I will consider your suggestion in due course though..  
> **username_4**: @DavidRicherby: perhaps you could take this to Meta?  
> **username_5**: Would you please add an example for a poset satisfying the conditions. I couldn't understand the first condition. A pointer to what you mean by (i) would be highly appreciated.  

---

## 0 answers

