Arrow Research search

Author name cluster

Prabhakar Ragde

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.

6 papers
2 author rows

Possible papers

6

SAT Conference 2006 Conference Paper

Solving #SAT Using Vertex Covers

  • Naomi Nishimura
  • Prabhakar Ragde
  • Stefan Szeider

Abstract We propose an exact algorithm for counting the models of propositional formulas in conjunctive normal form (CNF). Our algorithm is based on the detection of strong backdoor sets of bounded size; each instantiation of the variables of a strong backdoor set puts the given formula into a class of formulas for which models can be counted in polynomial time. For the backdoor set detection we utilize an efficient vertex cover algorithm applied to a certain “obstruction graph” that we associate with the given formula. This approach gives rise to a new hardness index for formulas, the clustering-width. Our algorithm runs in uniform polynomial time on formulas with bounded clustering-width. It is known that the number of models of formulas with bounded clique-width, bounded treewidth, or bounded branchwidth can be computed in polynomial time; these graph parameters are applied to formulas via certain (hyper)graphs associated with formulas. We show that clustering-width and the other parameters mentioned are incomparable: there are formulas with bounded clustering-width and arbitrarily large clique-width, treewidth, and branchwidth. Conversely, there are formulas with arbitrarily large clustering-width and bounded clique-width, treewidth, and branchwidth.

Details

SAT Conference 2004 Conference Paper

Detecting Backdoor Sets with Respect to Horn and Binary Clauses

  • Naomi Nishimura
  • Prabhakar Ragde
  • Stefan Szeider

We study the parameterized complexity of detecting backdoor sets for instances of the propositional satisfiability problem (SAT) with respect to the polynomially solvable classes horn and 2-cnf. A backdoor set is a subset of variables; for a strong backdoor set, the simplified formulas resulting from any setting of these variables is in a polynomially solvable class, and for a weak backdoor set, there exists one setting which puts the satisfiable simplified formula in the class. We show that with respect to both horn and 2-cnf classes, the detection of a strong backdoor set is fixed-parameter tractable (the existence of a set of size k for a formula of length N can be decided in time f (k)N O(1) ), but that the detection of a weak backdoor set is W[2]-hard, implying that this problem is not fixed-parameter tractable.

Details

TCS Journal 1989 Journal Article

On separating the EREW and CREW PRAM models

  • Eli Gafni
  • Joseph Naor
  • Prabhakar Ragde

In (1985), Snir proposed the Selection Problem (searching in a sorted table) to show that the CREW PRAM is strictly more powerful than the EREW PRAM. This problem defines a partial function, that is, one that is defined only on a restricted set of inputs. Recognizing whether an arbitrary input belongs to this restricted set is hard for both CREW and EREW PRAMs. The existence of a total function that exhibits the power of the CREW model over the EREW model was an open problem. Here we solve this problem by generalizing the Selection Problem to a decision tree problem which is defined on a full domain and to which Snir's lower bound applies.

Details DOI

FOCS Conference 1987 Conference Paper

Incomparability in Parallel Computation

  • Vince Grolmusz
  • Prabhakar Ragde

We consider the relative power of concurrentwrite PRAMs when the number of processors (and input variables) is fixed at n, and infinite shared memory is allowed. Several different models (COMMON, ARBITRARY, PRIORITY) have been used for algorithm design in the literature; these models differ in their method of write-conflict resolution. Recent work in separating these models ([FRW1, 2, 3], [LY]) has relied on further restrictions (limiting the size of memory or the power of processors); the only unrestricted results known concern the element distinctness problem ([FMW], [RSSW]). In this paper we contribute further unrestricted results. We consider the COLLISION model, a natural generalization of the Ethernet ([G]). Our main result is a lower bound of Ω(logloglogn) steps on COLLISION for a problem that can be done in O(1) steps on ARBITRARY. We use this result, together with a reduction performed by means of Ramsey's Theorem, to show that the powers of COMMON and COLLISION are incomparable. We also introduce a new and natural model, TOLERANT, and show that it is strictly less powerful than COLLISION and incomparable with COMMON. The proofs involved use combinatorial arguments, including Turán's Theorem for graphs and the Erdös-Rado intersecting set theorem.

Details