Arrow Research search

Author name cluster

Meirav Zehavi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

59 papers
2 author rows

Possible papers

59

AAAI Conference 2025 Conference Paper

Adaptive Manipulation for Coalitions in Knockout Tournaments

  • Juhi Chaudhary
  • Hendrik Molter
  • Meirav Zehavi

Knockout tournaments, also known as single-elimination or cup tournaments, are a popular form of sports competitions. In the standard probabilistic setting, for each pairing of players, one of the players wins the game with a certain (a priory known) probability. Due to their competitive nature, tournaments are prone to manipulation. We investigate the computational problem of determining whether, for a given tournament, a coalition has a manipulation strategy that increases the winning probability of a designated player above a given threshold. More precisely, in every round of the tournament, coalition players can strategically decide which games to throw based on the advancement of other players to the current round. We call this setting adaptive constructive coalition manipulation. To the best of our knowledge, while coalition manipulation has been studied in the literature, this is the first work to introduce adaptiveness to this context. We show that the above problem is hard for every complexity class in the polynomial hierarchy. On the algorithmic side, we show that the problem is solvable in polynomial time when the coalition size is a constant. Furthermore, we show that the problem is fixed-parameter tractable when parameterized by the coalition size and the size of a minimum player set that must include at least one player from each non-deterministic game. Lastly, we investigate a generalized setting where the tournament tree can be imbalanced.

PDF Details DOI

STOC Conference 2025 Conference Paper

Efficiently Finding and Counting Patterns with Distance Constraints in Sparse Graphs

  • Daniel Lokshtanov
  • Fahad Panolan
  • Saket Saurabh 0001
  • Jie Xue 0003
  • Meirav Zehavi

Graph classes of bounded expansion were introduced by Nešetřil and de Mendez as a general model of structurally sparse graphs, which have received considerable attention from both combinatorial and algorithmic perspectives. A celebrated result of Dvořák et al. [JACM’13] showed that any first-order model checking problem on bounded-expansion graph classes is fixed-parameter tractable. A main drawback of the FPT algorithms resulted from this result is the high dependency of their time complexity on the parameter k : the algorithms run in time at least doubly exponential in k , even when the graph class is of polynomial expansion. It is natural to ask whether there exist FPT algorithms for these problem that run in singly exponential time, i.e., 2 k O (1) n O (1) time. In this paper, we give a new algorithmic framework for a broad family of first-order model checking problems on sparse graphs, which results in algorithms with running time 2 k O (1) · n when the graph class is of exponential expansion (i.e., the expansion is bounded by a singly exponential function). This covers most well-studied instances of bounded-expansion graph classes, in particular, all polynomial-expansion graph classes. Our framework applies to all problems that can be formulated as finding k vertices in a host graph G with certain distance constraints . Furthermore, the framework can be generalized to give (1 ± ε)-approximation algorithms for the counting versions of these problems with running time 2 k O (1) · n (log n /ε) O (1) on exponential-expansion graph classes. In terms of techniques, our framework differs entirely from the one of Dvořák et al. based on centered coloring. We develop various technical components based on the theory of sparse graphs and other tools such as representative sets/functions, tree decomposition, inclusion-exclusion, etc., which are of independent interest. Remarkably, some of our techniques can be applied to even more general graph classes, such as degenerate graph classes. Therefore, as a byproduct, we obtain a (1 ± ε)-approximation algorithm for approximately counting bounded-treewidth induced subgraphs in degenerate graphs with running time k O ( k ) · ( n /ε) O (1) . This resolves (in a much stronger form) an open problem of Bressan and Roth [FOCS’22], which asked whether such an algorithm exists for counting induced k -matching in degenerate graphs.

Details

JAIR Journal 2025 Journal Article

Parameterized Analysis of Bribery in Challenge the Champ Tournaments

  • Juhi Chaudhary
  • Hendrik Molter
  • Meirav Zehavi

Challenge the champ tournaments are one of the simplest forms of competition, where a (initially selected) champ is repeatedly challenged by other players. If a player beats the champ, then that player is considered the new (current) champ. Each player in the competition challenges the current champ once in a fixed order. The champ of the last round is considered the winner of the tournament. We investigate a setting where players can be bribed to lower their winning probability against the initial champ. The goal is to maximize the probability of the initial champ winning the tournament by bribing the other players, while not exceeding a given budget for the bribes. Mattei et al. [Journal of Applied Logic, 2015] showed that the problem can be solved in pseudo-polynomial time, and that it is in XP when parameterized by the number of players. We show that the problem is weakly NP-hard and W[1]-hard when parameterized by the number of players. On the algorithmic side, we show that the problem is fixed-parameter tractable when parameterized either by the number of different bribe values or the number of different probability values. To this end, we establish several results that are of independent interest. In particular, we show that the product knapsack problem is W[1]-hard when parameterized by the number of items in the knapsack, and that constructive bribery for cup tournaments is W[1]-hard when parameterized by the number of players. Furthermore, we present a novel way of designing mixed integer linear programs, ensuring optimal solutions where all variables are integers.

PDF Details DOI

MFCS Conference 2025 Conference Paper

Quasipolynomial-Time Deterministic Kernelization and (Gammoid) Representation

  • Rohit Gurjar
  • Daniel Lokshtanov
  • Pranabendu Misra
  • Fahad Panolan
  • Saket Saurabh 0001
  • Meirav Zehavi

In this paper, we suggest to extend the notion of a kernel to permit the kernelization algorithm to be executed in quasi-polynomial time rather than polynomial time. So far, we are only aware of one work that addressed this negatively, showing that some lower bounds on kernel sizes proved for kernelization also hold when quasi-polynomial time complexity is allowed. When we, anyway, deal with an NP-hard problem, sacrificing polynomial time in preprocessing for quasi-polynomial time may often not be a big deal, but, of course, the question is - does it give us more power? The only known work, mentioned above, seems to suggest that the answer is "no". In this paper, we show that this is not the case - in particular, we show that this notion is extremely powerful for derandomization. Some of the most basic kernelization algorithms in the field are based on inherently randomized tools whose derandomization is a huge problem that has remained (and may still remain) open for many decades. Still, some breakthrough advances for derandomization in quasi-polynomial time have been made. Can we harness these advancements to design quasi-polynomial deterministic kernelization algorithms for basic problems in the field? To this end, we revisit the question of deterministic polynomial-time computation of a linear representation of transversal matroids and gammoids, which is a longstanding open problem. We present a deterministic computation of a representation matrix of a transversal matroid in time quasipolynomial in the rank of the matroid, where each entry of the matrix can be represented in quasipolynomial (in the rank of the matroid) bits. As a corollary, we obtain a linear representation of a gammoid in deterministic quasipolynomial time and quasipolynomial bits in the size of the underlying ground set of the gammoid. In turn, as applications of our results, we present deterministic quasi-polynomial time kernels of polynomial size for several central problems in the field.

Details

ICML Conference 2025 Conference Paper

What makes an Ensemble (Un) Interpretable?

  • Shahaf Bassan
  • Guy Amir
  • Meirav Zehavi
  • Guy Katz

Ensemble models are widely recognized in the ML community for their limited interpretability. For instance, while a single decision tree is considered interpretable, ensembles of trees (e. g. , boosted trees) are often treated as black-boxes. Despite this folklore recognition, there remains a lack of rigorous mathematical understanding of what particularly makes an ensemble (un)-interpretable, including how fundamental factors like the (1) number, (2) size, and (3) type of base models influence its interpretability. In this work, we seek to bridge this gap by applying concepts from computational complexity theory to study the challenges of generating explanations for various ensemble configurations. Our analysis uncovers nuanced complexity patterns influenced by various factors. For example, we demonstrate that under standard complexity assumptions like P$\neq$NP, interpreting ensembles remains intractable even when base models are of constant size. Surprisingly, the complexity changes drastically with the number of base models: small ensembles of decision trees are efficiently interpretable, whereas ensembles of linear models remain intractable, even with a constant number of models. We believe that our findings provide a more robust foundation for understanding the interpretability of ensembles, emphasizing the benefits of examining it through a computational complexity lens.

Details

AAAI Conference 2024 Conference Paper

How to Make Knockout Tournaments More Popular?

  • Juhi Chaudhary
  • Hendrik Molter
  • Meirav Zehavi

Given a mapping from a set of players to the leaves of a complete binary tree (called a seeding), a knockout tournament is conducted as follows: every round, every two players with a common parent compete against each other, and the winner is promoted to the common parent; then, the leaves are deleted. When only one player remains, it is declared the winner. This is a popular competition format in sports, elections, and decision-making. Over the past decade, it has been studied intensively from both theoretical and practical points of view. Most frequently, the objective is to seed the tournament in a way that ``assists'' (or even guarantees) some particular player to win the competition. We introduce a new objective, which is very sensible from the perspective of the directors of the competition: maximize the profit or popularity of the tournament. Specifically, we associate a ``score'' with every possible match, and aim to seed the tournament to maximize the sum of the scores of the matches that take place. We focus on the case where we assume a total order on the players' strengths, and provide a wide spectrum of results on the computational complexity of the problem.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Learning Small Decision Trees with Few Outliers: A Parameterized Perspective

  • Harmender Gahlawat
  • Meirav Zehavi

Decision trees is a fundamental tool in machine learning for representing, classifying, and generalizing data. It is desirable to construct ``small'' decision trees, by minimizing either the size (s) or the depth (d) of the decision tree (DT). Recently, the parameterized complexity of Decision Tree Learning has attracted a lot of attention. We consider a generalization of Decision Tree Learning where given a classification instance E and an integer t, the task is to find a ``small'' DT that disagrees with E in at most t examples. We consider two problems: DTSO and DTDO, where the goal is to construct a DT minimizing s and d, respectively. We first establish that both DTSO and DTDO are W[1]-hard when parameterized by s+y and d+y, respectively, where y is the maximum number of features in which two differently labeled examples can differ. We complement this result by showing that these problems become FPT if we include the parameter t. We also consider the kernelization complexity of these problems and establish several positive and negative results for both DTSO and DTDO.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Parameterized Analysis of Bribery in Challenge the Champ Tournaments

  • Juhi Chaudhary
  • Hendrik Molter
  • Meirav Zehavi

Challenge the champ tournaments are one of the simplest forms of competition, where a (initially selected) champ is repeatedly challenged by other players. If a player beats the champ, then that player is considered the new (current) champ. Each player in the competition challenges the current champ once in a fixed order. The champ of the last round is considered the winner of the tournament. We investigate a setting where players can be bribed to lower their winning probability against the initial champ. The goal is to maximize the probability of the initial champ winning the tournament by bribing the other players, while not exceeding a given budget for the bribes. In previous work is was shown that the problem can be solved in pseudo-polynomial time, and that it is in XP when parameterized by the number of players. We show that the problem is weakly NP-hard and W[1]-hard when parameterized by the number of players. On the algorithmic side, we show that the problem is fixed-parameter tractable when parameterized either by the number of different bribe values or the number of different probability values. To this end, we establish several results that are of independent interest. In particular, we show that the product knapsack problem is W[1]-hard when parameterized by the number of items in the knapsack, and that constructive bribery for cup tournaments is W[1]-hard when parameterized by the number of players. Furthermore, we present a novel way of designing mixed integer linear programs, ensuring optimal solutions where all variables are integers.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?

  • Pascal Kunz
  • Hendrik Molter
  • Meirav Zehavi

A temporal graph has an edge set that may change over discrete time steps, and a temporal path (or walk) must traverse edges that appear at increasing time steps. Accordingly, two temporal paths (or walks) are temporally disjoint if they do not visit any vertex at the same time. The study of the computational complexity of finding temporally disjoint paths or walks in temporal graphs has recently been initiated by Klobas et al. . This problem is motivated by applications in multi-agent path finding (MAPF), which include robotics, warehouse management, aircraft management, and traffic routing. We extend Klobas et al. ’s research by providing parameterized hardness results for very restricted cases, with a focus on structural parameters of the so-called underlying graph. On the positive side, we identify sufficiently simple cases where we can solve the problem efficiently. Our results reveal some surprising differences between the “path version” and the “walk version” (where vertices may be visited multiple times) of the problem, and answer several open questions posed by Klobas et al.

