Weighted Counting of Matchings in ...
Type de document :
Communication dans un congrès avec actes
Titre :
Weighted Counting of Matchings in Unbounded-Treewidth Graph Families
Auteur(s) :
Amarilli, Antoine [Auteur]
Data, Intelligence and Graphs [DIG]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
Inria Lille - Nord Europe
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Data, Intelligence and Graphs [DIG]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
Inria Lille - Nord Europe
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Titre de la manifestation scientifique :
MFCS
Ville :
Vienna
Pays :
Autriche
Date de début de la manifestation scientifique :
2022-08-22
Titre de l’ouvrage :
Proceedings of MFCS
Discipline(s) HAL :
Informatique [cs]/Base de données [cs.DB]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Logique en informatique [cs.LO]
Informatique [cs]/Théorie et langage formel [cs.FL]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Logique en informatique [cs.LO]
Informatique [cs]/Théorie et langage formel [cs.FL]
Résumé en anglais : [en]
We consider a weighted counting problem on matchings, denoted $\textrm{PrMatching}(\mathcal{G})$, on an arbitrary fixed graph family $\mathcal{G}$. The input consists of a graph $G\in \mathcal{G}$ and of rational probabilities ...
Lire la suite >We consider a weighted counting problem on matchings, denoted $\textrm{PrMatching}(\mathcal{G})$, on an arbitrary fixed graph family $\mathcal{G}$. The input consists of a graph $G\in \mathcal{G}$ and of rational probabilities of existence on every edge of $G$, assuming independence. The output is the probability of obtaining a matching of $G$ in the resulting distribution, i.e., a set of edges that are pairwise disjoint. It is known that, if $\mathcal{G}$ has bounded treewidth, then $\textrm{PrMatching}(\mathcal{G})$ can be solved in polynomial time. In this paper we show that, under some assumptions, bounded treewidth in fact characterizes the tractable graph families for this problem. More precisely, we show intractability for all graph families $\mathcal{G}$ satisfying the following treewidth-constructibility requirement: given an integer $k$ in unary, we can construct in polynomial time a graph $G \in \mathcal{G}$ with treewidth at least $k$. Our hardness result is then the following: for any treewidth-constructible graph family $\mathcal{G}$, the problem $\textrm{PrMatching}(\mathcal{G})$ is intractable. This generalizes known hardness results for weighted matching counting under some restrictions that do not bound treewidth, e.g., being planar, 3-regular, or bipartite; it also answers a question left open in Amarilli, Bourhis and Senellart (PODS'16). We also obtain a similar lower bound for the weighted counting of edge covers.Lire moins >
Lire la suite >We consider a weighted counting problem on matchings, denoted $\textrm{PrMatching}(\mathcal{G})$, on an arbitrary fixed graph family $\mathcal{G}$. The input consists of a graph $G\in \mathcal{G}$ and of rational probabilities of existence on every edge of $G$, assuming independence. The output is the probability of obtaining a matching of $G$ in the resulting distribution, i.e., a set of edges that are pairwise disjoint. It is known that, if $\mathcal{G}$ has bounded treewidth, then $\textrm{PrMatching}(\mathcal{G})$ can be solved in polynomial time. In this paper we show that, under some assumptions, bounded treewidth in fact characterizes the tractable graph families for this problem. More precisely, we show intractability for all graph families $\mathcal{G}$ satisfying the following treewidth-constructibility requirement: given an integer $k$ in unary, we can construct in polynomial time a graph $G \in \mathcal{G}$ with treewidth at least $k$. Our hardness result is then the following: for any treewidth-constructible graph family $\mathcal{G}$, the problem $\textrm{PrMatching}(\mathcal{G})$ is intractable. This generalizes known hardness results for weighted matching counting under some restrictions that do not bound treewidth, e.g., being planar, 3-regular, or bipartite; it also answers a question left open in Amarilli, Bourhis and Senellart (PODS'16). We also obtain a similar lower bound for the weighted counting of edge covers.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Projet ANR :
Commentaire :
34 pages, including 12 pages of main text
Collections :
Source :
Fichiers
- http://arxiv.org/pdf/2205.00851
- Accès libre
- Accéder au document
- 2205.00851
- Accès libre
- Accéder au document