Date Available

4-29-2022

Year of Publication

2022

Document Type

Master's Thesis

Degree Name

Master of Science (MS)

College

Engineering

Department/School/Program

Computer Science

Advisor

Dr. Jerzy W. Jaromczyk

Abstract

Even functionals are a set of polynomials evaluated on the terms of hollow symmetric matrices. Their properties lend themselves to applications such as counting subgraph embeddings in generic (weighted or unweighted) host graphs and computing moments of binary quadratic forms, which occur in combinatorial optimization. This research focuses primarily on counting subgraph embeddings, which is traditionally accomplished with brute-force algorithms or algorithms curated for special types of graphs. Even functionals provide a method for counting subgraphs algebraically in time proportional to matrix multiplication and is not restricted to particular graph types. Counting subgraph embeddings can be accomplished by evaluating a linear combination of matrix expressions on the adjacency matrix of a host graph. Algorithms for computing the coefficients of these terms for counting arbitrary subgraphs are presented, with a special focus on efficiency and robustness. These algorithms are used to produce coefficients for counting the number of 8-cycles in a host graph. The matrix expressions used are derived from the space of even functionals of degree 𝑙. This space is represented by the set of even multigraphs with 𝑙 edges. A difficulty in discovering these spaces hence is discovery of the even graphs themselves. Included in the research are tools developed to facilitate investigation of even functionals. These tools, written in both Python and C++, perform arbitrary-precision evaluation of matrix expressions, solve linear systems of equations, draw and compare graphs, and more. They utilize well-known libraries and packages such as GMP, NumPy, NetworkX, and Graphviz.

Digital Object Identifier (DOI)

https://doi.org/10.13023/etd.2022.122

Download

Share

COinS