Detecting Feedback Vertex Sets in Graphs
Feedback Vertex Sets (FVS) play a crucial role in solving deadlock recovery in operating systems. This research explores the efficient detection of FVS of various sizes in undirected graphs, impacting deadlock resolution and system performance. The study delves into algorithms and techniques for identifying FVS and their applications in forest theory, offering insights into the complexity and challenges of solving NP-complete problems in graph theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Detecting Feedback Vertex Sets of size ? in ? (2.7?)Time JOINT WORK WITH JASON LI CARNEGIE MELLON UNIVERSITY Appeared at SODA 20 (invited to TALG special issue )
Feedback Vertex Sets A Feedback Vertex Set (FVS)of an undirected graph ? = (?,?) is a subset ? ?such that ? ? ? is a forest. In operating systems, feedback vertex sets play a prominent role in the study of deadlock recovery. In the wait-for graph of an operating system, each directed cycle corresponds to a deadlock situation. In order to resolve all deadlocks, some blocked processes have to be aborted.
Feedback Vertex Sets A Feedback Vertex Set (FVS) of an undirected graph ? = (?,?) is a subset ? ?such that ? ? ? is a forest. Feedback Vertex Set Given: Undirected graph ?, integer ? Asked: Does ? have a FVS of size at most ?? Unfortunately, NP-complete. Today: What if ? is small? How fast can we solve it?
Becker et al. (2000) FVS(? = (?,?), ?) 1. If ? has no cycle return true, 2. If ? = 0return false 3.If ? has a vertex of degree 1, remove it 4. If ? has a vertex of degree 2, shortcut it 5. Uniformly sample {?,?} ? and ? {?,?} 6. Return FVS ? ?,? 1 ? ? ? ? ? ? ? ? ? ? If ? is FVS of ? ?, then ? ? is FVS of ? Always correct if it outputs true
Becker et al. (2000) Forest ? = (??,??) FVS(? = (?,?), ?) 1. If ? has no cycle return true, 2. If ? = 0return false 3.If ? has a vertex of degree 1, remove it 4. If ? has a vertex of degree 2, shortcut it 5. Uniformly sample {?,?} ? and ? {?,?} 6. Return FVS ? ?,? 1 FVS ? Lemma If ? has a FVS of size at most ?, Pr[FVS ?,? = true] 1/4k Claim ?? |?|/2 But ? ??deg ? 3|??| Since ? forest, ?? ?? ?? contributes at most 2 ?? At least |??| edges not in ??, but incident to |??| Proof by induction on ? Suppose ? is a FVS of size most k We show Pr ? ? 1/4 Thus by Claim, Pr ?,? ?? 1/2 If ?,? ??, at least one of ?,? is in ?
Becker et al. (2000) FVS(? = (?,?), ?) 1. If ? has no cycle return true, 2. If ? = 0return false 3.If ? has a vertex of degree 1, remove it 4. If ? has a vertex of degree 2, shortcut it 5. Uniformly sample {?,?} ? and ? {?,?} 6. Return FVS ? ?,? 1 Lemma If ? has a FVS of size at most ?, Pr[FVS ?,? = true] 1/4k Use 4? independent runs of FVS(?,?) Runs in ? (4?) time If ? has no FVS of size k, all runs return false Using 1 + ? ?? 4? 1 If ? has a FVS of size k, some run returns true with prob 1 1 1 1/? 4?
Guo et al. (2006), Dehne et al. (2007) Forest ? = (??,??) FVS ? Given FVS ?, we immediately have a tree decomposition of width ? a b c a Given a tree decomposition of width ?, a FVS of minimum size can be found detected in time O (? ? ) for some function ? b c d d e f f e g h i g h i Circularreasoningworksbecause One can use a technique called iterative compression to bootstrap
Cygan et al. (2011) Forest ? = (??,??) FVS ? Given FVS ?, we immediately have a tree decomposition of width ? a b c a Given a tree decomposition of width ?, a FVS of minimum size can be found detected in time ? (? ? ) for some function ? ? (3?). Not in O (2.9999?) time, assuming SETH!! b c d d e f f e g h i g h i Circularreasoningworksbecause One can use a technique called iterative compression to bootstrap
Our Appoach 1. Analyse the approach of Becker et al. to ensure: There is a FVS ? of size ? such that each vertex in X has average degree c, for some constant c 2. Use iterative compression technique to find such a FVS Given ?, compute tree decomposition of treewidth (1 2 ?+1+ ?(1))? 3. Run the O (3?) time algorithm of Cygan et al. 4.
Separations Separation: Partition of vertices into ? ? ?, such that no edges from ? to ? ? ? ? Ideally we want |?| small and ? |?| G has separator with ? = ?, |?| |?| if ? = (? ?,?) is bipartite, ? = ? ? has a FVS of size ? ? has a tree decomposition of width ?
Smaller Separations Lemma Let ? = (? = ? ?,?) be bipartite such that ? = ?, and vertices in ? have average degree at most ?. Then ? has a separation ? = ? ? ? with ? ? and ? ? , ? ? 2 ? ? 1 ? ? R L L R R ? S R S S S R (1) Add each vertex in ? with prob 1/2 to ? or ? For every vertex ? ?: a) If ? ? ?, add ? to ? b) If ? ? ?, add ? to ? c) Otherwise, add ? to ? (1) holds in expectation: ? ? ? ,? ? ? 1. 2. ? ? ? // has pr 2 d(?) // has pr 2 d(?) // has pr 1 2 ? ? +1 ? ? ? ? ?/2? We show Pr ? ? 2 ? ? 1 ? 0.99; Implies (1) If events 2a-2c were independent -> standard Chernoff bound Partition events in ?2groups of pairwise indep. events R S S S S R ? = (?,{?,?:??? ??? })
Smaller Separations Lemma Let ? = (? = ? ?,?) be bipartite such that ? = ?, and vertices in ? have average degree at most ?. Then ? has a separation ? = ? ? ? with ? ? and ? ? , ? ? 2 ? ? 1 ? ? (1 2 ?+1+ ?(1))? ? add vertices of degree ? to ?, then continue as before Lemma Let ? be a FVS of ? such that ? = ?, and vertices in ? have average degree at most ?. Then ? has a separation ? = ? ? ? with ? ? and ? ? , ? ? 2 ? ? 1 ? ? (1 2 ?+1+ ?(1))? ? Add set ? of ?? vertices of ? to ? st each cc of ? ? has at most ?/? edges to ? Do as before, treat each cc of ? ? as a single vertex
Smaller Separations Lemma Let ? be a FVS of ? such that ? = ?, and vertices in ? have average degree at most ?. Then ? has a separation ? = ? ? ? with ? ? and ? ? , ? ? 2 ? ? 1 ? ? (1 2 ?+1+ ?(1))? ? ? ? ? ? ? ? Gives tree decomposition of width at most (1 2 ?+1+?(1))? Thus we can run the ? 3?= ? (2.99999..?) time algo
Our Appoach 1. Analyse the approach of Becker et al. to ensure: There is a FVS ? of size ? such that each vertex in X has average degree c, for some constant c 2. Use iterative compression technique to find such a FVS Given ?, compute tree decomposition of treewidth (1 2 ?+1+ ?(1))? 3. Run the O (3?) time algorithm of Cygan et al. 4.
Becker et al. (2000) FVS(? = (?,?), ?) 1. If ? has no cycle return true, 2. If k=0return false 3.If ? has a vertex of degree 1, remove it 4. If ? has a vertex of degree 2, shortcut it 5. Uniformly sample {?,?} ? and ? {?,?} 6. Return FVS ? ?,? 1 Forest ? = (??,??) FVS ? Clearly always correct if it outputs true Lemma If ? has a FVS of size at most ?, Pr[FVS ?,? = true] 1/4k Claim ?? |?|/2 Since ? forest, ?? ?? But ? ??deg ? 3|??| ?? contributes at most 2 ?? At least |??| edges not in ?? Prove by induction on ? Suppose ? is a FVS of size most k We show Pr ? ? 1/4 Thus by Claim, Pr ?,? ?? 1/2 If ?,? ??, at least one of ?,? is in ?
Further Improvements The authors dig a deeper mine, adding a number of other ideas, and obtain the promised ~2.7^k * poly(n) complexity. -- Reviewer #252B Separate the graph in three parts Employ matrix multiplication Becomes very technical .
Further Research Better separations in bipartite graphs of bounded maximum degree? Better treewidth bounds in bipartite graphs of bounded maximum degree? Can we leverage structure of tree decompositions in other cases? Find a simple path on ? vertices Thanks for listening!!
