PhD Students

MS Students

 

Visiting PhD Students / Postdocs

New MS/PhD Thesis Topics (updated on August 2022)

MS (can be extended for a PhD Thesis)

Generating Random Perfect Graphs (to be co-supervised with Z.Caner Taşkın)

Perfect graphs model a wide range of applications in various fields such as sparse matrix computations, database management, computational biology (phylogeny), VLSI, computer vision, knowledge-based systems, and Bayesian networks. Accordingly, several algorithmic solutions especially tailored for perfect graphs have been developed for various optimization problems in perfect graphs. As pointed out in (Yildirim and Fan-Orzechowski 2006), the lack of perfect graph datasets makes it difficult to evaluate the performance of practical (exact, approximation or parameterized) algorithms especially tailored for perfect graphs. In (Şeker, Ekim, and Taşkın 2021), a series of perfect graphs have been generated using some operations preserving perfectness; to the best of our knowledge, this provides the first online available perfect graph generator. However, due to the lack of powerful structural results (see the extremely challenging question raised in (Chvátal 1984): can all perfect graphs be constructed from some “primitive” perfect graphs using perfection-preserving operations?) this algorithm do not guarantee that every perfect graph has a strictly positive probability to be generated. In other words, it generates only restricted types of perfect graphs. The aim of this project is to generate random perfect graphs which are as varied as possible so that the performance analyses of the algorithms that are tested on perfect graphs are not biaised.

A fundamental result (The Strong Perfect Graph Theorem) states that a graph is perfect if and only if it contains no induced odd cycle of length at least 5 and their complements. This will be exploited in diverse ways. Generating random (general) graphs, then testing perfectness can be seen as a starting point where perfect graph recognition algorithms with practical performance should be developed and tested. However, this will not yield a viable course of action for generating random perfect graphs of middle size since the big majority of graphs fail to be perfect as the number of vertices grows. The thesis will consist in combining asymptotic results with Integer Programming techniques. According to  (Prömel and Steger 1992), almost all C5-free graphs are perfect. Starting with this idea, an Integer programming formulation constructing a C5-free graph will be developed. If the graph constructed with this formulation is perfect then the algorithm stops. Otherwise new cuts forbidding longer induced odd cycles and their complements will be added to the formulation. This method can be applied recursively until a perfect graph is obtained. Lastly, the variety of the perfect graphs obtained by various methods will be studied.

Requirements: Good programming skills in C++, CPLEX or GUROBI. IE 456 (Graph Algorithms and Applications) or IE 518 (Advanced Graph Theory), and IE 613 (Large Scale Programming); or consent of the supervisors

References:

Chvátal, Vasek. 1984. ‘Notes on Perfect Graphs’. In Progress in Combinatorial Optimization, 107–15. Academic Press.

Prömel, Hans Jürgen, and Angelika Steger. 1992. ‘Almost All Berge Graphs Are Perfect’. Combinatorics, Probability and Computing 1 (1): 53–79. https://doi.org/10.1017/S0963548300000079.

Şeker, Oylum, Tınaz Ekim, and Z. Caner Taşkın. 2021. ‘An Exact Cutting Plane Algorithm to Solve the Selective Graph Coloring Problem in Perfect Graphs’. European Journal of Operational Research 291 (1): 67–83. https://doi.org/10.1016/j.ejor.2020.09.017.

Yildirim, E. Alper, and Xiaofei Fan-Orzechowski. 2006. ‘On Extracting Maximum Stable Sets in Perfect Graphs Using Lovász’s Theta Function’. Computational Optimization and Applications 33 (2): 229–47. https://doi.org/10.1007/s10589-005-3060-5

(MS) Fast Multiplication of Polynomials (to be co-supervised with Z.Caner Taşkın)

Multiplying two polynomials in an efficient way is a fundamental problem in cryptology and computer science in general. Since floating-point numbers are expressed in base 2, multiplying two floating-point numbers is equivalent to multiplying two univariate polynomials (Cenk and Ozbudak, 2010).

