id: 05823288
dt: a
an: 05823288
au: Gutin, Gregory; Kim, Eun Jung; Soleimanfallah, Arezou; Szeider, Stefan;
    Yeo, Anders
ti: Parameterized complexity results for general factors in bipartite graphs
    with an application to constraint programming.
so: Raman, Venkatesh (ed.) et al., Parameterized and exact computation. 5th
    international symposium, IPEC 2010, Chennai, India, December 13‒15,
    2010. Proceedings. Berlin: Springer (ISBN 978-3-642-17492-6/pbk).
    Lecture Notes in Computer Science 6478, 158-169 (2010).
py: 2010
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-17493-3_16
ab: Summary: 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 \uplus 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
    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.
rv: