Search Results

Documents authored by Mittal, Harshil

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.50
On the Parameterized Complexity of Diverse SAT

Authors: Neeldhara Misra, Harshil Mittal, and Ashutosh Rai

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We study the Boolean Satisfiability problem (SAT) in the framework of diversity, where one asks for multiple solutions that are mutually far apart (i.e., sufficiently dissimilar from each other) for a suitable notion of distance/dissimilarity between solutions. Interpreting assignments as bit vectors, we take their Hamming distance to quantify dissimilarity, and we focus on the problem of finding two solutions. Specifically, we define the problem Max Differ SAT (resp. Exact Differ SAT) as follows: Given a Boolean formula ϕ on n variables, decide whether ϕ has two satisfying assignments that differ on at least (resp. exactly) d variables. We study the classical and parameterized (in parameters d and n-d) complexities of Max Differ SAT and Exact Differ SAT, when restricted to some classes of formulas on which SAT is known to be polynomial-time solvable. In particular, we consider affine formulas, Krom formulas (i.e., 2-CNF formulas) and hitting formulas. For affine formulas, we show the following: Both problems are polynomial-time solvable when each equation has at most two variables. Exact Differ SAT is NP-hard, even when each equation has at most three variables and each variable appears in at most four equations. Also, Max Differ SAT is NP-hard, even when each equation has at most four variables. Both problems are 𝖶[1]-hard in the parameter n-d. In contrast, when parameterized by d, Exact Differ SAT is 𝖶[1]-hard, but Max Differ SAT admits a single-exponential FPT algorithm and a polynomial-kernel. For Krom formulas, we show the following: Both problems are polynomial-time solvable when each variable appears in at most two clauses. Also, both problems are 𝖶[1]-hard in the parameter d (and therefore, it turns out, also NP-hard), even on monotone inputs (i.e., formulas with no negative literals). Finally, for hitting formulas, we show that both problems can be solved in polynomial-time.
Cite as

