Arrow Research search

Author name cluster

Neeldhara Misra

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.

34 papers
2 author rows

Possible papers

34

AAAI Conference 2026 Conference Paper

The Cost and Complexity of Minimizing Envy in House Allocations (Abstract Reprint)

  • Jayakrishnan Madathil
  • Neeldhara Misra
  • Aditi Sethia

We study almost envy-freeness in house allocation, where m houses are to be allocated among n agents so that every agent receives exactly one house. An envy-free allocation need not exist, and therefore we may have to settle for relaxations. We study different aggregate measures of envy as markers of fairness. In particular, we define the amount of envy experienced by an agent a w.r.t. an allocation to be the number of agents that agent a envies under that allocation. We quantify the envy generated by an allocation using three different metrics: 1) the number of agents who are envious; 2) the maximum amount of envy experienced by any agent; and 3) the total amount of envy experienced by all agents, and look for allocations that minimize one of the three metrics. We prove a host of algorithmic and hardness results. We also suggest practical approaches for these problems via integer linear program (ILP) formulations and report the findings of our experimental evaluation of ILPs. Finally, we study the price of fairness, which quantifies the loss of welfare we must suffer due to the fairness requirements, and present tight bounds as well as algorithms that simultaneously optimize both welfare and fairness.

PDF Details DOI

JAAMAS Journal 2025 Journal Article

The Cost and Complexity of Minimizing Envy in House Allocation

  • Jayakrishnan Madathil
  • Neeldhara Misra
  • Aditi Sethia

Abstract We study almost envy-freeness in house allocation, where m houses are to be allocated among n agents so that every agent receives exactly one house. An envy-free allocation need not exist, and therefore we may have to settle for relaxations. We study different aggregate measures of envy as markers of fairness. In particular, we define the amount of envy experienced by an agent a w. r. t. an allocation to be the number of agents that agent a envies under that allocation. We quantify the envy generated by an allocation using three different metrics: 1) the number of agents who are envious; 2) the maximum amount of envy experienced by any agent; and 3) the total amount of envy experienced by all agents, and look for allocations that minimize one of the three metrics. We prove a host of algorithmic and hardness results. We also suggest practical approaches for these problems via integer linear program (ILP) formulations and report the findings of our experimental evaluation of ILPs. Finally, we study the price of fairness, which quantifies the loss of welfare we must suffer due to the fairness requirements, and present tight bounds as well as algorithms that simultaneously optimize both welfare and fairness.

Details DOI

AAMAS Conference 2024 Conference Paper

Opinion Diffusion on Society Graphs Based on Approval Ballots

  • Jayakrishnan Madathil
  • Neeldhara Misra
  • Yash More

A society graph, as considered by [Faliszewski et al. , IJCAI 2018], is a graph corresponding to an election instance where every possible ranking is a node, and the weight of such a node is given by the number of voters whose vote correspond to the said ranking. A natural diffusion process on this graph is defined, and an immediate question that emerges is whether there is a diffusion path that leads to a particular candidate winning according to a certain voting rule—this turns out to be NP-complete. In this contribution, we consider the setting when votes are approval ballots, as opposed to rankings—and we consider both the possible and necessary winner problems. We demonstrate that it is possible to efficiently determine if a candidate is a possible winner (i. e, if there exists a diffusion path along which a given candidate wins the election) if the underlying society graph is a star (i. e, tree of diameter at most two), while the problem is NP-complete for trees of diameter d for d > 2. Analogously, we show that it is possible to efficiently determine if a candidate is a necessary winner (i. e, a winner for every possible diffusion path) if the underlying society graph is a star, while the problem is coNP-complete for trees of diameter d for d > 2. We also show the following results on structured graphs for the possible winner problem: the problem is strongly NP-complete on a disjoint union of paths, and on trees of constant diameter. We also report preliminary experiments from an ILP-based implementation.

PDF

MFCS Conference 2023 Conference Paper

Spartan Bipartite Graphs Are Essentially Elementary

  • Neeldhara Misra
  • Saraswati Girish Nanoti

We study a two-player game on a graph between an attacker and a defender. To begin with, the defender places guards on a subset of vertices. In each move, the attacker attacks an edge. The defender must move at least one guard across the attacked edge to defend the attack. The defender wins if and only if the defender can defend an infinite sequence of attacks. The smallest number of guards with which the defender has a winning strategy is called the eternal vertex cover number of a graph G and is denoted by evc(G). It is clear that evc(G) is at least mvc(G), the size of a minimum vertex cover of G. We say that G is Spartan if evc(G) = mvc(G). The characterization of Spartan graphs has been largely open. In the setting of bipartite graphs on 2n vertices where every edge belongs to a perfect matching, an easy strategy is to have n guards that always move along perfect matchings in response to attacks. We show that these are essentially the only Spartan bipartite graphs.

Details

AAMAS Conference 2023 Conference Paper

The Complexity of Minimizing Envy in House Allocation

  • Jayakrishnan Madathil
  • Neeldhara Misra
  • Aditi Sethia

The house allocation problem asks for m houses to be allocated among n agents so that every agent receives exactly one house. The preferences of the agents over houses can be modeled as weak orders, of which two special cases are strict rankings and binary valuations. Given an allocation ϕ of houses to agents, an agent a envies agent b if a receives a house ϕ(a) that they like strictly less than ϕ(b), the house allocated to b. The amount of envy experienced by an agent a is the number of agents b that it envies with respect to ϕ. We consider the computational problem of finding allocations that minimize: the number of agents who are envious, the maximum envy experienced by any agent, or the total amount of envy experienced by all agents. We investigate the complexity of all three optimization objectives for both strict rankings as well as binary valuations. We show that these problems are FPT when parameterized by the number of houses and the number of agents. When parameterized by solution size, i. e, the value of the optimization objective, we demonstrate W-hardness in the first objective and para-NP-hardness for the last objective. We also consider these questions in the setting of restricted domains and also suggest practical approaches for these problems via ILP formulations.

PDF

IJCAI Conference 2020 Conference Paper

On the Complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules

  • Chinmay Sonar
  • Palash Dey
  • Neeldhara Misra

The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) dissatisfaction score of at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee? , and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for Theta_2^P. Our contribution fills an essential gap in the literature for these important multi-winner rules.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

A Parameterized Perspective on Protecting Elections

  • Palash Dey
  • Neeldhara Misra
  • Swaprava Nath
  • Garima Shakya

We study the parameterized complexity of the optimal defense and optimal attack problems in voting. In both the problems, the input is a set of voter groups (every voter group is a set of votes) and two integers k_a and k_d corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the optimal defense problem, we want to know if it is possible for the defender to commit to a strategy of defending at most k_d voter groups such that, no matter which k_a voter groups the attacker attacks, the out-come of the election does not change. In the optimal attack problem, we want to know if it is possible for the attacker to commit to a strategy of attacking k_a voter groups such that, no matter which k_d voter groups the defender defends, the outcome of the election is always different from the original (without any attack) one. We show that both the optimal defense problem and the optimal attack problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only3candidates. We also show that the optimal defense problem for every scoring rule and the Condorcet voting rule is W[2]-hard for both the parameters k_a and k_d, while it admits a fixed parameter tractable algorithm parameterized by the combined parameter (ka, kd). The optimal attack problem for every scoring rule and the Condorcet voting rule turns out to be much harder – it is W[1]-hard even for the combined parameter (ka, kd). We propose two greedy algorithms for the OPTIMAL DEFENSE problem and empirically show that they perform effectively on reasonable voting profiles.

PDF Details

MFCS Conference 2017 Conference Paper

On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

  • Palash Dey
  • Neeldhara Misra

We consider election scenarios with incomplete information, a situation that arises often in practice. There are several models of incomplete information and accordingly, different notions of outcomes of such elections. In one well-studied model of incompleteness, the votes are given by partial orders over the candidates. In this context we can frame the problem of finding a possible winner, which involves determining whether a given candidate wins in at least one completion of a given set of partial votes for a specific voting rule. The Possible Winner problem is well-known to be NP-Complete in general, and it is in fact known to be NP-Complete for several voting rules where the number of undetermined pairs in every vote is bounded only by some constant. In this paper, we address the question of determining precisely the smallest number of undetermined pairs for which the Possible Winner problem remains NP-Complete. In particular, we find the exact values of t for which the Possible Winner problem transitions to being NP-Complete from being in P, where t is the maximum number of undetermined pairs in every vote. We demonstrate tight results for a broad subclass of scoring rules which includes all the commonly used scoring rules (such as plurality, veto, Borda, and k-approval), Copeland^\alpha for every \alpha in [0, 1], maximin, and Bucklin voting rules. A somewhat surprising aspect of our results is that for many of these rules, the Possible Winner problem turns out to be hard even if every vote has at most one undetermined pair of candidates.

Details

AAMAS Conference 2017 Conference Paper

Parameterized Dichotomy of Choosing Committees Based on Approval Votes in the Presence of Outliers

  • Palash Dey
  • Neeldhara Misra
  • Y. Narahari

Approval ballots provide an opportunity for agents to make a comment about every candidate, without incurring the overhead of determining a full ranking on the set of candidates; they are very natural for many practical settings. We study the computational complexity of the committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outliers render the committee selection problem intractable for approval, net approval, and minisum approval voting rules. We next study the parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter namely the number of candidates outside the committee); and the number of outliers (and its dual parameter namely the number of non-outliers). For approval, net approval, and minisum approval voting rules, we provide a dichotomous result, which resolves the parameterized complexity of this problem for all subsets of the above five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters). CCS Concepts •Theory of computation → Analysis of Algorithms and Problem Complexity; •Distributed Artificial Intelligence → Multi-agent Systems;

PDF

IJCAI Conference 2016 Conference Paper

Complexity of Manipulation with Partial Information in Voting

  • Palash Dey
  • Neeldhara Misra
  • Y. Narahari

The Coalitional Manipulation problem has been studied extensively in the literature for many voting rules. However, most studies have focused on the complete information setting, wherein the manipulators know the votes of the non-manipulators. While this assumption is reasonable for purposes of showing intractability, it is unrealistic for algorithmic considerations. In most real-world scenarios, it is impractical for the manipulators to have accurate knowledge of all the other votes. In this paper, we investigate manipulation with incomplete information. In our framework, the manipulators know a partial order for each voter that is consistent with the true preference of that voter. In this setting, we formulate three natural computational notions of manipulation, namely weak, opportunistic, and strong manipulation. We consider several scenarios for which the traditional manipulation problems are easy (for instance, Borda with a single manipulator). For many of them, the corresponding manipulative questions that we propose turn out to be computationally intractable. Our hardness results often hold even when very little information is missing, or in other words, even when the instances are quite close to the complete information setting. Our overall conclusion is that computational hardness continues to be a valid obstruction to manipulation, in the context of a more realistic model.

PDF Details

IJCAI Conference 2016 Conference Paper

Elicitation for Preferences Single Peaked on Trees

  • Palash Dey
  • Neeldhara Misra

Eliciting preferences of a set of agents over a set of items is a problem of fundamental interest in artificial intelligence in general and social choice theory in particular. Prior works on preference elicitation focus on unrestricted domain and the domain of single peaked preferences and show that the preferences in single peaked domain can be elicited by much less number of queries compared to unrestricted domain. We extend this line of research and study preference elicitation for single peaked preferences on trees which is a strict superset of the domain of single peaked preferences. We show that the query complexity crucially depends on the number of leaves, the path cover number, and the distance from path of the underlying single peaked tree, whereas the other natural parameters like maximum degree, diameter, pathwidth do not play any direct role in determining query complexity. We then investigate the query complexity for finding a weak Condorcet winner for preferences single peaked on a tree and show that this task has much less query complexity than preference elicitation. Here again we observe that the number of leaves in the underlying single peaked tree and the path cover number of the tree influence the query complexity of the problem.

PDF Details

AAAI Conference 2016 Conference Paper

Frugal Bribery in Voting

  • Palash Dey
  • Neeldhara Misra
  • Y. Narahari

Bribery in elections is an important problem in computational social choice theory. We introduce and study two important special cases of the bribery problem, namely, FRUGAL- BRIBERY and FRUGAL-$BRIBERY where the briber is frugal in nature. By this, we mean that the briber is only able to influence voters who benefit from the suggestion of the briber. More formally, a voter is vulnerable if the outcome of the election improves according to her own preference when she accepts the suggestion of the briber. In the FRUGAL-BRIBERY problem, the goal is to make a certain candidate win the election by changing only the vulnerable votes. In the FRUGAL- $BRIBERY problem, the vulnerable votes have prices and the goal is to make a certain candidate win the election by changing only the vulnerable votes, subject to a budget constraint. We show that both the FRUGAL-BRIBERY and the FRUGAL- $BRIBERY problems are intractable for many commonly used voting rules for weighted as well as unweighted elections. These intractability results demonstrate that bribery is a hard computational problem, in the sense that several special cases of this problem continue to be computationally intractable. This strengthens the view that bribery, although a possible attack on an election in principle, may be infeasible in practice.

PDF Details

AAMAS Conference 2016 Conference Paper

