### Resumé

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 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.

Originalsprog | Engelsk |
---|---|

Tidsskrift | Algorithmica |

Vol/bind | 64 |

Udgave nummer | 1 |

Sider (fra-til) | 112-125 |

ISSN | 0178-4617 |

DOI | |

Status | Udgivet - 2012 |

Udgivet eksternt | Ja |

### Fingeraftryk

### Citer dette

*Algorithmica*,

*64*(1), 112-125. https://doi.org/10.1007/s00453-011-9548-8

}

*Algorithmica*, bind 64, nr. 1, s. 112-125. https://doi.org/10.1007/s00453-011-9548-8

**Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming.** / Gutin, Gregory; Kim, Eun Jung; Soleimanfallah, Arezou; Szeider, Stefan; Yeo, Anders.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

TY - JOUR

T1 - Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming

AU - Gutin, Gregory

AU - Kim, Eun Jung

AU - Soleimanfallah, Arezou

AU - Szeider, Stefan

AU - Yeo, Anders

PY - 2012

Y1 - 2012

N2 - 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 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.

AB - 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 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.

KW - Fixed-parameter tractable

KW - General factor

KW - Global constraint

U2 - 10.1007/s00453-011-9548-8

DO - 10.1007/s00453-011-9548-8

M3 - Journal article

VL - 64

SP - 112

EP - 125

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -