## About me

Currently I am a PhD student at London School of Economics working under supervision of László Végh. You can find out more about me in **CV** (February 2018). Partially supported by ERC grant ScaleOpt.

## News

1.12.2019 | In the next three weeks I am visiting University of Helsinki and Alexandru I. Tomescu. |

20.06.2019 | The paper A polynomial-time algorithm for the independent set problem in {P10,C4,C6}-free graphsreceived the best student paper award at WG2019. |

07.02.2019 | A news article about our work on tumor evolution: An algorithm shedding light on the evolution of tumours helps individualise cancer therapies. |

1.10.2018 | I am attending FOCS 2018 (October 5-9, Paris). |

29.06.2018 | I am attending: - Building Bridges II (July 2 - 6, Budapest), - Midsummer Combinatorial Workshop XXIII (July 30 - August 3, Prague), - Hausdorff School on Combinatorial Optimization (August 20 - 24, Bonn). |

19.03.2018 | I am attending Google's Algorithms and Optimization PhD Workshop in Zurich from 10.04 until 12.04. |

17.02.2018 | Started making personal website. |

## Manuscripts

Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands

We present a simple auction algorithm that obtains an approximate market equilibrium for the exchange market model with divisible goods where the demands of the agents satisfy the weak gross substitutes (WGS) property. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash Social Welfare problem.

[arXiv] ## Publications

The independent set problem is FPT for even-hole-free graphs

The class of even-hole-free graphs is very similar to the class of perfect graphs, and was indeed a cornerstone in the tools leading to the proof of the Strong Perfect Graph Theorem. However, the complexity of computing a maximum independent set (MIS) is a long-standing open question in even-hole-free graphs. From the hardness point of view, MIS is W[1]-hard in the class of graphs without induced 4-cycle (when parameterized by the solution size). Halfway of these, we show in this paper that MIS is FPT when parameterized by the solution size in the class of even-hole-free graphs. The main idea is to apply twice the well-known technique of augmenting graphs to extend some initial independent set.

[IPEC 2019] [arXiv] A polynomial-time algorithm for the independent set problem in {P10,C4,C6}-free graphs

We consider the independent set problem, a classical NP-hard optimization problem that remains hard even under substantial restrictions on the input graphs. The complexity status of the problem is unknown for the classes of Pk-free graphs for all k ≥ 7 and for the class of even-hole-free graphs, that is, graphs not containing any even induced cycles. Using the technique of augmenting graphs we show that the independent set problem is solvable in polynomial time in the class of even-hole-free graphs not containing an induced path on 10 vertices. Our result is developed in the context of the more general class of {P10,C4,C6}-free graphs.

Best Student Paper Award at WG 2019

[WG 2019] MIPUP : Minimum perfect unmixed phylogenies for multi-sampled tumors via branchings and ILP

Discovering the evolution of a tumor may help identify driver mutations and provide a more comprehensive view on the history of the tumor. Recent studies have tackled this problem using multiple samples sequenced from a tumor, and due to clinical implications, this has attracted great interest. However, such samples usually mix several distinct tumor subclones, which confounds the discovery of the tumor phylogeny. We study a natural problem formulation requiring to decompose the tumor samples into several subclones with the objective of forming a minimum perfect phylogeny. We propose an Integer Linear Programming formulation for it, and implement it into a method called MIPUP. We tested the ability of MIPUP and of four popular tools LICHeE, AncesTree, CITUP, Treeomics to reconstruct the tumor phylogeny. On simulated data, MIPUP shows up to a 34% improvement under the ancestor-descendant relations metric. On four real datasets, MIPUP’s reconstructions proved to be generally more faithful than those of LICHeE.

[Bioinformatics (open access)] Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem

Motivated by applications in cancer genomics and following the work of Hajirasouliha and Raphael (WABI 2014), Hujdurović et al. (IEEE TCBB, to appear) introduced the minimum conflict-free row split (MCRS) problem; split each row of a given binary matrix into a bitwise OR of a set of rows so that the resulting matrix corresponds to a perfect phylogeny and has the minimum possible number of rows among all matrices with this property. Hajirasouliha and Raphael also proposed the study of a similar problem, in which the task is to minimize the number of distinct rows of the resulting matrix. Hujdurović et al. proved that both problems are NP-hard, gave a related characterization of transitively orientable graphs, and proposed a polynomial-time heuristic algorithm for the MCRS problem based on coloring cocomparability graphs. We give new, more transparent formulations of the two problems, showing that the problems are equivalent to two optimization problems on branchings in a derived directed acyclic graph. Building on these formulations, we obtain new results on the two problems, including (i) a strengthening of the heuristic by Hujdurović et al. via a new min-max result in digraphs generalizing Dilworth's theorem, which may be of independent interest, (ii) APX-hardness results for both problems, (iii) approximation algorithms, and (iv) exponential-time algorithms solving the two problems to optimality faster than the naïve brute-force approach. Our work relates to several well studied notions in combinatorial optimization; chain partitions in partially ordered sets, laminar hypergraphs, and (classical and weighted) colorings of graphs.

[ACM Transactions on Algorithms] [WG 2017] [arXiv]