JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: 2010 TCO Marathon Round 3
Problem: SubgraphIsomorphism

Problem Statement

    In this problem you will be given a large graph formed by a random process. You will then be asked to find a series of subgraphs of ever-increasing size. Your task is to answer as many queries as possible before time runs out.



An undirected graph G = (V,E) is defined by a set of vertices, V, indexed from 0 to N-1 and a set of edges (u,v). As the graph is undirected, each edge will be listed in both directions. An induced subgraph H of G is defined by a subset of vertices V' and all of the edges in E where both u and v are in V'. See Wikipedia for a more rigorous definition.



In the induced subgraph isomorphism problem, you are given two graphs: a graph G with N vertices, and a graph H with K vertices. Your task is to find a mapping f() from 0..K-1 to 0..N-1 such that (u,v) is an edge in H if and only if (f(u), f(v)) is an edge in G. Again, see Wikipedia for a formal definition.



In this problem, you will be given a graph G, followed by a series of smaller graphs H5, H6, H7, ... (starting from H5 intentionally). Hi will be an induced subgraph of G on i vertices. For each such query, you should return a int[] with i elements, where element j of your return represents f(j) above.



Each graph input will be formatted as a single int[]. The first element of the array will give the number of vertices. The degrees of the nodes will then be listed one at a time, along the their lists of neighbors. Thus, the following pseudocode will decode the input:
	ptr = 0
	vertices = input[ptr++]
	for (i = 0; i < vertices; i++) 
		degree = input[ptr++]
		for (j = 0; j < degree; j++) 
			createEdge(i, input[ptr++])
where createEdge(u,v) creates an edge in whatever data structure you choose to use.



Scoring

You will be given 10 seconds of total execution time. A function initialize will take the large graph G, and should return an integer (it doesn't matter what you return here). A function query will then be called repeatedly, starting with H5. Your 10 seconds includes the time spent in these functions (both initialize and query). Your query function will be called until you either run out of time, or give an incorrect return (one that isn't a match, or isn't valid). Your score for each test case will simply be the number of queries answered correctly before time runs out (or an incorrect return). Your overall score for all test cases will be the sum of your scores on all the individual test cases.

Test Generation

The graph G will be generated by first picking three values: N, alpha, and D. N will be chosen uniformly at random in [1000,20000]. Alpha will be a floating point number uniformly at random in [1,3). D will be an integer chosen uniformly in [2,30].



For vertex i, a location (xi,yi) will be chosen with xi and yi each integers in [0,220). For each vertex i, we will then generate D undirected edges (i,j). Given a choice of i, each j will be chosen with probability proportional to (1+dist(i,j))-alpha, where dist(i,j) = sqrt((xi-xj)2 + (yi-yj)2). The choices of j will be made with replacement, so the same j may be chosen multiple times. After all selection are made, duplicates are eliminated, leaving a simple undirected graph.



To select each Hi, a seed vertex u will be chosen uniformly at random from the N vertices in G. All neighbors of u will be added to the set of frontier vertices. Then, a node is chosen randomly from the set of frontier vertices and all of its neighbors are added to the frontier. A node added to the frontier multiple times will have multiple chances to be selected (making the frontier a multiset). This process is repeated until i vertices are chosen. If the frontier set becomes empty before i vertices have been selected, the select process is restarted from scratch. Finally, the subgraph is extracted and the vertex labels are randomly shuffled.

Offline Tool

An offline testing tool is provided here.
 

Definition

    
Class:SubgraphIsomorphism
Method:initialize
Parameters:int[]
Returns:int
Method signature:int initialize(int[] G)
 
Method:query
Parameters:int[]
Returns:int[]
Method signature:int[] query(int[] H)
(be sure your methods are public)
    
 

Notes

-The time limit is 10 seconds.
-The memory limit is 1024MB.
-Your method will be queried until you run out of time, or until the size of the subgraph is equal to the largest connected component in G.
-There are 50 test cases.
 

Examples

0)
    
seed = 1
N = 13878
alpha = 2.178079240820598
deg = 9
1)
    
seed = 2
N = 19425
alpha = 1.8807096080672547
deg = 16
2)
    
seed = 3
N = 7403
alpha = 2.6339482751431706
deg = 21
3)
    
seed = 4
N = 11809
alpha = 2.743153197688343
deg = 4
4)
    
seed = 5
N = 15638
alpha = 1.8666642015582442
deg = 7
5)
    
seed = 6
N = 13268
alpha = 2.9672762511627835
deg = 30
6)
    
seed = 7
N = 6674
alpha = 1.726463701449059
deg = 8
7)
    
seed = 8
N = 18559
alpha = 1.8207492412680386
deg = 27
8)
    
seed = 9
N = 2650
alpha = 2.3528908831563458
deg = 12
9)
    
seed = 10
N = 2706
alpha = 1.545583100723283
deg = 5

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.