PDF Details DOI

MFCS Conference 2023 Conference Paper

Parameterized Analysis of the Cops and Robber Game

  • Harmender Gahlawat
  • Meirav Zehavi

Pursuit-evasion games have been intensively studied for several decades due to their numerous applications in artificial intelligence, robot motion planning, database theory, distributed computing, and algorithmic theory. Cops and Robber (CnR) is one of the most well-known pursuit-evasion games played on graphs, where multiple cops pursue a single robber. The aim is to compute the cop number of a graph, k, which is the minimum number of cops that ensures the capture of the robber. From the viewpoint of parameterized complexity, CnR is W[2]-hard parameterized by k [Fomin et al. , TCS, 2010]. Thus, we study structural parameters of the input graph. We begin with the vertex cover number (vcn). First, we establish that k ≤ vcn/3+1. Second, we prove that CnR parameterized by vcn is FPT by designing an exponential kernel. We complement this result by showing that it is unlikely for CnR parameterized by vcn to admit a polynomial compression. We extend our exponential kernels to the parameters cluster vertex deletion number and deletion to stars number, and design a linear vertex kernel for neighborhood diversity. Additionally, we extend all of our results to several well-studied variations of CnR.

Details

FOCS Conference 2023 Conference Paper

Planar Disjoint Paths, Treewidth, and Kernels

  • Michal Wlodarczyk 0001
  • Meirav Zehavi

In the PLANAR DISJOINT PATHS problem, one is given an undirected planar graph with a set of k vertex pairs $\left(s_{i}, t_{i}\right)$ and the task is to find k pairwise vertex-disjoint paths such that the i-th path connects $s_{i}$ to $t_{i}$. We study the problem through the lens of kernelization, aiming at efficiently reducing the input size in terms of a parameter. We show that PLANAR DISJOINT PATHS does not admit a polynomial kernel when parameterized by k unless coNP $\subseteq \mathrm{NP} /$ poly, resolving an open problem by [Bodlaender, Thomassé, Yeo, ESA’09]. Moreover, we rule out the existence of a polynomial Turing kernel unless the WKhierarchy collapses. Our reduction carries over to the setting of edge-disjoint paths, where the kernelization status remained open even in general graphs. On the positive side, we present a polynomial kernel for PLANAR DISJOINT PATHS parameterized by $k+\mathrm{tw}$, where tw denotes the treewidth of the input graph. As a consequence of both our results, we rule out the possibility of a polynomialtime (Turing) treewidth reduction to $t w=k^{\mathcal{O}(1)}$ under the same assumptions. To the best of our knowledge, this is the first hardness result of this kind. Finally, combining our kernel with the known techniques [Adler, Kolliopoulos, Krause, Lokshtanov, Saurabh, Thilikos, JCTB’17; Schrijver, SICOMP’94] yields an alternative (and arguably simpler) proof that PLANAR DISJOINT PATHS can be solved in time $2^{\mathcal{O}\left(k^{2}\right)} \cdot n^{\mathcal{O}(1)}$, matching the result of [Lokshtanov, Misra, Pilipczuk, Saurabh, Zehavi, STOC’20].

Details

AAAI Conference 2023 Conference Paper

Tournament Fixing Parameterized by Feedback Vertex Set Number Is FPT

  • Meirav Zehavi

A knockout (or single-elimination) tournament is a format of a competition that is very popular in practice (particularly in sports, elections and decision making), and which has been extensively and intensively studied from a theoretical point of view for more than a decade. Particular attention has been devoted to the Tournament Fixing problem, where, roughly speaking, the objective is to determine whether we can conduct the knockout tournament in a way that makes our favorite player win. Here, part of the input is a tournament graph D that encodes the winner of each possible match. A sequence of papers has studied the parameterized complexity of Tournament Fixing with respect to the feedback arc set number (fas) of D Given that this parameter yielded tractability, it has been asked explicitly and repeatedly whether Tournament Fixing is FPT also with respect to the feedback vertex set number (fvs) of D. We answer this question positively. In fact, although fvs can be arbitrarily smaller than fas, we attain the same dependency on the parameter in the time complexity. So, additionally, our work subsumes the best known algorithm for Tournament Fixing with respect to as.

PDF Details DOI

SODA Conference 2022 Conference Paper

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent

  • Akanksha Agrawal 0001
  • Lawqueen Kanesh
  • Daniel Lokshtanov
  • Fahad Panolan
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001
  • Meirav Zehavi

Vertex-deletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by mod ℋ ) of a modulator to a graph class ℋ, i. e. , a set of vertices whose deletion results in a graph in ℋ. Recent years have seen the development of a research programme where the complexity of modulators is measured in ways other than size. For instance, for a graph class ℋ, the graph parameters elimination distance to ℋ (denoted by ed ℋ ) [Bulian and Dawar, Algorithmica, 2016] and ℋ -treewidth (denoted by tw ℋ ) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the “torso” of the graph induced on a modulator to the graph class ℋ. Here, the torso of a vertex set S in a graph G is the graph with vertex set S and an edge between two vertices u, v ∊ S if there is a path between u and v in G whose internal vertices all lie outside S. In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ℋ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ℋ satisfying mild additional conditions, with the exception of ed ℋ parameterized by tw ℋ, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ℋ ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing ed ℋ and tw ℋ. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a “strong irrelevant vertex rule”, then there exists a uniform FPT algorithm for ed ℋ. Using these sufficient conditions, we obtain uniform FPT algorithms for computing ed ℋ, when ℋ is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when ℋ is any of bipartite, chordal or interval graphs. For most of these problems, the existence of a uniform FPT algorithm has remained open in the literature. In fact, for some of them, even a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when ℋ is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative.

