Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming

Abstract : The NP-hard general factor problem asks, given a graph and for each vertex a list of integers, whether the graph has a spanning subgraph where each vertex has a degree that belongs to its assigned list. The problem remains NP-hard even if the given graph is bipartite with partition U⊎V, and each vertex in U is assigned the list {1}; this subproblem appears in the context of constraint programming as the consistency problem for the extended global cardinality constraint. We show that this subproblem is fixed-parameter tractable when parameterized by the size of the second partite set V. More generally, we show that the general factor problem for bipartite graphs, parameterized by |V|, is fixed-parameter tractable as long as all vertices in U are assigned lists of length 1, but becomes \normalfont W[1] -hard if vertices in U are assigned lists of length at most 2. We establish fixed-parameter tractability by reducing the problem instance to a bounded number of acyclic instances, each of which can be solved in polynomial time by dynamic programming.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2012, 64, pp.112-125. 〈10.1007/s00453-011-9548-8〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00807998
Contributeur : Alexandre Pinlou <>
Soumis le : jeudi 4 avril 2013 - 16:47:03
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

Lien texte intégral

Identifiants

Collections

Citation

Gregory Gutin, Eunjung Kim, Arezou Soleimanfallah, Stefan Szeider, Anders Yeo. Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming. Algorithmica, Springer Verlag, 2012, 64, pp.112-125. 〈10.1007/s00453-011-9548-8〉. 〈lirmm-00807998〉

Partager

Métriques

Consultations de la notice

87