Packing non-zero \(A\)-paths in group-labelled graphs (Q879161): Difference between revisions

Let \(G=(V,E)\) be an oriented graph whose edges are labelled by the elements of a group \(\Gamma\) and let \(A\subseteq V\). An \(A\)-path is a path whose ends are both in \(A\). The weight of a path \(P\) in \(G\) is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in \(P\). (If \(\Gamma\) is not abelian, we sum the labels in their order along the path.) The authors give a connection of this problem to some other problems studied in the literature. The authors prove that for any integer \(k\), either there are \(k\)-vertex-disjoint \(A\)-paths each of non-zero weight, or there is a set of at most \(2k-2\) vertices that meets each non-zero \(A\)-path.