Supervisors info:
Θηλυκός Δημήτριος, Καθηγητής, Τμήμα Μαθηματικών, ΕΚΠΑ.
Summary:
Given a graph G, we study the problem of counting the number of even induced subgraphs with k vertices. As even graph, we call a graph that has even number of vertices. Firstly, we will present the structural results that a graph should satisfy in order to have at least one even induced subgraph with k vertices. Using a lower bound from Ramsey theory, we will conclude that, for graphs with enough large number of vertices, the existence of at least one even induced subgraph k vertices can be easily decided by checking if the graph G belongs in a certain and small group of graph families, and checking some simple arithmetic relations for k. Using the above, we design a parameterized algorithm, with k as parameter, that decides whether there is an even subgraph in the given graph in k vertices. Moreover, we find an unexpected result, which shows that if a graph G with n vertices (where n is efficiently larger than k) has at least one even subgraph, then the G will have a large number of these subgraphs. Actually, the number of these subgraphs is large enough in order the method of random sampling to give a good approximation of the total number of these subgraphs without demanding too many repetitions. Accordingly, we study the same aspects for the odd induced subgraphs with k vertices, i.e., those which have odd number of edges.
Keywords:
graphs, counting even subgraphs, parameterized complexity, FPT, FPTRAS, Ramsey theory
