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

Gregory Gutin, Eun Jung Kim, Arezou Soleimanfallah, Stefan Szeider*, Anders Yeo

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

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.

OriginalsprogEngelsk
TidsskriftAlgorithmica
Vol/bind64
Udgave nummer1
Sider (fra-til)112-125
ISSN0178-4617
DOI
StatusUdgivet - 2012
Udgivet eksterntJa

Fingeraftryk

Parameterized Complexity
Constraint Programming
Dynamic programming
Bipartite Graph
Computational complexity
Polynomials
Graph in graph theory
Vertex of a graph
Fixed-parameter Tractability
Cardinality Constraints
Global Constraints
Spanning Subgraph
NP-hard Problems
Dynamic Programming
Polynomial time
NP-complete problem
Partition
Integer

Citer dette

Gutin, Gregory ; Kim, Eun Jung ; Soleimanfallah, Arezou ; Szeider, Stefan ; Yeo, Anders. / Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming. I: Algorithmica. 2012 ; Bind 64, Nr. 1. s. 112-125.
@article{9e66a6cec41743108acde40527fa393a,
title = "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 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.",
keywords = "Fixed-parameter tractable, General factor, Global constraint",
author = "Gregory Gutin and Kim, {Eun Jung} and Arezou Soleimanfallah and Stefan Szeider and Anders Yeo",
year = "2012",
doi = "10.1007/s00453-011-9548-8",
language = "English",
volume = "64",
pages = "112--125",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "1",

}

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.

I: Algorithmica, Bind 64, Nr. 1, 2012, s. 112-125.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer 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 -