Details

JAAMAS Journal 2022 Journal Article

Verification of multi-layered assignment problems

  • Barak Steindl
  • Meirav Zehavi

Abstract The class of assignment problems is a fundamental and well-studied class in the intersection of Social Choice, Computational Economics and Discrete Allocation. In a general assignment problem, a group of agents expresses preferences over a set of items, and the task is to allocate items to agents in an “optimal” way. A verification variant of this problem includes an allocation as part of the input, and the question becomes whether this allocation is “optimal”. In this paper, we generalize the verification variant to the setting where each agent is equipped with multiple incomplete preference lists: Each list (called a layer ) is a ranking of items in a possibly different way according to a different criterion. In particular, we introduce three multi-layer verification problems, each corresponds to an optimality notion that weakens the notion of global optimality (that is, pareto optimality in multiple layers) in a different way. Informally, the first notion requires that, for each group of agents whose size is exactly some input parameter k, the agents in the group will not be able to trade their assigned items among themselves and benefit in at least \(\alpha \) layers; the second notion is similar, but it concerns all groups of size at most k rather than exactly k; the third notion strengthens these notions by requiring that groups of k agents will not be part of possibly larger groups that benefit in at least \(\alpha \) layers. We study the three problems from the perspective of parameterized complexity under several natural parameterizations such as the number of layers, the number of agents, the number of items, the number of allocated items, the maximum length of a preference list, and more. We present an almost comprehensive picture of the parameterized complexity of the problems with respect to these parameters.

Details DOI

SODA Conference 2021 Conference Paper

Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version)

  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Meirav Zehavi

