What does it mean to "place gadgets in parallel"?

45 Views Asked by At

I'm reading this paper, and in section 3, authors use gadgets in the reductions, namely paths. At some point, they use words 'placing $\Gamma$, $\Gamma^\pi$ in parallel [...] yields a composite gadget $\Gamma^*$'. ($\Gamma$, $\Gamma^\pi$ are gadgets).

I'm still new to the topic and they haven't elaborated further on what it exactly means. Is this more general construction (the parallel construction)?

1

There are 1 best solutions below

0
On

Each gadget has two terminal vertices: $1$ and $L$. When the authors write

Placing $\Gamma$ and $\Gamma^\pi$ in parallel, identifying the terminals, yields a composite gadget $\Gamma^*$

they mean to take the two gadgets $\Gamma$ and $\Gamma^\pi$, combine $\Gamma$'s terminal $1$ with $\Gamma^\pi$'s terminal $1$, and combine $\Gamma$'s terminal $L$ with $\Gamma^\pi$'s terminal $L$.

The clause "identifying the terminals" is there to help explain what "Placing in parallel" is supposed to accomplish, but it is probably still not clear if you haven't encountered the notions of "parallel composition" and "series composition" of a series-parallel graph. Wikipedia has a diagram:

enter image description here

Here, "parallel composition" is what we're doing, except that we haven't called the terminal $s$ and $t$.