Given two univariate polynomials, we can obtain their product by multiplying all the cross terms. Given a polynomial a(x) of degree n (the largest power is n), and a polynomial b(x) of degree m (the largest power is m), the product, ab, will have degree n+m. To compute the product ab, there will be up to (n+1)(m+1) cross terms to multiply.

One measure of efficiency is the number of multiplication operations while computing all the coefficients in ab. In other words, we neglect the cost of the summation and subtraction operations, and we only count the total number of multiplication operations. As an example, take two polynomials

a(x)=a0+a1x

b(x)=b0+b1x

then c:=a(x)b(x)=a0b0 + (a0b1+a1b0)x + a1bx2

where c0= a0b0, c1 = a0b1+a1band c2= a1b1 and a total of 4 multiplications in used to obtain these coefficients. However, by computing c1=(a0+a1)(b0+b1)- a0b0 - a1b1, we would use only 3 multiplications to obtain all of c0, c1 and c2.

Karatsuba Algorithm (Karatsuba and Ofman, 1963) is a well-known heuristic method to multiply two polynomials efficiently. When the coefficients of the given polynomials are defined to be 0 or 1, then it is known that the minimum number of multiplications needed to multiply two polynomials of degree 1 is 3, of degree 2 is 6, of degree 3 is 9, of degree 4 is 13. For degree 5 polynomials the best known bound is 17, however it is not known if it is the optimal (Montgomery, 2005). This thesis is about formulating this problem of minimizing the number of multiplications to multiply two polynomials as an integer program and developing solution procedures (using decomposition methods) to solve it.

Requirements: Good programming skills in C++, CPLEX or GUROBI, IE 613 (Large Scale Programming) or consent of the supervisors

References:

Karatsuba, A., & Ofman, Y. (1963). In Multiplication of multidigit numbers on automata, Vol. Soviet Physics Doklady: Russia, 595-595.

Montgomery, P. L. (2005). Five, six, and seven-term Karatsuba-like formulae. IEEE Transactions on Computers54(3), 362-369.

Cenk, M., & Özbudak, F. (2010). On multiplication in finite fields. Journal of Complexity26(2), 172-186.


MS THESIS (To be co-supervised with Caner Taskin)

Solving the Defensive Domination Problem using Integer Programming techniques

Defensive domination: a k-attack is a subset of at most k vertices. A k-defense is a one-to-one assignment of defenders to a k-attack (a defender can also defend against an attack on itself). A set D is a k-defensive set if it can defend against ANY k-attack. The defensive domination problem is to find a k-defensive dominating set of minimum cardinality. Deciding whether there is a k-defensive dominating set of size at most t is known to be NP-complete for fixed k; if k is part of the input, the problem is not even in NP. There are only very few special graph classes where the k-defensive dominating set can be solved in polynomial time. No Integer Programming formulation has been suggested in the literature. The student will suggest IP formulations for the defensive domination problem and develop solution procedures.

Requirements: Good programming skills in C++, CPLEX or GUROBI. IE 613 (Large Scale Programming); or consent of the supervisors

References:

T. Ekim, A. Farley, A. Proskurowski, The Complexity of the Defensive Domination Problem in Special Graph Classes, Discrete Mathematics, 343 (2), Feb 2020, 111665. doi: 10.1016/j.disc.2019.111665

T. Ekim, A. Farley, A. Proskurowski, M. Shalom, Defensive Domination in Proper Interval Graphs, submitted. http://arxiv.org/abs/2010.03865

GRAPH MODIFICATION PROBLEMS TO REDUCE POLARISATION IN SOCIAL NETWORKS  (NOT ACTIVE)