In this paper we prove an analogue of the classic Bollobás lemma for approximate counting. In fact, we match an analogous result of Fomin et al. [JACM 2016] for decision. This immediately yields, for a number of fundamental problems, parameterized approximate counting algorithms with the same running times as what is obtained for the decision variant using the representative family technique of Fomin et al. [JACM 2016]. For example, we devise an algorithm for approximately counting (a factor (1 ± ∊ ) approximation algorithm) k -paths in an n -vertex directed graph (# k -Path) running in time ( n + m )). This improves over an earlier algorithm of Brand et al. [STOC 2018] that runs in time. Additionally, we obtain an approximate counting analogue of the efficient computation of representative families for product families of Fomin et al. [TALG 2017], again essentially matching the running time for decision. This results in an algorithm with running time for computing a (1 + ∊ ) approximation of the sum of the coefficients of the multilinear monomials in a degree- k homogeneous n -variate polynomial encoded by a monotone circuit (#M ultilinear M onomial D etection ). When restricted to monotone circuits (rather than polynomials of non-negative coefficients), this improves upon an earlier algorithm of Pratt [FOCS 2019] that runs in time.

Details

AAMAS Conference 2021 Conference Paper

Multivariate Analysis of Scheduling Fair Competitions

  • Siddharth Gupta
  • Meirav Zehavi

A fair competition, based on the concept of envy-freeness, is a noneliminating competition where each contestant (team or individual player) may not play against all other contestants, but the total difficulty for each contestant is the same: the sum of the initial rankings of the opponents for each contestant is the same. Similar to other non-eliminating competitions like the Round-robin competition or the Swiss-system competition, the winner of the fair competition is the contestant who wins the most games. The Fair Non-Eliminating Tournament (Fair-NET) problem can be used to schedule fair competitions whose infrastructure is known. In the Fair-NET problem, we are given an infrastructure of a tournament represented by a graph G and the initial rankings of the contestants represented by a multiset of integers S. The objective is to decide whether G is S-fair, i. e. , there exists an assignment of the contestants to the vertices of G such that the sum of the rankings of the neighbors of each contestant in G is the same constant k ∈ N. We initiate a study of the classical and parameterized complexity of Fair-NET with respect to several central structural parameters motivated by real world scenarios, thereby presenting a comprehensive picture of it.

PDF

EUMAS Conference 2021 Conference Paper

Parameterized Analysis of Assignment Under Multiple Preferences

  • Barak Steindl
  • Meirav Zehavi

Abstract The Assignment problem is a fundamental and well-studied problem in the intersection of Social Choice, Computational Economics and Discrete Allocation. In the Assignment problem, a group of agents expresses preferences over a set of items, and the task is to find a pareto optimal allocation of items to agents. We introduce a generalized version of this problem, where each agent is equipped with multiple incomplete preference lists: each list (called a layer ) is a ranking of items in a possibly different way according to a different criterion. We introduce the concept of global optimality, which extends the notion of pareto optimality to the multi-layered setting, and we focus on the problem of deciding whether a globally optimal assignment exists. We study this problem from the perspective of Parameterized Complexity: we consider several natural parameters such as the number of layers, the number of agents, the number of items, and the maximum length of a preference list. We present a comprehensive picture of the parameterized complexity of the problem with respect to these parameters.

Details

IJCAI Conference 2021 Conference Paper

Participatory Budgeting with Project Groups

  • Pallavi Jain
  • Krzysztof Sornat
  • Nimrod Talmon
  • Meirav Zehavi

We study a generalization of the standard approval-based model of participatory budgeting (PB), in which voters are providing approval ballots over a set of predefined projects and---in addition to a global budget limit---there are several groupings of the projects, each group with its own budget limit. We study the computational complexity of identifying project bundles that maximize voter satisfaction while respecting all budget limits. We show that the problem is generally intractable and describe efficient exact algorithms for several special cases, including instances with only few groups and instances where the group structure is close to being hierarchical, as well as efficient approximation algorithms. Our results could allow, e. g. , municipalities to hold richer PB processes that are thematically and geographically inclusive.

PDF Details DOI

EUMAS Conference 2021 Conference Paper

Verification of Multi-layered Assignment Problems

  • Barak Steindl
  • Meirav Zehavi

Abstract The class of assignment problems is a fundamental and well-studied class in the intersection of Social Choice, Computational Economics and Discrete Allocation. In a general assignment problem, a group of agents expresses preferences over a set of items, and the task is to allocate items to agents in an “optimal” way. A verification variant of this problem includes an allocation as part of the input, and the question becomes whether this allocation is “optimal”. In this paper, we generalize the verification variant to the setting where each agent is equipped with multiple incomplete preference lists: Each list (called a layer ) is a ranking of items in a possibly different way according to a different criterion. In particular, we introduce three multi-layer verification problems, each corresponds to an optimality notion that weakens the notion of global optimality (that is, pareto optimality in multiple layers) in a different way. Informally, the first notion requires that, for each group of agents whose size is exactly some input parameter k, the agents in the group will not be able to trade their assigned items among themselves and benefit in at least \(\alpha \) layers; the second notion is similar, but it concerns all groups of size at most k rather than exactly k; the third notion strengthens these notions by requiring that groups of k agents will not be part of possibly larger groups that benefit in at least \(\alpha \) layers. We study the three problems from the perspective of parameterized complexity under several natural parameterizations such as the number of layers, the number of agents, the number of items, the number of allocated items, the maximum length of a preference list, and more. We present an almost comprehensive picture of the parameterized complexity of the problems with respect to these parameters.

Details

SODA Conference 2020 Conference Paper

Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Meirav Zehavi

In this paper, we prove a new scaling lemma for vertex weighted minor free graphs that allows for a smooth trade-off between the weight of a vertex set S and the treewidth of G — S. More precisely, we show the following. There exists an algorithm that given an H- minor free graph G, a weight function w: V ( G ) → ℚ + and integers t and s, runs in polynomial time, and outputs a subset S ⊆ V ( G ) of weight at most d log n · opt( G, w, t )/s such that the treewidth of G – S is at most c·st. Here, d and c are fixed constants that depend only on H, and opt( G, w, t ) is the (unknown) minimum weight of a subset U ⊆ V ( G ) such that the treewidth of G – U is at most t. This lemma immediately yields the first polynomial-time approximation schemes (PTASes) for WEIGHTED T reewidth - η V ertex D eletion, for η > 2, on graphs of bounded genus and the first PTAS for W eighted F eedback vertex S et on H -minor free graphs. These results effortlessly generalize to include weighted edge deletion problems, to all W eighted C onnected P lanar -D eletion problems, and finally to quasi polynomial time approximation schemes (QPTASes) for all of these problems on H -minor free graphs. For most of these problems even constant factor approximation algorithms, even on planar graphs, were not previously known. Additionally, using the scaling lemma we subsume, simplify and extend the recent framework of Cohen-Addad et al. [STOC 2016] for turning constant factor approximation algorithms for “ubiquitous” problems into PTASes for the same problems on graphs of bounded genus. Specifically, we obtain PTASes for ubiquitous problems without the requirement of having a constant factor approximation. While the statement of the scaling lemma is inspired by an analogous lemma by Cohen-Addad et al. [STOC 2016] for edge contractions on weighted graphs of bounded genus, as well as a scaling lemma by Fomin et al. [SODA 2011] for unweighted graphs, the proof is entirely different. The proof detours via three different linear programming relaxations for the W eighted T reewidth - η V ertex D eletion problems and a strengthening of a recent rounding procedure of Bansal et al. [SODA 2017] enhanced by the classic Klein-Plotkin-Rao Theorem [STOC 1993].

Details

JAAMAS Journal 2020 Journal Article

Gehrlein stability in committee selection: parameterized hardness and algorithms

  • Sushmita Gupta
  • Pallavi Jain
  • Meirav Zehavi

Abstract In a multiwinner election based on the Condorcet criterion, we are given a set of candidates, and a set of voters with strict preference rankings over the candidates. A committee is weakly Gehrlein stable (WGS) if each committee member is preferred to each non-member by at least half of the voters. Recently, Aziz et al. [IJCAI 2017] studied the computational complexity of finding a WGS committee of size k. They show that this problem is NP -hard in general and polynomial-time solvable when the number of voters is odd. In this article, we initiate a systematic study of the problem in the realm of parameterized complexity. We first show that the problem is W[1] -hard when parameterized by the size of the committee. To overcome this intractability result, we use a known reformulation of WGS as a problem on directed graphs and then use parameters that measure the “structure” of these directed graphs. We show that the problem is fixed parameter tractable and admits linear kernels with respect to these parameters; and also present an exact-exponential time algorithm with running in time \({\mathcal {O}}(1. 2207^nn^{{\mathcal {O}}(1)})\), where n denotes the number of candidates.

Details DOI

JAIR Journal 2020 Journal Article

The Parameterized Complexity of Motion Planning for Snake-Like Robots

  • Siddharth Gupta
  • Guy Sa'ar
  • Meirav Zehavi

We study the parameterized complexity of a variant of the classic video game Snake that models real-world problems of motion planning. Given a snake-like robot with an initial position and a final position in an environment (modeled by a graph), our objective is to determine whether the robot can reach the final position from the initial position without intersecting itself. Naturally, this problem models a wide-variety of scenarios, ranging from the transportation of linked wagons towed by a locomotor at an airport or a supermarket to the movement of a group of agents that travel in an “ant-like” fashion and the construction of trains in amusement parks. Unfortunately, already on grid graphs, this problem is PSPACE-complete. Nevertheless, we prove that even on general graphs, the problem is solvable in FPT time with respect to the size of the snake. In particular, this shows that the problem is fixed-parameter tractable (FPT). Towards this, we show how to employ color-coding to sparsify the configuration graph of the problem to reduce its size significantly. We believe that our approach will find other applications in motion planning. Additionally, we show that the problem is unlikely to admit a polynomial kernel even on grid graphs, but it admits a treewidth-reduction procedure. To the best of our knowledge, the study of the parameterized complexity of motion planning problems (where the intermediate configurations of the motion are of importance) has so far been largely overlooked. Thus, our work is pioneering in this regard.

PDF Details DOI

MFCS Conference 2019 Conference Paper

A Sub-Exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs

  • Jayakrishnan Madathil
  • Roohani Sharma
  • Meirav Zehavi

Given an n-vertex digraph D and a non-negative integer k, the Minimum Directed Bisection problem asks if the vertices of D can be partitioned into two parts, say L and R, such that |L| and |R| differ by at most 1 and the number of arcs from R to L is at most k. This problem, in general, is W-hard as it is known to be NP-hard even when k=0. We investigate the parameterized complexity of this problem on semicomplete digraphs. We show that Minimum Directed Bisection on semicomplete digraphs is one of a handful of problems that admit sub-exponential time fixed-parameter tractable algorithms. That is, we show that the problem admits a 2^{O(sqrt{k} log k)}n^{O(1)} time algorithm on semicomplete digraphs. We also show that Minimum Directed Bisection admits a polynomial kernel on semicomplete digraphs. To design the kernel, we use (n, k, k^2)-splitters. To the best of our knowledge, this is the first time such pseudorandom objects have been used in the design of kernels. We believe that the framework of designing kernels using splitters could be applied to more problems that admit sub-exponential time algorithms via chromatic coding. To complement the above mentioned results, we prove that Minimum Directed Bisection is NP-hard on semicomplete digraphs, but polynomial time solvable on tournaments.

Details

SODA Conference 2019 Conference Paper

Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in Parameterized Complexity

  • Fahad Panolan
  • Saket Saurabh 0001
  • Meirav Zehavi

We give a new decomposition theorem in unit disk graphs (UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits a Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010] and H -minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi ( www. youtube. com/watch? v=2Bq2gy1N01w ) regarding the existence of contraction decompositions for classes of graphs beyond H -minor free graphs. Second, we present a “parameteric version” of our new decomposition theorem. We prove that there is an algorithm that given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of O ( k ) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into O ( k ) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece which is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or slightly superexponential) algorithms for well-studied problems such as M in B isection, S teiner C ut, s -W ay C ut, and E dge M ultiway C ut -U ncut on UDGs; these algorithms are substantially faster than the best known algorithms for these problems on general graphs.

