1
$\begingroup$

I was reading the paper Computing Small Search Numbers in Linear Time by Bodlaender et. al. and I noticed a notation that I had never seen before. On page three it says:

$X$ is nice if $|X_1| = 1$ and $\forall_{2 \leq i \leq |X|} |(X_i \Leftrightarrow X_{i-1}) \cup (X_{i-1} \Leftrightarrow X_i)| = 1 $

What does the logical equivalence symbol mean when it is used between sets? Does this indicate a bijection?

$\endgroup$
1
  • 1
    $\begingroup$ A it before that the paper uses $\max_{1\le i\le |X|}\{|X_i|\Leftrightarrow 1\}$, which makes little sense as well (logical equivalebde of numbers? Maximum over singleton sets contaiing a truth value? $\endgroup$ – Hagen von Eitzen Jul 14 '17 at 18:17
6
$\begingroup$

Seeing the other uses of that symbol in that particular paper, it looks like something went wrong with the font in that paper. I guess many occurrences of $\iff$ should be $-$, and in your particular case it then means set-difference.

A compelling hint that this is the error, is the definition of linear width: in the abstract it uses a $-$, but in the body a $\iff$ at the same place.

$\endgroup$
2
  • 2
    $\begingroup$ ... and so $(X_i\Leftrightarrow X_{i-1}\cup(X_{i-1}\Leftrightarrow X_{i})$ turns out to be the symmetric set difference $X_i\mathop\Delta X_{i-1}$ ... $\endgroup$ – Hagen von Eitzen Jul 14 '17 at 18:22
  • 1
    $\begingroup$ This would make sense since pathwidth is $max\{|X_i|\} - 1$ by the traditional definitions. That also makes sense with niceness, as then the definition simply becomes a symmetric difference. $\endgroup$ – Jabbath Jul 14 '17 at 18:22

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.