Abstract
Analterable digraph is a digraph with a subset of its edges marked alterable and their orientations left undecided. We say that an alterable digraph has an invariant ofk on the length of the longest circuit if it has a circuit of length at leastk regardless of the orientations over its alterable edges. Computing the maximum invariant on the length of the longest circuit in an alterable digraph is aglobal optimization problem. We show that it is hard to approximate the global optimal solution for the maximum invariant problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M. Ajtai (1987), Recursive Construction for 3-Regular Expanders, inProc. 28th IEEE Symp. on Foundations of Computer Science, pp. 295–304.
A. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy (1992), Proof Verification and Hardness of Approximation Problems, inProc. 33rd IEEE Symp. on Foundations of Computer Science, pp. 14–23.
A. Condon, J. Feigenbaum, C. Lund, and P. Shor (1993), Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions, inProc. 25thACM Symp. on Theory of Computing, pp. 305–314.
M.R. Garey and D.S. Johnson (1979),Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company.
K.-I. Ko and C.-L. Lin (1994), Non-Approximability in the Polynomial-Time Hierarchy, Technical Report 94-2, Dept. of Computer Science, SUNY at Stony Brook.
K.-I. Ko and C.-L. Lin (1995), On the Complexity of min-max Optimization Problems and Their Approximation, in D.-Z. Du and P.M. Pardalos, eds.,Minimax and Applications, pp. 213–233, Kluwer, Boston.
M. Kiwi, C. Lund, A. Russell, D. Spielman, and R. Sundaram (1994), Alteration in Interaction, inProc. 9th IEEE Structure in Complexity Theory Conference, pp. 294–303.
D. Karger, R. Motwani, and G.D.S. Ramkumar (1993), On Approximating the Longest Path in a Graph, inAlgorithms and Data Structures, Proc. of the 3rd Workshop, WADS'93, Lecture Notes in Computer Science 709, pp. 421–432, Springer-Verlag.
C. Lund and M. Yannakakis (1993), On the Hardness of Approximating Maximization Problems, inProc. 25th ACM Symp. on Theory of Computing, pp. 286–293.
C.H. Papadimitriou and M. Yannakakis (1991), Optimization, Approximation, and Complexity Classes,J. Comput. System Sci. 43, 425–440.
C.H. Papadimitriou and M. Yannakakis (1993), The Traveling Salesman Problem with Distances One and Two,Math. Oper. Res. 18(1), 1–11.
L.J. Stockmeyer (1977), The Polynomial-Time Hierarchy,Theoret. Comput. Sci. 3, 1–22.
Author information
Authors and Affiliations
Additional information
Research supported in part by NSF grant CCR 9121472.
Rights and permissions
About this article
Cite this article
Ko, KI., Lin, CL. On the longest circuit in an alterable digraph. J Glob Optim 7, 279–295 (1995). https://doi.org/10.1007/BF01279452
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01279452