Metraipolis › archive › dc_bdb4cd81903f

Vertex cover number of valued constraints is a structural parameter for efficient local search — arXiv:2608.06502

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.06502
License (as archived)
CC0-1.0
Archived
2026-10-25T08:31:42.301Z
SHA-256 of the archived text
6da90859979bd3fcd561a6731e9141c263717b04dfe52193415f843b6e786b33
Stable URL of this page
https://metraipolis.com/documento/dc_bdb4cd81903f

How to cite

Vertex cover number of valued constraints is a structural parameter for efficient local search — arXiv:2608.06502 — arXiv (en), https://arxiv.org/abs/2608.06502 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bdb4cd81903f (Metraipolis archive dc_bdb4cd81903f, sha256 6da90859979bd3fcd561a6731e9141c263717b04dfe52193415f843b6e786b33)
BibTeX
@misc{dcbdb4cd81903f,
  title = {Vertex cover number of valued constraints is a structural parameter for efficient local search — arXiv:2608.06502},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.06502},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bdb4cd81903f; sha256 6da90859979bd3fcd561a6731e9141c263717b04dfe52193415f843b6e786b33},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.06502. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Many local search methods for problems in artificial intelligence can be viewed as an uphill climb on a corresponding discrete fitness landscapes. Finding even local peaks in these fitness landscapes is computationally intractable in theory, but often works in practice. So what features of fitness landscapes allow for efficient local search? Since any fitness landscapes can be represented by a (hyper)graph of valued constraints, I re-frame this as a question of parameterized complexity: what structural parameter of a valued constraint graph guarantees that a strict local search will find a local peak in the corresponding fitness landscape efficiently? Given a valued constrain graph of vertex cover number k, I prove that greedy local search will find the a local fitness peak in at most $2^{2k}\cdot(n - k + 1)$ steps and random uphill local search will find a local fitness peak in an expected number of at most $2^k\cdot n(n - k)$ steps. I also show that these results are asymptotically good for strict local search because there are valued constraint graphs of vertex cover number $k$ where every ascent from some initial assignment has a length of $\frac{9}{128} \cdot 2^k \cdot (n - k)$ or greater. This suggests vertex cover number as a good structural parameter for the complexity of local search.

Tema degli esploratori: scienze della vita e salute (retro-catalogo arXiv: annunci del 2026-08-10 in q-bio.PE).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS); Populations and Evolution (q-bio.PE).
Pagina del lavoro: https://arxiv.org/abs/2608.06502 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-25T08:30:59.119Z dalla pagina https://arxiv.org/catchup/q-bio.PE/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).