Details

AAMAS Conference 2019 Conference Paper

Gehrlein Stability in Committee Selection: Parameterized Hardness and Algorithms

  • Sushmita Gupta
  • Pallavi Jain
  • Sanjukta Roy
  • Saket Saurabh
  • Meirav Zehavi

In a multiwinner election based on the Condorcet criterion, we are given a set of candidates, and a set of voters with strict preference ranking over the candidates. A committee is weakly Gehrlein stable (WGS) if each committee member is preferred to each non-member by at least half of the voters. Recently, Aziz et al. [IJCAI 2017] studied the computational complexity of finding a WGS committee of size k. They show that this problem is NP-hard in general and polynomial time solvable when the number of voters is odd. In this article, we initiate a systematic study of the problem in the realm of parameterized complexity. We first show that the problem is W[1]-hard when parameterized by the size of the committee. To overcome this intractability result, we use a known reformulation of WGS as a problem on directed graphs and then use parameters that measure the “structure” of these directed graphs. In particular, we consider the majority graph, defined as follows: there is a vertex corresponding to each candidate, and there is a directed arc from a candidate c to c′ if the number of voters that prefer c over c′ is more than those that prefer c′ over c. The problem of finding WGS committee of size k corresponds to finding a vertex subset X of size k in the majority graph with the following property: the set X contains no vertex outside the committee that has an in-neighbor in X. Observe that the polynomial time algorithm of Aziz et al. [IJCAI 2017] corresponds to solving the problem on a tournament (a complete graph with orientation on edges). Thus, natural parameters to study our problem are “closeness” to being a tournament. We define closeness as the number of missing arcs in the given directed graph and the number of vertices we need to delete from the given directed graph such that the resulting graph is a tournament. We show that the problem is fixed parameter tractable (FPT) and admits linear kernels with respect to closeness parameters. Finally, we also design an exact exponential time algorithm running in time O(1. 2207nnO(1)). Here, n denotes the number of candidates. Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), N. Agmon, M. E. Taylor, E. Elkind, M. Veloso (eds.), May 13–17, 2019, Montreal, Canada. © 2019 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). All rights reserved.

PDF

SODA Conference 2019 Conference Paper

Interval Vertex Deletion Admits a Polynomial Kernel

  • Akanksha Agrawal 0001
  • Pranabendu Misra
  • Saket Saurabh 0001
  • Meirav Zehavi

Given a graph G and an integer k, the I nterval V ertex D eletion (IVD) problem asks whether there exists a subset S ⊆ V ( G ) of size at most k such that G–S is an interval graph. This problem is known to be NP-complete [Yannakakis, STOC’78]. Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10 k n O (1) [Cao and Marx, SODA’14]. The existence of a polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this paper, we settle this problem in the affirmative. We also introduce a “bounded intersection” variant of the classical Two Families theorem of Bollobás. We believe this result will find further applications in combinatorics and algorithm design.

Details

IJCAI Conference 2019 Conference Paper

On Succinct Encodings for the Tournament Fixing Problem

  • Sushmita Gupta
  • Saket Saurabh
  • Ramanujan Sridharan
  • Meirav Zehavi

Single-elimination tournaments are a popular format in competitive environments. The Tournament Fixing Problem (TFP), which is the problem of finding a seeding of the players such that a certain player wins the resulting tournament, is known to be NP-hard in general and fixed-parameter tractable when parameterized by the feedback arc set number of the input tournament (an oriented complete graph) of expected wins/loses. However, the existence of polynomial kernelizations (efficient preprocessing) for TFP has remained open. In this paper, we present the first polynomial kernelization for TFP parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time routine that computes a SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.

PDF Details

MFCS Conference 2019 Conference Paper