The first graph modification problem with primary focus on polarisation reduction in social networks is defined very recently in(Interian et al., 2019). Its objective is to add a minimum number of edges to the input graph so that the distance from any vertex v in a specified vertexset A V to any other vertex in V \ A  is at most a given integer D. Clearly, the graph obtained after addition of edges has moreconnections between the set A and the rest, consequently, inter-group communication is improved. It is formally defined as follows. Let dG(v; V’) denote the distance of a vertex v to a set of vertices V’ defined as thelength (number of edges) of a shortest path between a vertex v of graph G to any vertex in V’ V.

Minimum-cardinality Balanced Edge Addition Problem (Min CBEAP)

Instance: Graph G = (V, E), subset A V , integer D.

Goal: Find a minimum-cardinality set E’ (V × V) \ E such that d G =(V, EE’) (v, V \ A) ≤ D, v A.

According to the choice of polarisation measure, we can define different polarisationreduction problems. These measures are mainly based on the notion of shortest paths which is seen as the best way of ensuring an efficient (rapid andreliable) communication in a network.

For a vertex v, the eccentricity of v is the maximum distance between v and anyvertex in the graph. The diameter of a graph is the maximum of the eccentricity of any vertex in the graph. In other words, the diameter of a graph is themaximum length of a shortest path between two vertices in the graph.

The problem of adding a minimum number of edges to a given graph in order to minimize itsdiameter is studied in (Demaine and Zadimoghaddam, 2010). This problem, called Minimum-cardinality-bounded-eccentricity edge addition problem (Min CBE), ismotivated by not only polarisation reduction in social networks but also other real-life problems where the interruption/disruption of the transportation and/orcommunication in the underlying network is a concern. Examples of such situations include slow-downs in power-grid networks, sensor networks ormulticore processor networks, but more importantly in the primordial task of repairing communication and transportation networks after natural disasters inorder to accommodate further help.

This thesis will consist in considering Min CBEAP, Min CBE and variations of these problemsfrom an optimization point of view. Integer Programming Formulations and heuristic algorithms will be developed and their performance will be testedempirically on both synthetically generated and real instances.

·  Demaine, E. D., & Zadimoghaddam, M. (2010). Minimizing the Diameter of a Network UsingShortcut Edges. In H. Kaplan (Ed.), Algorithm Theory—SWAT 2010 (Vol. 6139, pp. 420–431). Springer Berlin Heidelberg.https://doi.org/10.1007/978-3-642-13731-0_39

·  Interian, R., Moreno, J. R., & Ribeiro, C. C. (2020). Reducing Network Polarisation byEdge Additions. 87–92. https://doi.org/10.1145/3396474.3396486

TITLE: MAXIMUM ACYCLIC MATCHING (NOT ACTIVE)

A matching M in a graph G ıs acyclic if the subgraph of G induced by the set of vertices that are incident to an edge in M is a forest. If ν(G), νac(G), and νs(G) denote the largest size of a matching, an acyclic matching, and an induced matching in G, respectively, then, since every induced matching is acyclic, we have ν(G) ≥ νac(G) ≥ νs(G). In contrast to the matching number ν(G), which is a well known classical tractable graph parameter, both, the acyclic matching number νac(G) as well as the induced matching number νs(G)  are computationally hard. While induced matchings have been studied in great detail, only few results are known on the acyclic matching number. While the equality ν(G) = νs(G) can be decided efficiently for a given graph G, it is NP-complete to decide whether ν(G) = νac(G) for a given bipartite graph G of maximum degree at most 4, and efficient algorithms computing the acyclic matching number are known only for certain graph classes.

This project is about

1)      Identifying graph classes where νac(G) can be computed in polynomial time, if possible, and

2)      Developing Integer Programming Formulations and approximation algorithms for the Max Acyclic Matching Problem and testing their performance with experiments.

References:

https://arxiv.org/pdf/2002.03649.pdf

https://hal.sorbonne-universite.fr/hal-01777928/file/Degenerate_Matchings.pdf


