Parameterized algorithms for feedback set problems and their duals in tournaments.

*(English)*Zbl 1086.68105Summary: The parameterized feedback vertex (arc) set problem is to find whether there are \(k\) vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions.

We also address the parametric dual problems which are also natural optimization problems. We show that they are fixed parameter tractable not just in tournaments but in oriented directed graphs (where there is at most one directed arc between a pair of vertices). More specifically, the dual problem we show fixed parameter tractable are: Given an oriented directed graph, is there a subset of \(k\) vertices (arcs) that forms an acyclic directed subgraph of the graph?

Our main results include:

\(\bullet\) an \(O((2.4143)^{k}n^{\omega})^{1}\) algorithm for weighted feedback vertex set problem, and an \(O((2.415)^{k}n^{\omega })\) algorithm for weighted feedback arc set problem in tournaments;

\(\bullet\) an \(O((e2^{k}/k)^{k}k^{2}+\min \{m \mathrm{lg} n,n^{2}\})\) algorithm for the dual of feedback vertex set problem (maximum vertex induced acyclic graph) in oriented directed graphs, and an \(O(4^{k}k+m)\) algorithm for the dual of feedback arc set problem (maximum arc induced acyclic graph) in general directed graphs.

We also show that the dual of feedback vertex set is \(W[1]\)-hard in general directed graphs and the feedback arc set problem is fixed parameter tractable in dense directed graphs. Our results are the first non-trivial results for these problems.

We also address the parametric dual problems which are also natural optimization problems. We show that they are fixed parameter tractable not just in tournaments but in oriented directed graphs (where there is at most one directed arc between a pair of vertices). More specifically, the dual problem we show fixed parameter tractable are: Given an oriented directed graph, is there a subset of \(k\) vertices (arcs) that forms an acyclic directed subgraph of the graph?

Our main results include:

\(\bullet\) an \(O((2.4143)^{k}n^{\omega})^{1}\) algorithm for weighted feedback vertex set problem, and an \(O((2.415)^{k}n^{\omega })\) algorithm for weighted feedback arc set problem in tournaments;

\(\bullet\) an \(O((e2^{k}/k)^{k}k^{2}+\min \{m \mathrm{lg} n,n^{2}\})\) algorithm for the dual of feedback vertex set problem (maximum vertex induced acyclic graph) in oriented directed graphs, and an \(O(4^{k}k+m)\) algorithm for the dual of feedback arc set problem (maximum arc induced acyclic graph) in general directed graphs.

We also show that the dual of feedback vertex set is \(W[1]\)-hard in general directed graphs and the feedback arc set problem is fixed parameter tractable in dense directed graphs. Our results are the first non-trivial results for these problems.

##### MSC:

68R10 | Graph theory (including graph drawing) in computer science |

05C20 | Directed graphs (digraphs), tournaments |

05C85 | Graph algorithms (graph-theoretic aspects) |

68Q25 | Analysis of algorithms and problem complexity |

PDF
BibTeX
XML
Cite

\textit{V. Raman} and \textit{S. Saurabh}, Theor. Comput. Sci. 351, No. 3, 446--458 (2006; Zbl 1086.68105)

Full Text:
DOI

##### References:

[1] | Bang-Jensen, J.; Gutin, G., Digraphs theory, algorithms and applications, (2001), Springer Berlin · Zbl 0958.05002 |

[2] | Bermond, J.C.; Germa, A.; Heydemann, M.C.; Sotteau, D., Girth in digraphs, J. graph theory, 4, 3, 337-341, (1980) · Zbl 0412.05048 |

[3] | Cai, L.; Juedes, D., On the existence of subexponential parameterized algorithms, J. computer system sci., 67, 4, 789-807, (2003) · Zbl 1091.68121 |

[4] | C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank aggregation revisited, manuscript available at: \(<\)www.cs.northwestern.edu/\(\sim\)kao/cs395-ecommerce/reading_document_ranking/ecom.document_ranking.dwork.pdf>. |

[5] | Even, G.; (Seffi) Naor, J.; Schieber, B.; Sudan, M., Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20, 151-174, (1998) · Zbl 0897.68078 |

[6] | Fellows, M.; Hallett, M.; Korostensky, C.; Stege, U., Analogs and duals of the MAST problem for sequences and trees, J. algorithms, 49, 1, 192-216, (2003) · Zbl 1064.68044 |

[7] | T. Gallai, On directed paths and circuits, in: P. Erdős, G. Katona (Eds.), Theory of Graphs, Proceedings Colloquium Tihnay, 1968, pp. 115-118. · Zbl 0159.54403 |

[8] | Ya, E.; Grinberg; Dambit, Ya.Ya., Nekotorye svoistva grafov soderzhashchikh kontury, Latviiskii mathematicheskii ezhegodnile, 2, 65-70, (1966), (Russian: Some Properties of Directed Graphs With Circuits) |

[9] | Itai, A.; Rodeh, M., Finding a minimum circuit in a graph, SIAM J. comput., 7, 4, 413-423, (1978) · Zbl 0386.68064 |

[10] | Khot, S.; Raman, V., Parameterized complexity of finding subgraphs with hereditary properties, Theoret. comput. sci., 289, 997-1008, (2002) · Zbl 1061.68061 |

[11] | Mahajan, M.; Raman, V., Parameterizing above guaranteed values: maxsat and maxcut, J. algorithms, 31, 335-354, (1999) · Zbl 0921.68052 |

[12] | Niedermeier, R.; Rossmanith, P., An efficient fixed parameter algorithm for 3-hitting set, J. discrete algorithms, 1, 1, 89-102, (2003) · Zbl 1118.68511 |

[13] | Poljak, S.; Turzik, D., A polynomial algorithm for constructing a large bipartite aubgraph, with an application to a satisfiability problem, Canad. J. math, 34, 3, 519-524, (1982) · Zbl 0471.68041 |

[14] | V. Raman, S. Saurabh, Parameterized complexity of directed feedback set problems in tournaments’, in: Proc. Workshop on Data Structures and Algorithms (WADS 2003), Lecture Notes in Computer Science, Vol. 2748, Springer, Berlin, 2003, pp. 484-492. · Zbl 1278.68110 |

[15] | V. Raman, S. Saurabh, Improved parameterized algorithms for feedback set problems in weighted tournaments, in: Proc. Internat. Workshop on Parameterized and Exact Computation (IWPEC 2004), Lecture Notes in Computer Science, Vol. 3162, Springer, Berlin, 2004, pp. 260-270. · Zbl 1104.68547 |

[16] | V. Raman, S. Saurabh, C.R. Subramanian, Faster fixed parameter tractable algorithms for undirected feedback vertex set, in: Proc. 13th Internat. Symp. on Algorithms and Computation (ISAAC 2002), Lecture Notes in Computer Science, Vol. 2518, Springer, Berlin, 2002, pp. 241-248. · Zbl 1019.68082 |

[17] | Raman, V.; Saurabh, S.; Subramanian, C.R., Faster algorithms for feedback vertex set, in: proc. second Brazilian symp. on graphs, algorithms and combinatorics (GRACO 2005), Electronic notes in discrete mathematics, 19, 273-279, (2005) |

[18] | E. Speckenmeyer, On feedback problems in digraphs, in: Proc. 15th Internat. Workshop WG’89, Lecture Notes in Computer Science, Vol. 411, Springer, Berlin, 1989, pp. 218-231. · Zbl 0768.68181 |

[19] | N. Alon, Ranking tournaments. SIAM Journal of Discrete Mathematics, to appear. · Zbl 1112.05043 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.