On the Computational Hardness of Manipulating Pairwise Voting Rules

  • Rohit Vaish
  • Neeldhara Misra
  • Shivani Agarwal
  • Avrim Blum

Standard voting rules usually assume that the preferences of voters are provided in the form of complete rankings over a fixed set of alternatives. This assumption does not hold in applications like recommendation systems where the set of alternatives is extremely large and only partial preferences can be elicited. In this paper, we study the problem of strategic manipulation of voting rules that aggregate voter preferences provided in the form of pairwise comparisons between alternatives. Our contributions are twofold: first, we show that any onto pairwise voting rule is manipulable in principle. Next, we analyze how the computational complexity of manipulation of such rules varies with the structure of the graph induced by the pairs of alternatives that the manipulator is allowed to vote over and the type of the preference relation. Building on natural connections between the pairwise manipulation and sports elimination problems (including a mixed-elimination variant that we introduce in this paper), we show that manipulating pairwise voting rules can be computationally hard even in the single-manipulator setting, a setting where most standard voting rules are known to be easy to manipulate. General Terms Algorithms, Economics, Theory

PDF

IJCAI Conference 2016 Conference Paper

Preference Elicitation for Single Crossing Domain

  • Palash Dey
  • Neeldhara Misra

Eliciting the preferences of a set of agents over a set of alternatives is a problem of fundamental importance in social choice theory. Prior work on this problem has studied the query complexity of preference elicitation for the unrestricted domain and for the domain of single peaked preferences. In this paper, we consider the domain of single crossing preference profiles and study the query complexity of preference elicitation under various settings. We consider two distinct situations: when an ordering of the voters with respect to which the profile is single crossing is known versus when it is unknown. We also consider random and sequential access models. The main contribution of our work is to provide polynomial time algorithms with low query complexity for preference elicitation in all the above cases. Further, we show that the query complexities of our algorithms are optimal up to constant factors for all but one of the above cases.

PDF Details

AAAI Conference 2016 Conference Paper

Randomised Procedures for Initialising and Switching Actions in Policy Iteration

  • Shivaram Kalyanakrishnan
  • Neeldhara Misra
  • Aditya Gopalan