Stable Matchings and University Admission Problem (to be co-supervised with Prof. Ahmet Alkan from Sabancı University)
(MS Student in Industrial Engineering and/or Computer Science)

Among several applications of the stable matchings, one of the most studied is the university admission problem. This can be seen as a one-to-one matching problem where institutions and applicants have preference lists on each other. The objective is to find a matching between institutions and applicants which is stable; that is, a matching where there is no pair of institution-applicant which are not matched to each other but which would be both better off if matched to each other. Gale and Shapley describe an algorithm to determine a stable matching in such a context. Gale-Shapley Algorithm generates two extreme stable matchings, one which is best for the applicants (thus worst for the institutions) and one which is best for the institutions (thus, worst for the applicants).

Consider all the stable matchings. For any agent, order all the possible matches (with possible multiplicities) in these stable matchings and take the median one. Then the median stable matching is such that all agents are matched to their median matches. Teo and Sethuraman established the existence of a median stable matching and proposed an algorithm to find it. One objective of this thesis is to suggest new algorithms to find median stable matchings and compare them with the ones in the literature both from theoretical and practical point of views. It is known that the number of all stable matchings may increase exponentially with the number of agents. A particular aim will be to find an algorithm that is polynomially bounded over an interestingly large domain.

The student will also be focused on an extension of the university admission problem where we seek a many-to-many matching (instead of one-to-one) upon which to schedule interviews: The students matched with a university in this matching (on the basis of student preferences and exam scores) will be those whom the university will interview for additional information to update its preferences. The interview lists here, per student and per university, should naturally be of "short" length since each interview has an associated cost. On the other hand, each interview brings an informational return that can be seen as a profit. The objective is to generate the most valuable list of interviews. Algorithms to find most valuable list of interviews will be proposed and empirically tested.

•    Alkan and D. Gale, "Stable schedule matching under revealed preference", Journal of Economic Theory, 2003
•    T. Ekim, Eşleme Kuramı ve 2012 Nobel Ekonomi Ödülü, Matematik Dünyası, 2019.
•    D. Gale and L.S. Shapley, "College admissions and the stability of marriage", Amer. Math. Monthly, 69:9–14, 1962.
•    C.P. Teo and J. Sethuraman (1998): “The Geometry of Fractional Stable Matchings and Its Applications,” Mathematics of Operations Research, 23(4), 874–891.


The Selective Tree Problem (to be co-supervised with Z.Caner Taşkın) (NOT ACTIVE)

Problems of selective nature, such as the selective coloring problem, have already been studied in the literature. In general, they bring more flexibility to the application areas of the problem under consideration.

Given a graph and a partition of its vertex set into clusters, the Selective Tree Problem is the following decision problem: is there a selection of exactly one vertex per cluster such that the graph induced by the selection is a tree? Noting that a tree is a minimally connected graph, this can be seen as the most economical way to connect all clusters.

If each cluster has one vertex then the problem boils down into deciding whether the given
graph is a tree, thus a trivial question. However, as soon as clusters are allowed to contain 2 vertices, the problem becomes intractable even in restricted cases. More precisely, it is NP-complete to decide whether a given planar bipartite graph with clusters containing either 1 or 2 vertices admits a selection inducing a tree or not.

One can also think about the optimization version of the Selective Tree Problem where the objective is to find a selection (that is, exactly one vertex per cluster) such that the order or the total weight of an induced tree in this selection is maximized.

The aim of this project is to develop an Integer Programming Formulations and efficient solution algorithms for the Selective Tree Problem (both for the decision and optimization versions) and test its efficiency in a systematic way. Two defining properties of trees will be used in such a formulation: connectivity and the absence of cycles. A similar, yet different problem will also be considered from the same aspect: The Selective Forest Problem where the selection is still required to induce an acyclic graph, however the connectivity requirement is relaxed. It is not clear at first sight whether this relaxation makes the problem computationally easier or harder. This project is also expected to shed light on this question.