Packing Arc-Disjoint Cycles in Tournaments

  • Stéphane Bessy
  • Marin Bougeret
  • R. Krithika 0001
  • Abhishek Sahu
  • Saket Saurabh 0001
  • Jocelyn Thiebaut
  • Meirav Zehavi

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT and ATT are fixed-parameter tractable, they can be solved in 2^{O(k log k)} n^{O(1)} time and 2^{O(k)} n^{O(1)} time respectively. Moreover, they both admit a kernel with O(k) vertices. We also prove that ACT and ATT cannot be solved in 2^{o(sqrt{k})} n^{O(1)} time under the Exponential-Time Hypothesis.

Details

JAAMAS Journal 2019 Journal Article

Stability in barter exchange markets

  • Sushmita Gupta
  • Fahad Panolan
  • Meirav Zehavi

Abstract The notion of stability is the foundation of several classic problems in economics and computer science that arise in a wide-variety of real-world situations, including Stable Marriage, Stable Roommate, Hospital Resident and Group Activity Selection. We study this notion in the context of barter exchange markets. The input of our problem of interest consists of a set of people offering goods/services, with each person subjectively assigning values to a subset of goods/services offered by other people. The goal is to find a stable transaction, a set of cycles that is stable in the following sense: there does not exist a cycle such that every person participating in that cycle prefers to his current “status”. For example, consider a market where families are seeking vacation rentals and offering their own homes for the same. Each family wishes to acquire a vacation home in exchange of its own home without any monetary exchange. We study such a market by analyzing a stable transaction of houses involving cycles of fixed length. The underlying rationale is that an entire trade/exchange fails if any of the participating agents cancels the agreement; as a result, shorter (trading) cycles are desirable. We show that given a transaction, it can be verified whether or not it is stable in polynomial time, and that the problem of finding a stable transaction is NP-hard even if each person desires only a small number of other goods/services. Having established these results, we study the problem of finding a stable transaction in the framework of parameterized algorithms.

Details DOI

IJCAI Conference 2019 Conference Paper

The Parameterized Complexity of Motion Planning for Snake-Like Robots

  • Siddharth Gupta
  • Guy Sa'ar
  • Meirav Zehavi

We study a motion-planning problem inspired by the game Snake that models scenarios like the transportation of linked wagons towed by a locomotor to the movement of a group of agents that travel in an ``ant-like'' fashion. Given a ``snake-like'' robot with initial and final positions in an environment modeled by a graph, our goal is to decide whether the robot can reach the final position from the initial position without intersecting itself. Already on grid graphs, this problem is PSPACE-complete [Biasi and Ophelders, 2018]. Nevertheless, we prove that even on general graphs, it is solvable in time k^{O(k)}|I|^{O(1)} where k is the size of the robot, and |I| is the input size. Towards this, we give a novel application of color-coding to sparsify the configuration graph of the problem. We also show that the problem is unlikely to have a polynomial kernel even on grid graphs, but it admits a treewidth-reduction procedure. To the best of our knowledge, the study of the parameterized complexity of motion problems has been~largely~neglected, thus our work is pioneering in this regard.

PDF Details

SODA Conference 2018 Conference Paper

Cliquewidth III: The Odd Case of Graph Coloring Parameterized by Cliquewidth

  • Petr A. Golovach
  • Daniel Lokshtanov
  • Saket Saurabh 0001
  • Meirav Zehavi

