P496: Enumeration of all minimal path-conjunctions of an undirected graph.

P496: Enumeration of all minimal path-conjunctions of an undirected graph.

Input:

An undirected graph $G=(V, E)$ and $\mathcal{P} = \{(s_i, t_i ) \in V \times V \mid i \in [k] \}$.

Output:

All minimal path-conjunction of $G$.

Complexity:

Incremental polynomial time.

Comment:

A minimal path-conjunction is a minimal set of edges $E'$ such that any pair of vertices in $\mathcal{P}$ is connected in $(V, E')$.

Reference:

[Khachiyan2007] (Bibtex)