Orienting Graphs to Optimize Reachability
<|reference_start|>Orienting Graphs to Optimize Reachability: The paper focuses on two problems: (i) how to orient the edges of an undirected graph in order to maximize the number of ordered vertex pairs (x,y) such that there is a directed path from x to y, and (ii) how to orient the edges so as to minimize the number of such pairs. The paper describes a quadratic-time algorithm for the first problem, and a proof that the second problem is NP-hard to approximate within some constant 1+epsilon > 1. The latter proof also shows that the second problem is equivalent to ``comparability graph completion''; neither problem was previously known to be NP-hard.<|reference_end|>
@article{hakimi2002orienting,
    title={Orienting Graphs to Optimize Reachability},
    author={S. L. Hakimi, E. Schmeichel, Neal E. Young},
    journal={Information Processing Letters 63:229-235 (1997)},
    year={2002},
    doi={10.1016/S0020-0190(97)00129-4},
    archivePrefix={arXiv},
    eprint={cs/0205042},
    primaryClass={cs.DS cs.DM}
}