Policy Iteration (PI) (Howard 1960) is a classical method for computing an optimal policy for a finite Markov Decision Problem (MDP). The method is conceptually simple: starting from some initial policy, “policy improvement” is repeatedly performed to obtain progressively dominating policies, until eventually, an optimal policy is reached. Being remarkably efficient in practice, PI is often favoured over alternative approaches such as Value Iteration and Linear Programming. Unfortunately, even after several decades of study, theoretical bounds on the complexity of PI remain unsatisfactory. For an MDP with n states and k actions, Mansour and Singh (1999) bound the number of iterations taken by Howard’s PI, the canonical variant of the method, by Opkn {nq. This bound merely improves upon the trivial bound of kn by a linear factor. However, a randomised variant of PI introduced by Mansour and Singh (1999) does yield an exponential improvement, with its expected number of iterations bounded by O ppp1 ` 2{ log2pkqq k{2qn q. With the objective of furnishing improved upper bounds for PI, we introduce two randomised procedures in this paper. Our first contribution is a routine to find a good initial policy for PI. After evaluating a number of randomly generated policies, this procedure applies a novel criterion to pick one to initialise PI. When PI is subsequently applied, we show that the expected number of policy evaluations—including both the initialisation and the improvement stages—remains bounded in expectation by Opkn{2 q. The key construction employed in this routine is a total order on the set of policies. Our second contribution is a randomised action-switching rule for PI, which admits a bound of p2 ` lnpk ´ 1qqn on the expected number of iterations. To the best of our knowledge, this is the tightest complexity bound known for PI when k ě 3.

PDF Details

AAAI Conference 2014 Conference Paper

Backdoors into Heterogeneous Classes of SAT and CSP

  • Serge Gaspers
  • Neeldhara Misra
  • Sebastian Ordyniak
  • Stefan Szeider
  • Stanislav Zivny

Backdoor sets represent clever reasoning shortcuts through the search space for SAT and CSP. By instantiating the backdoor variables one reduces the given instance to several easy instances that belong to a tractable class. The overall time needed to solve the instance is exponential in the size of the backdoor set, hence it is a challenging problem to find a small backdoor set if one exists; over the last years this problem has been subject of intensive research. In this paper we extend the classical notion of a strong backdoor set by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong backdoor sets into heterogeneous base classes for SAT and CSP. We provide algorithms that establish fixedparameter tractability under natural parameterizations, and we contrast the tractability results with hardness results that pinpoint the theoretical limits. Our results apply to the current state-of-the-art of tractable classes of CSP and SAT that are definable by restricting the constraint language.

PDF Details

MFCS Conference 2013 Conference Paper

On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

  • Prachi Goyal
  • Vikram Kamat
  • Neeldhara Misra

Abstract We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q ≥ 2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q ≥ 2, and has been well-studied from the point of view of approximation. Our main focus is the case when q = 2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

Details

MFCS Conference 2013 Conference Paper

Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?

  • Neeldhara Misra
  • Fahad Panolan
  • Saket Saurabh 0001

Abstract The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually “not too far apart”, without necessarily being adjacent. One such generalization is realized by structures called s-clubs, which are graphs of diameter at most s. In this work, we study the question of finding a set of at most k edges whose removal leaves us with a graph whose components are s -clubs. Recently, it has been shown that unless Exponential Time Hypothesis fail (ETH) fails Cluster Editing (whose components are 1-clubs) does not admit sub-exponential time algorithm [ STACS, 2013 ]. That is, there is no algorithm solving the problem in time 2 o ( k ) n O (1). However, surprisingly they show that when the number of cliques in the output graph is restricted to d, then the problem can be solved in time \(O(2^{O(\sqrt{dk})}+m+n)\). We show that this sub-exponential time algorithm for the fixed number of cliques is rather an exception than a rule. Our first result shows that assuming the ETH, there is no algorithm solving the s -Club Cluster Edge Deletion problem in time 2 o ( k ) n O (1). We show, further, that even the problem of deleting edges to obtain a graph with d s -clubs cannot be solved in time 2 o ( k ) n O (1) for any fixed s, d ≥ 2. This is a radical contrast from the situation established for cliques, where sub-exponential algorithms are known.

Details

SAT Conference 2013 Conference Paper

Upper and Lower Bounds for Weak Backdoor Set Detection

  • Neeldhara Misra
  • Sebastian Ordyniak
  • Venkatesh Raman 0001
  • Stefan Szeider

Abstract We obtain upper and lower bounds for running times of exponential time algorithms for the detection of weak backdoor sets of 3CNF formulas, considering various base classes. These results include (omitting polynomial factors), (i) a 4. 54 k algorithm to detect whether there is a weak backdoor set of at most k variables into the class of Horn formulas; (ii) a 2. 27 k algorithm to detect whether there is a weak backdoor set of at most k variables into the class of Krom formulas. These bounds improve an earlier known bound of 6 k. We also prove a 2 k lower bound for these problems, subject to the Strong Exponential Time Hypothesis.

Details

FOCS Conference 2012 Conference Paper

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms

  • Fedor V. Fomin
  • Daniel Lokshtanov
  • Neeldhara Misra
  • Saket Saurabh 0001

Let F be a finite set of graphs. In the F-DELETION problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k vertices can be deleted from G such that the resulting graph does not contain a graph from F as a minor. F-DELETION is a generic problem and by selecting different sets of forbidden minors F, one can obtain various fundamental problems such as VERTEX COVER, FEEDBACK VERTEX SET or TREEWIDTH η-DELETION. In this paper we obtain a number of generic algorithmic results about F-DELETION, when F contains at least one planar graph. The highlights of our work are · A constant factor approximation algorithm for the optimization version of F-DELETION; · A linear time and single exponential parameterized algorithm, that is, an algorithm running in time O(2 O(k) n), for the parameterized version of F-DELETION where all graphs in F are connected; · A polynomial kernel for parameterized F-DELETION. These algorithms unify, generalize, and improve a multitude of results in the literature. Our main results have several direct applications, but also the methods we develop on the way have applicability beyond the scope of this paper. Our results - constant factor approximation, polynomial kernelization and FPT algorithms - are stringed together by a common theme of polynomial time preprocessing.

Details

MFCS Conference 2010 Conference Paper

Solving minones-2-sat as Fast as vertex cover

  • Neeldhara Misra
  • N. S. Narayanaswamy
  • Venkatesh Raman 0001
  • Bal Sri Shankar

Abstract The problem of finding a satisfying assignment for a 2-SAT formula that minimizes the number of variables that are set to 1 ( min ones 2 –sat ) is NP-complete. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from min ones 2 –sat to vertex cover without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2 k variables kernel subsuming these results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover.

Details