DROPS

Document

DOI: 10.4230/LIPIcs.WADS.2025.19

On the Enumeration of Signatures of XOR-CNF’s

Authors: Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

Given a CNF formula φ with clauses C_1, … , C_m over a set of variables V, a truth assignment 𝐚: V → {0, 1} generates a binary sequence σ_φ(𝐚) = (C_1(𝐚), …, C_m(𝐚)), called a signature of φ, where C_i(𝐚) = 1 if clause C_i evaluates to 1 under assignment 𝐚, and C_i(𝐚) = 0 otherwise. Signatures and their associated generation problems have given rise to new yet promising research questions in algorithmic enumeration. In a recent paper, Bérczi et al. interestingly proved that generating signatures of a CNF is tractable despite the fact that verifying a solution is hard. They also showed the hardness of finding maximal signatures of an arbitrary CNF due to the intractability of satisfiability in general. Their contribution leaves open the problem of efficiently generating maximal signatures for tractable classes of CNFs, i.e., those for which satisfiability can be solved in polynomial time. Stepping into that direction, we completely characterize the complexity of generating all, minimal, and maximal signatures for XOR-CNF’s.

Cite as

Nadia Creignou, Oscar Defrain, Frédéric Olive, and Simon Vilmin. On the Enumeration of Signatures of XOR-CNF’s. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{creignou_et_al:LIPIcs.WADS.2025.19,
  author =	{Creignou, Nadia and Defrain, Oscar and Olive, Fr\'{e}d\'{e}ric and Vilmin, Simon},
  title =	{{On the Enumeration of Signatures of XOR-CNF’s}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.19},
  URN =		{urn:nbn:de:0030-drops-242508},
  doi =		{10.4230/LIPIcs.WADS.2025.19},
  annote =	{Keywords: Algorithmic enumeration, XOR-CNF, signatures, maximal bipartite subgraphs enumeration, extension, proximity search}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2024.51

Half-Space Separation in Monophonic Convexity

Authors: Mohammed Elaroussi, Lhouari Nourine, and Simon Vilmin

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

We study half-space separation in the convexity of chordless paths of a graph, i.e., monophonic convexity. In this problem, one is given a graph and two (disjoint) subsets of vertices and asks whether these two sets can be separated by complementary convex sets, called half-spaces. While it is known this problem is NP-complete for geodesic convexity - the convexity of shortest paths - we show that it can be solved in polynomial time for monophonic convexity.

Cite as

Mohammed Elaroussi, Lhouari Nourine, and Simon Vilmin. Half-Space Separation in Monophonic Convexity. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{elaroussi_et_al:LIPIcs.MFCS.2024.51,
  author =	{Elaroussi, Mohammed and Nourine, Lhouari and Vilmin, Simon},
  title =	{{Half-Space Separation in Monophonic Convexity}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{51:1--51:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.51},
  URN =		{urn:nbn:de:0030-drops-206070},
  doi =		{10.4230/LIPIcs.MFCS.2024.51},
  annote =	{Keywords: chordless paths, monophonic convexity, separation, half-space}
}

Search Results

Documents authored by Vilmin, Simon

On the Enumeration of Signatures of XOR-CNF’s

Abstract

Cite as

Half-Space Separation in Monophonic Convexity

Abstract

Cite as

Thanks for your feedback!

Could not send message