Minimal-to-Maximal Conversion Search Is Not Output-Polynomial: Input Hypergraphs, Results and Code

This record contains the following artifacts of the paper Minimal-to-Maximal Conversion Search Is Not Output-Polynomial input-hypergraphs.zipcontains the input files for the experiments. input-hypergraph-stats.zip contains some computed metrics for the used inputs hypergraphs as well as their transversal hypergraphs. input-hypergraph-transversals.zip contains the transversals of all used input hypergraphs. experiments-repo.zip contains the code for the experiments including an implementation of MMCS (thanks to Max Göttlicher for providing it) and our visualization scripts. Read its README.md if you want to run the experiments yourself. You can also view the code in our GitLab repository. results.zip contains the obtained unprocessed results as a CSV file. Read theREADME.md of experiments-repo.zip to undertand the format. Input Hypergraphs The file all.toml in input-hypergraphs.zip acts as configuration file for the experiments. It specifies which hypergraphs we included with how many runs. Subfolder HPIValid A unique column combination in a database is a set of columns, whose value combinations are without duplicates. One can construct a hypergraph for a database, such that its hitting sets are exactly the unique column combinations. We used HPIValid[^2] to generate these hypergraphs for some of the databases from HPIValid's experimental evaluation. Along with them, the program computes the respective transversal hypergraphs (this is its purpose actually). We also include some of those hypergraphs for our experiments. The files are named accordingly, either ending in _hypergraph or in _transversal. Instead of using the official implementation of HPIValid, which is also based on MMCS, we integrated its validator into our own implementation of MMCS. Note that we did not use all hypergraphs that we list here, since many were very small and some were too large to be used in extensive experiments. For the database `isolet` we only computed the hypergraph and its transversal only using the first c columns (with different values of c), since the resulting files are already very large. The hypergraphs are located in the subfolders HPIValid/exported_hypergraphs/ and HPIValid/exported_hypergraphs_isolet_col_scaling/. Subfolder Gainer-Devar Connect 4 The set of all minimal winning states of the game Connect 4 can be interpreted as a hypergraph. We use these two hypergraphs and various subgraphs of them (constructed by only taking the first k hyperedges). The data originates from the UCI Machine Learning Repository, was converted to hypergraphs by Murakami and Uno[^1] and published in their Hypergraph Dualization Repository. Gainer-Devar and Vera-Licona[^3] converted them into a JSON format and provide them in their GitHub repository. These hypergraphs in JSON format are located in Gainer-Devar/benchmark_inputs/connect4-win/. Accident Given the set of complements of maximal frequent itemsets as edges of a hypergraph, its minimal hitting sets are exactly the minimal infrequent itemsets.The underlaying dataset consists of anonymized traffic accident data from the region of Flanders, Belgium and originates from the Frequent Itemset Mining Dataset Repository and was first published by Karolien Guerts.[^4]Murakami and Uno[^1] converted it into an instance for the transversal hypergraph problem and list it in their Hypergraph Dualization Repository.We, however, took it from the GitHub repository of Gainer-Devar and Vera-Licona.[^3] These hypergraphs in JSON format are located in Gainer-Devar/benchmark_inputs/accident/.The number in the filename represents the support threshold (between 30k and 200k). Metabolic Reaction Networks from E. coli In this application, minimal hitting sets correspond to “minimal cut sets” of certain metabolic reaction networks from E. coli. The data originates from an example for the Metatool 4.9 program. The data was prepared into hypergraphs in the JSON format by Gainer-Devar and Vera-Licona[^3] and provided in their GitHub repository. These hypergraphs in JSON format are located in Gainer-Devar/benchmark_inputs/ecoli/. Cell Signaling Network EGFR In this application, minimal hitting sets correspond to “optimal combinations of interventions” in the cell signaling network EGFR. Gainer-Devar and Vera-Licona[^3] provide the hypergraphs in their GitHub repository. They generated them using OSCANA[^6] from the network model from the paper The logic of EGFR/ErbB signaling: theoretical properties and analysis of high-throughput data by Samaga et al.[^5] The three resolutions short, sub and all correspond to different configurations of OSCANA. Gainer-Devar and Vera-Licona[^3] also provide hypergraphs for the HER2+[^6] cell signaling network, but we did not include them in our experiments because of the extensive runtime. These hypergraphs in JSON format are located in Gainer-Devar/benchmark_inputs/oscana/. Subfolder Hypergraph Dualization Repository Connect 4 In addition to the hypergraphs representing the minimal winning states of Connect 4, Murakami and Uno[^1] also provide the hypergraphs representing the minimal losing states of Connect 4 in their Hypergraph Dualization Repository. We converted them to a JSON format using this script provided by Gainer-Devar and Vera-Licona[^3] on their GitHub repository. These hypergraphs in JSON format are located in Hypergraph Dualization Repository/lose/. BMS-WebView2 As in the minimal infrequent itemset application above, but with a different underlaying dataset, Murakami and Uno[^1] provide another class of hypergraph in their Hypergraph Dualization Repository. It contains clickstream data from an e-commerce website. It also originates from the Frequent Itemset Mining Dataset Repository (though we could not find it on the given website) and was discussed in Real World Performance of Association Rule Algorithms[^7] by Zheng et al. We converted the hypergraphs to a JSON format using this script provided by Gainer-Devar and Vera-Licona[^3] on their GitHub repository. These hypergraphs in JSON format are located in Hypergraph Dualization Repository/bms2/.The number in the filename represents the support threshold (between 10 and 800). Hypergraph File Formats The .json format has the following form, where the used vertex indices are in the range {0, …, n-1} (or {1, …, n}). The .0-json and .1-json formats are explicit about the index range they use. See this example:{ "sets": [ [0, 1, 2], [1, 2, 3], [3, 4] ]} The .mhs or .g format has the following form. The first line contains the number of vertices (n). Each subsequent line is a comma-separated list of vertex indices in the range {0, …, n-1}. See this example: 40,1,21,2,33,4 References [^1]: Murakami, K., & Uno, T. (2014). Efficient algorithms for dualizing large-scale hypergraphs. Discrete Applied Mathematics, 170, 83-94. doi.org/10.1016/j.dam.2014.01.012 [^2]: Birnick, Johann, Thomas Bläsius, Tobias Friedrich, Felix Naumann, Thorsten Papenbrock, and Martin Schirneck. ‘Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery’. Proc. VLDB Endow. 13, no. 12 (2020): 2270–83. https://doi.org/10.14778/3407790.3407824. [^3]: Gainer-Dewar, Andrew, and Paola Vera-Licona. ‘The Minimal Hitting Set Generation Problem: Algorithms and Computation’. SIAM Journal on Discrete Mathematics 31, no. 1 (2017): 63–100. https://doi.org/10.1137/15M1055024. [^4]: Geurts, Karolien, Geert Wets, Tom Brijs, and Koen Vanhoof. ‘Profiling of High-Frequency Accident Locations by Use of Association Rules’. Transportation Research Record 1840, no. 1 (2003): 123–30. https://doi.org/10.3141/1840-14. [^5]: Samaga, Regina, Julio Saez-Rodriguez, Leonidas G. Alexopoulos, Peter K. Sorger, and Steffen Klamt. ‘The Logic of EGFR/ErbB Signaling: Theoretical Properties and Analysis of High-Throughput Data’. PLOS Computational Biology 5, no. 8 (2009): e1000438. https://doi.org/10.1371/journal.pcbi.1000438. [^6]: Vera-Licona, Paola, Eric Bonnet, Emmanuel Barillot, and Andrei Zinovyev. ‘OCSANA: Optimal Combinations of Interventions from Network Analysis’. Bioinformatics 29, no. 12 (2013): 1571–73. https://doi.org/10.1093/bioinformatics/btt195. [^7]: Zheng, Zijian, Ron Kohavi, and Llew Mason. ‘Real World Performance of Association Rule Algorithms’. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA), KDD ’01, 26 August 2001, 401–6. https://doi.org/10.1145/502512.502572.