Hardness of Games and Graph Sampling

Nayak, Bhagirathi and Aravind, N R (2018) Hardness of Games and Graph Sampling. Masters thesis, Indian Institute of Technology Hyderabad.

Thesis_Mtech_CS_4065.pdf - Published Version

Download (8MB) | Preview


The work presented in this document is divided into two parts. The �rst part presents the hardness of games and the second part presents Graph sampling. Non-deterministic constraint logic[1] is used to prove the hardness of games. The games which are considered in this work is Reversi (2 player bounded game), Peg Solitaire (single player bounded game), Badland (single player bounded game). It also contains a theoretical study of peg solitaire on special graph classes. Reversi is proved to be PSPACE-Complete using Bounded 2CL, Peg Solitaire is proved to be NP-Complete using Bounded NCL. Badland is proved to be NP-Complete by a reduction from 3-SAT. The objective of study of peg solitaire of special graph classes is to �nd the maximum number of marbles we can remove from a fully �lled board, if the player is given the privilege to remove a marble from any cell initially, then following the rules after the initial move. The second part of the work is dedicated to graph sampling. Given a graph G, we try to sample a represen- tative subgraph Gs which is similar to the original graph G. The properties that are being studied are Degree Distribution, Clustering Coefficient, Average Shortest Path Length, Largest Connected Component Size. To measure the similarity between the original graph and sample we use the metrics Kolmogorov - Smirnov test and Kullback - Leibler divergence test. Tightly Induced Edge Sampling performs well on general graphs but it's performance decreases when the graph is a tree. Overall TIBFS and KARGER produces a sample which closely matches the distribution of original graphs. v

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Thesis (Masters)
Uncontrolled Keywords: NCL, Hardness, Sampling, Subgraph
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 22 Jun 2018 10:25
Last Modified: 22 Jun 2018 10:25
URI: http://raiith.iith.ac.in/id/eprint/4065
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 4065 Statistics for this ePrint Item