M ax -C ut (MC), E dge D ominating S et (EDS), G raph C oloring (GC) and H amiltonian P ath (HP) on graphs of bounded cliquewidth have received significant attention as they can be formulated in MSO 2 (and therefore have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle's theorem), but cannot be formulated in MSO 1 (which would have yielded linear-time algorithms on bounded cliquewidth graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g ( k ) n f ( k ) on graphs of cliquewidth k. Fomin et al. [ Intractability of Clique-Width Parameterizations. SIAM J. Comput. 39(5): 1941–1956 (2010) ] showed that the running times cannot be improved to g ( k ) n O (1) assuming W[1]≠FPT. However, this does not rule out nontrivial improvements to the exponent f ( k ) in the running times. In a follow-up paper, Fomin et al. [ Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. SIAM J. Comput. 43(5): 1541–1563 (2014) ] improved the running times for EDS and MC to n O ( k ), and proved g ( k ) n o ( k ) lower bounds for EDS, MC and HP assuming the ETH. Recently, Bergougnoux, Kante and Kwon [ WADS 2017 ] gave an n O ( k ) -time algorithm for HP. Thus, prior to this work, EDS, MC and HP were known to have tight n Θ( k ) algorithmic upper and lower bounds. In contrast, GC has an upper bound of n O (2 k ) and a lower bound of merely (implicit from the W[1]-hardness proof). In this paper, we close the gap for GC by proving a lower bound of n 2 o ( k ) This shows that GC behaves qualitatively different from the other three problems. To the best of our knowledge, GC is the first natural problem known to require exponential dependence on the parameter in the exponent of n.

Details

SODA Conference 2018 Conference Paper

Parameterized Algorithms for Survivable Network Design with Uniform Demands

  • Jørgen Bang-Jensen
  • Manu Basavaraju
  • Kristine Vitting Klinkby
  • Pranabendu Misra
  • M. S. Ramanujan 0001
  • Saket Saurabh 0001
  • Meirav Zehavi

In the S urvivable N etwork D esign P roblem (SNDP), the input is an edge-weighted (di)graph G and an integer r uυ for every pair of vertices u, υ ∊ V ( G ). The objective is to construct a subgraph H of minimum weight which contains r uυ edge-disjoint (or node-disjoint) u-υ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-E dge C onnected S ubgraph (λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-V ertex C onnected S ubgraph (λ-VCS) problem. We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2 O ( k log k ) | V ( G )| O (1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical M inimum E quivalent G raph (MEG) problem. We also show that λ-Ves is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs.

Details

AAMAS Conference 2018 Conference Paper

Stability in Barter Exchange Markets

  • Sushmita Gupta
  • Fahad Panolan
  • Saket Saurabh
  • Meirav Zehavi

The notion of stability is the foundation of several classic problems in economics and computer science that arise in a wide-variety of real-world situations, including Stable Marriage, Stable Roommate, Hospital Resident and Group Activity Selection. We study this notion in the context of barter exchange markets. The input of our problem of interest consists of a set of people offering goods/services, with each person subjectively assigning values to a subset of goods/services offered by other people. The goal is to find a stable transaction, a set of cycles that is stable in the following sense: there does not exist a cycle such that every person participating in that cycle prefers to his current “status”. For example, consider a market where families are seeking vacation rentals and offering their own homes for the same. Each family wishes to acquire a vacation home in exchange of its own home without any monetary exchange. We study such a market by analyzing a stable transaction of houses involving cycles of fixed length. The underlying rationale is that an entire trade/exchange fails if any of the participating agents cancels the agreement; as a result, shorter (trading) cycles are desirable. We show that given a transaction, it can be verified whether or not it is stable in polynomial time, and that the problem of finding a stable transaction is NP-hard even if each person desires only a small number of other goods/services. Having established these results, we study the problem of finding a stable transaction in the framework of parameterized algorithms.

PDF

IJCAI Conference 2018 Conference Paper

When Rigging a Tournament, Let Greediness Blind You

  • Sushmita Gupta
  • Sanjukta Roy
  • Saket Saurabh
  • Meirav Zehavi

A knockout tournament is a standard format of competition, ubiquitous in sports, elections and decision making. Such a competition consists of several rounds. In each round, all players that have not yet been eliminated are paired up into matches. Losers are eliminated, and winners are raised to the next round, until only one winner exists. Given that we can correctly predict the outcome of each potential match (modelled by a tournament D), a seeding of the tournament deterministically determines its winner. Having a favorite player v in mind, the Tournament Fixing Problem (TFP) asks whether there exists a seeding that makes v the winner. Aziz et al. [AAAI’14] showed that TFP is NP-hard. They initiated the study of the parameterized complexity of TFP with respect to the feedback arc set number k of D, and gave an XP-algorithm (which is highly inefficient). Recently, Ramanujan and Szeider [AAAI’17] showed that TFP admits an FPT algorithm, running in time 2^{ O(k^2 log k)} n ^{O(1)}. At the heart of this algorithm is a translation of TFP into an algebraic system of equations, solved in a black box fashion (by an ILP solver). We present a fresh, purely combinatorial greedy solution. We rely on new insights into TFP itself, which also results in the better running time bound of 2^{ O(k log k)} n^{ O(1)}. While our analysis is intricate, the algorithm itself is surprisingly simple.

PDF Details

IJCAI Conference 2018 Conference Paper

Winning a Tournament by Any Means Necessary

  • Sushmita Gupta
  • Sanjukta Roy
  • Saket Saurabh
  • Meirav Zehavi

In a tournament, $n$ players enter the competition. In each round, they are paired-up to compete against each other. Losers are thrown, while winners proceed to the next round, until only one player (the winner) is left. Given a prediction of the outcome, for every pair of players, of a match between them (modeled by a digraph $D$), the competitive nature of a tournament makes it attractive for manipulators. In the Tournament Fixing (TF) problem, the goal is to decide if we can conduct the competition (by controlling how players are paired-up) so that our favorite player $w$ wins. A common form of manipulation is to bribe players to alter the outcome of matches. Kim and Williams [IJCAI 2015] integrated such deceit into TF, and showed that the resulting problem is NP-hard when $\ell 0$). For this problem, our contribution is fourfold. First, we present two operations that ``obfuscate deceit'': given one solution, they produce another solution. Second, we present a combinatorial result, stating that there is always a solution with all reversals incident to $w$ and ``elite players''. Third, we give a closed formula for the case where $D$ is a DAG. Finally, we present exact exponential-time and parameterized algorithms for the general case.

PDF Details

SODA Conference 2017 Conference Paper

Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

  • Akanksha Agrawal 0001
  • Daniel Lokshtanov
  • Pranabendu Misra
  • Saket Saurabh 0001
  • Meirav Zehavi

Given a graph G and a parameter k, the C hordal V ertex D eletion (CVD) problem asks whether there exists a subset U ⊆ V ( G ) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size O ( k 161 log 58 k ), and asked whether one can design a kernel of size O ( k 10 ). While we do not completely resolve this question, we design a significantly smaller kernel of size O ( k 25 log 14 k ), inspired by the O ( k 2 )-size kernel for F eedback V ertex S et. To obtain this result, we first design an O (opt-log 2 n )-factor approximation algorithm for CVD, which is central to our kernelization procedure. Thus, we improve upon both the kernelization algorithm and the approximation algorithm of Jansen and Pilipczuk. Next, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution. We believe that this notion could be useful in designing kernels for other problems.

Details

MFCS Conference 2017 Conference Paper

Parameterized Algorithms and Kernels for Rainbow Matching

  • Sushmita Gupta
  • Sanjukta Roy 0001
  • Saket Saurabh 0001
  • Meirav Zehavi

In this paper, we study the NP-complete colorful variant of the classical Matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, this problem asks whether there exists a matching of size at least k such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves Rainbow Matching on paths in time O*(((1+\sqrt{5})/2)^k) and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a "divide-and-conquer-like" approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures "divided-and-conquered" pieces of the path. Our second result is a randomized algorithm that solves Rainbow Matching on general graphs in time O*(2^k) and polynomial space. Here, we show how a result by Björklund et al. [JCSS, 2017] can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for Rainbow Matching on general and bounded-degree graphs.

Details

MFCS Conference 2013 Conference Paper

Parameterized Algorithms for Module Motif

  • Meirav Zehavi

Abstract Module Motif is a pattern matching problem that was introduced in the context of biological networks. Informally, given a multiset of colors P and a graph H whose nodes have sets of colors, it asks if P occurs in a module of H (i. e. in a set of nodes that have the same neighborhood outside the set). We present three parameterized algorithms for this problem that measure similarity between matched colors and handle deletions and insertions of colors to P. We observe that the running time of two of them might be essentially tight and prove that the problem is unlikely to admit a polynomial kernel.

Details