Neeldhara Misra, Harshil Mittal, and Ashutosh Rai. On the Parameterized Complexity of Diverse SAT. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.ISAAC.2024.50,
  author =	{Misra, Neeldhara and Mittal, Harshil and Rai, Ashutosh},
  title =	{{On the Parameterized Complexity of Diverse SAT}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{50:1--50:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.50},
  URN =		{urn:nbn:de:0030-drops-221773},
  doi =		{10.4230/LIPIcs.ISAAC.2024.50},
  annote =	{Keywords: Diverse solutions, Affine formulas, 2-CNF formulas, Hitting formulas}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.31
On the Power of Border Width-2 ABPs over Fields of Characteristic 2

Authors: Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The celebrated result by Ben-Or and Cleve [SICOMP92] showed that algebraic formulas are polynomially equivalent to width-3 algebraic branching programs (ABP) for computing polynomials. i.e., VF = VBP₃. Further, there are simple polynomials, such as ∑_{i = 1}⁸ x_i y_i, that cannot be computed by width-2 ABPs [Allender and Wang, CC16]. Bringmann, Ikenmeyer and Zuiddam, [JACM18], on the other hand, studied these questions in the setting of approximate (i.e., border complexity) computation, and showed the universality of border width-2 ABPs, over fields of characteristic ≠ 2. In particular, they showed that polynomials that can be approximated by formulas can also be approximated (with only a polynomial blowup in size) by width-2 ABPs, i.e., VF ̅ = VBP₂ ̅. The power of border width-2 algebraic branching programs when the characteristic of the field is 2 was left open. In this paper, we show that width-2 ABPs can approximate every polynomial irrespective of the field characteristic. We show that any polynomial f with 𝓁 monomials and with at most t odd-power indeterminates per monomial can be approximated by 𝒪(𝓁⋅ (deg(f)+2^t))-size width-2 ABPs. Since 𝓁 and t are finite, this proves universality of border width-2 ABPs. For univariate polynomials, we improve this upper-bound from O(deg(f)²) to O(deg(f)). Moreover, we show that, if a polynomial f can be approximated by small formulas, then the polynomial f^d, for some small power d, can be approximated by small width-2 ABPs. Therefore, even over fields of characteristic two, border width-2 ABPs are a reasonably powerful computational model. Our construction works over any field.
Cite as

Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar. On the Power of Border Width-2 ABPs over Fields of Characteristic 2. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.STACS.2024.31,
  author =	{Dutta, Pranjal and Ikenmeyer, Christian and Komarath, Balagopal and Mittal, Harshil and Nanoti, Saraswati Girish and Thakkar, Dhara},
  title =	{{On the Power of Border Width-2 ABPs over Fields of Characteristic 2}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.31},
  URN =		{urn:nbn:de:0030-drops-197419},
  doi =		{10.4230/LIPIcs.STACS.2024.31},
  annote =	{Keywords: Algebraic branching programs, border complexity, characteristic 2}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.53
On the Complexity of the Eigenvalue Deletion Problem

Authors: Neeldhara Misra, Harshil Mittal, Saket Saurabh, and Dhara Thakkar

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
For any fixed positive integer r and a given budget k, the r-Eigenvalue Vertex Deletion (r-EVD) problem asks if a graph G admits a subset S of at most k vertices such that the adjacency matrix of G⧵S has at most r distinct eigenvalues. The edge deletion, edge addition, and edge editing variants are defined analogously. For r = 1, r-EVD is equivalent to the Vertex Cover problem. For r = 2, it turns out that r-EVD amounts to removing a subset S of at most k vertices so that G⧵ S is a cluster graph where all connected components have the same size. We show that r-EVD is NP-complete even on bipartite graphs with maximum degree four for every fixed r > 2, and FPT when parameterized by the solution size and the maximum degree of the graph. We also establish several results for the special case when r = 2. For the vertex deletion variant, we show that 2-EVD is NP-complete even on triangle-free and 3d-regular graphs for any d ≥ 2, and also NP-complete on d-regular graphs for any d ≥ 8. The edge deletion, addition, and editing variants are all NP-complete for r = 2. The edge deletion problem admits a polynomial time algorithm if the input is a cluster graph, while - in contrast - the edge addition variant is hard even when the input is a cluster graph. We show that the edge addition variant has a quadratic kernel. The edge deletion and vertex deletion variants admit a single-exponential FPT algorithm when parameterized by the solution size alone. Our main contribution is to develop the complexity landscape for the problem of modifying a graph with the aim of reducing the number of distinct eigenvalues in the spectrum of its adjacency matrix. It turns out that this captures, apart from Vertex Cover, also a natural variation of the problem of modifying to a cluster graph as a special case, which we believe may be of independent interest.
Cite as

Neeldhara Misra, Harshil Mittal, Saket Saurabh, and Dhara Thakkar. On the Complexity of the Eigenvalue Deletion Problem. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.ISAAC.2023.53,
  author =	{Misra, Neeldhara and Mittal, Harshil and Saurabh, Saket and Thakkar, Dhara},
  title =	{{On the Complexity of the Eigenvalue Deletion Problem}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{53:1--53:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.53},
  URN =		{urn:nbn:de:0030-drops-193555},
  doi =		{10.4230/LIPIcs.ISAAC.2023.53},
  annote =	{Keywords: Graph Modification, Rank Reduction, Eigenvalues}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.5
Chess Is Hard Even for a Single Player

Authors: N.R. Aravind, Neeldhara Misra, and Harshil Mittal

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 × 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left. We generalize this game to unbounded boards with n pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board. Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs.
Cite as

N.R. Aravind, Neeldhara Misra, and Harshil Mittal. Chess Is Hard Even for a Single Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aravind_et_al:LIPIcs.FUN.2022.5,
  author =	{Aravind, N.R. and Misra, Neeldhara and Mittal, Harshil},
  title =	{{Chess Is Hard Even for a Single Player}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.5},
  URN =		{urn:nbn:de:0030-drops-159753},
  doi =		{10.4230/LIPIcs.FUN.2022.5},
  annote =	{Keywords: chess, strategy, board games, NP-complete}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact