×

Set graphs. II. Complexity of set graph recognition and similar problems. (English) Zbl 1298.05146

Summary: A graph \(G\) is said to be a set graph if it admits an acyclic orientation that is also extensional, in the sense that the out-neighborhoods of its vertices are pairwise distinct. Equivalently, a set graph is the underlying graph of the digraph representation of a hereditarily finite set. In this paper, we continue the study of set graphs and related topics, focusing on computational complexity aspects. We prove that set graph recognition is NP-complete, even when the input is restricted to bipartite graphs with exactly two leaves. The problem remains NP-complete if, in addition, we require that the extensional acyclic orientation be also slim, that is, that the digraph obtained by removing any arc from it is not extensional.Our approach in fact allows us to also show that the counting variants of the above problems are #P-complete, and prove similar complexity results for problems related to a generalization of extensional acyclic digraphs, the so-called hyper-extensional digraphs, which were proposed by Aczel to describe hypersets. Our proofs are based on reductions from variants of the Hamiltonian Path problem. We also consider a variant of the well-known notion of a separating code in a digraph, the so-called open-out-separating code, and show that it is NP-complete to determine whether an input extensional acyclic digraph contains an open-out-separating code of given size.
For Part I see [M. Milanič and A. I. Tomescu, Discrete Appl. Math. 161, No. 4–5, 677–690 (2013; Zbl 1259.05143)].

MSC:

05C20 Directed graphs (digraphs), tournaments
05C62 Graph representations (geometric and intersection representations, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 1259.05143

Software:

AEtnaNova; SETL; Referee
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cantone, D.; Ferro, A.; Omodeo, E. G., Computable Set Theory, Oxford Science Publications of International Series of Monographs on Computer Science, vol. 6 (1989), Clarendon Press · Zbl 0755.03024
[2] Schwartz, J.; Dewar, R.; Dubinsky, E.; Schonberg, E., Programming with Sets: An Introduction to SETL, Texts and Monographs in Computer Science (1986), Springer-Verlag: Springer-Verlag New York · Zbl 0604.68001
[3] Dovier, A.; Omodeo, E. G.; Pontelli, E.; Rossi, G., \(\{\log \}\): a language for programming in logic with finite sets, J. Log. Program., 28, 1, 1-44 (1996) · Zbl 0874.68056
[4] Dovier, A.; Piazza, C.; Pontelli, E.; Rossi, G., Sets and constraint logic programming, ACM Trans. Program. Lang. Syst., 22, 5, 861-931 (2000)
[5] Omodeo, E. G.; Cantone, D.; Policriti, A.; Schwartz, J. T., A computerized referee, (Stock, O.; Schaerf, M., Reasoning, Action and Interaction in AI Theories and Systems - Essays Dedicated to Luigia Carlucci Aiello. Reasoning, Action and Interaction in AI Theories and Systems - Essays Dedicated to Luigia Carlucci Aiello, Lecture Notes in Artificial Intelligence, vol. 4155 (2006), Springer), 117-139
[6] Schwartz, J. T.; Cantone, D.; Omodeo, E. G., Computational Logic and Set Theory (2011), Springer
[7] Levy, A., Basic Set Theory (1979), Springer: Springer Berlin · Zbl 0404.04001
[8] Milanič, M.; Tomescu, A. I., Set graphs. I. Hereditarily finite sets and extensional acyclic orientations, Discrete Appl. Math., 161, 4-5, 677-690 (2013) · Zbl 1259.05143
[9] Omodeo, E. G.; Tomescu, A. I., Set graphs. III. Proof pearl: claw-free graphs mirrored into transitive hereditarily finite sets, J. Automat. Reason., 52, 1, 1-29 (2014), see also · Zbl 1315.68223
[10] Aczel, P., Non-Well-Founded Sets, CSLI Lecture Notes, vol. 14 (1988) · Zbl 0668.04001
[11] Dovier, A.; Piazza, C.; Policriti, A., An efficient algorithm for computing bisimulation equivalence, Theoret. Comput. Sci., 311, 1-3, 221-256 (2004) · Zbl 1070.68101
[12] Policriti, A.; Tomescu, A. I., Well-quasi-ordering hereditarily finite sets, Int. J. Comput. Math., 90, 6, 1278-1291 (2013) · Zbl 1273.05091
[13] van Benthem, J., Model correspondence theory (1976), Universiteit van Amsterdam, Instituut voor Logica en Grondslagenonderzo ek van Exacte Wetenschappen, Ph.D. thesis
[14] Park, D., Concurrency and automata on infinite sequences, (Deussen, P., Proc. 5th Internat. Conf. on Theoretical Computer Science. Proc. 5th Internat. Conf. on Theoretical Computer Science, Lecture Notes in Computer Science LNCS/LNAI, vol. 104 (1981)), 167-183
[15] Milner, R., Operational and algebraic semantics of concurrent processes, (Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics (1990)), 1201-1242 · Zbl 0900.68217
[16] Clarke, E. M.; Grumberg, O.; Peled, D. A., Model Checking (1999), The MIT Press: The MIT Press Cambridge, MA
[17] Omodeo, E. G., Bisimilarity, hypersets, and stable partitioning: a survey, Rend. Istit. Mat. Univ. Trieste, 42, 211-234 (2010) · Zbl 1245.03072
[18] Kanellakis, P. C.; Smolka, S. A., CCS expressions, finite state processes, and three problems of equivalence, Inform. and Comput., 86, 1, 43-68 (1990) · Zbl 0705.68063
[19] Paige, R.; Tarjan, R. E., Three partition refinement algorithms, SIAM J. Comput., 16, 6, 973-989 (1987) · Zbl 0654.68072
[20] Barwise, J.; Moss, L. S., Vicious Circles, CSLI Lecture Notes (1996), CSLI Publications/Center for the Study of Language & Information: CSLI Publications/Center for the Study of Language & Information Stanford, CA · Zbl 0865.03002
[21] Garey, M. R.; Johnson, D. S., Computers and Intractability. Guide to the Theory of NP-Completeness (1990), W.H. Freeman & Co.: W.H. Freeman & Co. New York, NY, USA
[22] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049
[23] Dyer, M.; Frieze, A.; Jerrum, M., Approximately counting Hamilton paths and cycles in dense graphs, SIAM J. Comput., 27, 5, 1262-1272 (1998) · Zbl 0907.68111
[24] Haynes, T. W.; Hedetniemi, S.; Slater, P., Fundamentals of Domination in Graphs, Pure and Applied Mathematics (1998), Marcel Dekker, CRC · Zbl 0890.05002
[25] Foucaud, F.; Naserasr, R.; Parreau, A., Characterizing extremal digraphs for identifying codes and extremal cases of Bondy’s theorem on induced subsets, Graphs Combin., 29, 3, 463-473 (2013) · Zbl 1267.05132
[26] Karpovsky, M.; Chakrabarty, K.; Levitin, L., On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44, 599-611 (1998) · Zbl 1105.94342
[27] Henning, M.; Yeo, A., Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs, Graphs Combin. (2014), in press · Zbl 1298.05236
[28] Seo, S. J.; Slater, P. J., Open neighborhood locating-dominating sets, Australas. J. Combin., 46, 109-119 (2010) · Zbl 1196.05067
[29] Seo, S. J.; Slater, P. J., Open neighborhood locating-dominating in trees, Discrete Appl. Math., 159, 6, 484-489 (2011) · Zbl 1209.05053
[30] Charbit, E.; Charon, I.; Cohen, G.; Hudry, O., Discriminating codes in bipartite graphs, Electron. Notes Discrete Math., 26, 29-35 (2006) · Zbl 1291.05152
[31] Charon, I.; Cohen, G.; Hudry, O.; Lobstein, A., Discriminating codes in (bipartite) planar graphs, European J. Combin., 29, 1353-1364 (2008) · Zbl 1143.94024
[32] Bondy, J. A., Induced subsets, J. Combin. Theory Ser. B, 12, 201-202 (1972) · Zbl 0211.56901
[33] de Bontridder, K. M.J.; Halldórsson, B. V.; Halldórsson, M. M.; Hurkens, C. A.J.; Lenstra, J. K.; Ravi, R.; Stougie, L., Approximation algorithms for the test cover problem, Math. Program., Ser. B, 98, 1-3, 477-491 (2003) · Zbl 1160.90646
[34] Moret, B.; Shapiro, H., On minimizing a set of tests, SIAM J. Sci. Stat. Comput., 6, 4, 983-1003 (1985)
[35] Charon, I.; Hudry, O.; Lobstein, A., Identifying and locating-dominating codes: NP-completeness results for directed graphs, IEEE Trans. Inform. Theory, 48, 8, 2192-2200 (2002) · Zbl 1062.94056
[36] Charon, I.; Hudry, O.; Lobstein, A., Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoret. Comput. Sci., 290, 2109-2120 (2003) · Zbl 1044.68066
[37] Cohen, G.; Honkala, I.; Lobstein, A.; Zémor, G., On identifying codes, (Proc. DIMACS Workshop on Codes and Association Schemes. Proc. DIMACS Workshop on Codes and Association Schemes, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 56 (2001)), 97-109 · Zbl 0990.94036
[38] Milanič, M.; Tomescu, A. I., Set graphs. IV. Further connections with claw-freeness, Discrete Appl. Math., 174, 113-121 (2014) · Zbl 1298.05147
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.