- Oylum Şeker, Decomposition Methods for Selective Coloring Problem, (co-supervised with Z. Caner Taşkın) October 2018. (currently post-doc at the University of Toronto, Department of Mechanical and Industrial Engineering)
- Arman Boyacı, Graphs of Edge Intersectıng Non-Splitting Paths, June 2015. (currently at miks)

- Ömer Burak Onar, The Selective Tree Problem, Jan 2022.
- Gizem Taş, Network Based Methods for Anti-Money Laundering, July 2020.
- Ahmet Çağrı Düzgün, Finding Maximum Stable Sets in Perfect Graphs, (co-supervised with Z. Caner Taşkın), 2017. (currently PhD Candidate at Princeton University, Operations Research and Financial Engineering)
- Cemil Dibek, Edge-Extremal Graphs Under Degree and Matching Number Restrictions, 2016. (currently PhD Candidate at Princeton University, Operations Research and Financial Engineering)
- Betül Ahat, Integer programming formulations for the Maximum Induced Matching Problem, (co-supervised with Z. Caner Taşkın), 2016. (currently PhD candidate at Boğaziçi University, Industrial Engineering Department)
- Ayberk Çalık, The Selective Graph Coloring Problem, 2013. (currently Senior Product Manager at Turkcell)
- Ahu Akdemir (Göral), Defective Ramsey Numbers and Defective Cocolorings, 2012. (currently Thermal Optimization and Planning Team Lead at Enerjisa Üretim)
- Aysel Erey, Convexity in graphs, 2011. (currently Assist. Prof. at Gebze Technical University, Department of Mathematics)
- Arman Boyacı, Unit Disc Graph Coloring and its Reoptimization, 2009. (currently at miks)

- Zakir Deniz (October 2015 - May 2016, now Assist. Prof. at Düzce University, Turkey)
- Carl Feghali (April 2019)
- Milad Ahanjideh (March 2020-August 2021)

**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)=a_{0}+a_{1}x

b(x)=b_{0}+b_{1}x

then c:=a(x)b(x)=a_{0}b_{0} +
(a_{0}b_{1}+a_{1}b_{0})x + a_{1}b_{1 }x^{2}

where c_{0}=
a_{0}b_{0}, c_{1} = a_{0}b_{1}+a_{1}b_{0 }and
c_{2}= a_{1}b_{1} and a total of 4
multiplications
in used to obtain these coefficients. However, by computing c_{1}=(a_{0}+a_{1})(b_{0}+b_{1})-
a_{0}b_{0} - a_{1}b_{1}, 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 Computers*, *54*(3), 362-369.

Cenk, M., &
Özbudak, F. (2010). On multiplication in finite fields. *Journal
of
Complexity*, *26*(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 d_{G}(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, E}_{∪}_{E’)} (v, V \ A) ≤ D, ∀v
∈ A.

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.