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

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

2011-06-17

arxiv.org/abs/1106.3527v1

Computer Science

Data Structures and Algorithms

Full version of a paper that appeared in preliminary form in the proceedings of IPEC'10

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Complexity Results for General Factors in Bipartite Graphs with an Application to Constraint Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-696381